Given an undirected graph G=(V,E) and a positive integer k∈1,…,|V|, we initiate the combinatorial study of stable sets of cardinality exactly k in G. Our aim is to instigate the polyhedral investigation of the convex hull of fixed cardinality stable sets, inspired by the rich theory on the classical structure of stable sets. We introduce a large class of valid inequalities to the natural integer programming formulation of the problem. We also present simple combinatorial relaxations based on computing maximum weighted matchings, which yield dual bounds towards finding minimum-weight fixed cardinality stable sets, and particular cases which are solvable in polynomial time.

The pooling problem is a frequently studied extension of the traditional minimum cost flow problem, in which the composition of the flow is subject to restrictions. In a network consisting of three layers of nodes, the composition is given at the source layer. In the intermediate nodes, referred to as pools, the composition is a weighted average of the compositions in entering flow streams. The same is true at the sink layer, where upper bounds on the concentration of each component apply. Motivated by practical applications, and needs for heuristic methods for the standard pooling problem, the current work focuses on pooling problems where the flow graph is restricted to satisfy certain sparsity conditions. We consider in particular the requirements that each pool receives flow from at most one neighboring source, or sends flow to at most one neighboring sink. We prove that the pooling problem remains NP-hard after this and other similar extensions. It is also demonstrated how the single-flow constrained extensions can be modeled by means of mixed integer linear programming (MILP), without introducing bilinear terms. We also show that such MILP-models are useful for computing good feasible solutions to the original problem.

We consider the problem of constructing a shared broadcast tree (SBT) in wireless networks, such that the total power required for supporting broadcast initiated by all source nodes is minimal. In the well-studied minimum-energy broadcast (MEB) problem, the optimal tree varies by source. In contrast, SBT is source-independent, thus substantially reducing the overhead for information storage and processing. The SBT problem also differs from the range assignment problem (RAP), because the power for message forwarding in SBT, although being source-independent, depends on from which tree neighbor the message is received. We approach SBT from a computational optimization standpoint, and present a dual decomposition method applied to an optimization model that embeds multiple directed trees into a shared tree. For the dual decomposition method, some of the constraints in the model are preferably formulated implicitly. The dual decomposition scheme is coupled with a fast local search algorithm. We report computational results demonstrating the effectiveness of the proposed approach. In average, the performance gap to global optimality is less than three percent.

The pooling problem is an important global optimization problem which is encountered in many industrial settings. It is traditionally modeled as a bilinear, nonconvex optimization problem, and solved by branch-and-bound algorithms where the subproblems are convex. In some industrial applications, for instance in pipeline transportation of natural gas, a different modeling approach is often made. Rather than defining it as a bilinear problem, the range of qualities is discretized, and the complicating constraints are replaced by linear ones involving integer variables. Consequently, the pooling problem is approximated by a mixed-integer programming problem. With a coarse discretization, this approach represents a saving in computational effort, but may also lead to less accurate modeling. Justified guidelines for choosing between a bilinear and a discrete model seem to be scarce in the pooling problem literature. In the present work, we study discretized versions of models that have been proved to work well when formulated as bilinear programs. Through extensive numerical experiments, we compare the discrete models to their continuous ancestors. In particular, we study how the level of discretization must be chosen if a discrete model is going to be competitive in both running time and accuracy.

Abstract A multicast session in a wireless ad hoc network concerns routing messages from a source to a set of destination devices. Transmitting messages consumes energy at the source and intermediate devices of the session. Since a battery is the only energy source in many applications of wireless ad hoc networks, energy efficiency is an important performance measure of multicasting. In this paper, we present and analyze integer programming models for the problem of minimizing the total energy required by multicasting. We start from a straightforward multicommodity flow model, which is strengthened by a more efficient representation of transmission power. Further strengthening is accomplished by lifting the capacity constraints of the model. We then present cut‐based models for the problem, and prove, from a bounding standpoint, the equivalence in strength between these models and their flow‐based counterparts. By expanding the underlying graph, we show that the problem can be transformed into finding a minimum Steiner arborescence. The expanded graph arises also in the separation procedure for solving one of the cut‐based models. In addition to a theoretical analysis of the relation between various models, we perform extensive computational experiments to study the numerical strengths of these models and their efficiency in solving the problem. © 2008 Wiley Periodicals, Inc. NETWORKS, 2008

We present a signal compression scheme based on coding linear segments approximating the signal. Although the approach is useful for many types of signals, we focus in this paper on compression of electrocardiogram (EGG) signals. The ECG signal compression has traditionally been tackled by heuristic approaches. However, it has been demonstrated that exact optimization algorithms outclass these heuristic approaches by a wide margin with respect to the reconstruction error. The exact optimization algorithm extracts signal samples from the original signal by formulating the sample selection problem as a graph theory problem. Thus known optimization theory can be applied in order to yield optimal compression. This paper generalizes the exact optimization scheme by removing the interpolation restriction when applying piecewise linear approximation. This guarantees a lower reconstruction error with respect to the number of extracted signal samples. The method shows superior performance compared to traditional ECG compression methods.

Compression of digital electrocardiogram (ECG) signals has traditionally been tackled by heuristical approaches. It has been demonstrated that exact optimization algorithms outclass these heuristical approaches by a wide margin with respect to the reconstruction error. As opposed to traditional time-domain algorithms, where some heuristic is used to extract representative signal samples from the original signal, the exact optimization algorithm proposed by Haugland, Heber and Husoy (see Medical & Biological Engineering & Computing, vol.35, p.420-24, 1997) formulates the sample selection problem as a graph theory problem. Thus well known optimization theory can be applied in order to yield optimal compression. Haughland et al. applied linear interpolation in the reconstruction of the signal. This paper generalizes the optimization algorithm such that reconstruction can be made by second order polynomial interpolation in the extracted signal samples. The polynomials are fitted in a way that guarantees minimal reconstruction error, and the method proves the good performance compared to the case where linear interpolation is used in the reconstruction of the signal.

Compression of image contours is an important problem in many contexts. An example is object oriented video coding, where efficient encoding of shape information of arbitrarily shaped objects is a major problem. This paper presents a method for compressing contours by extracting representative points from the original curve. By formulating the point selection problem as a graph theory problem, known optimization theory can be applied in order to yield optimal compression with respect to a given error bound. The contour is reconstructed based on linear interpolation among the extracted curve points. The method presented guarantees a minimal distortion for a given number of retained curve points. Compared to many other compression methods, this method shows superior performance.