A classical theorem by Block and Levin says that certain variants of the relaxation method for solving systems of linear inequalities produce bounded sequences of intermediate solutions even when running on inconsistent input data. Using a new approach, we prove a more general version of this result and answer an old open problem of quantifying … Read more
Representation of a given nonnegative multivariate polynomial in terms of a sum of squares of polynomials has become an essential subject in recent developments of sums of squares optimization and SDP (semidefinite programming) relaxation of polynomial optimization problems. We disscuss effective methods to obtain a simpler representation of a “sparse” polynomial as a sum of … Read more
In this paper we use facets of mixed-integer sets with two and three variables to derive valid inequalities for integer sets defined by a single equation. These inequalities also define facets of the master cyclic group polyhedron of Gomory. Facets of this polyhedron give strong valid inequalities for general mixed-integer sets, such as the well-known … Read more
In a previous work, we proposed a new integer programming formulation for the graph coloring problem which, to a certain extent, avoids symmetry. We studied the facet structure of the 0/1-polytope associated with it. Based on these theoretical results, we present now a Branch-and-Cut algorithm for the graph coloring problem. Our computational experiences compare favorably … Read more
Stable multi-sets are an evident generalization of the well-known stable sets. As integer programs, they constitute a general structure which allows for a wide applicability of the results. Moreover, the study of stable multi-sets provides new insights to well-known properties of stable sets. In this paper, we continue our investigations started in Koster and Zymolka … Read more
The concentrator location problem is to choose a subset of a given terminal set to install concentrators and to assign each remaining terminal node to a concentrator to minimize the cost of installation and assignment. The concentrators may have capacity constraints. We study the polyhedral properties of concentrator location problems with different capacity structures. We … Read more
We propose an algorithm based on Barvinok’s counting algorithm for P -> max {c’x | Ax
The hub location problem with single assignment is the problem of locating hubs and assigning the terminal nodes to hubs in order to minimize the cost of hub installation and the cost of routing the traffic in the network. There may also be capacity restrictions on the amount of traffic that can transit by hubs. … Read more
We consider the integer program $\max \{c’ x\,|\,Ax=b,x\in N^n\}$. A formal parallel between linear programming and continuous integration on one side, and discrete summation on the other side, shows that a natural duality for integer programs can be derived from the $Z$-transform and Brion and Vergne’s counting formula. Along the same lines, we also provide … Read more
Given $A\in Z^{m\times n}$ and $b\in Z^m$, we consider the integer program $\max \{c’x\vert Ax=b;x\in N^n\}$ and provide an equivalent and explicit linear program $\max \{\widehat{c}’q\vert M q=r;q\geq 0\}$, where $M,r,\widehat{c}$ are easily obtained from $A,b,c$ with no calculation. We also provide an explicit algebraic characterization of the integer hull of the convex polytope $P=\{x\in\R^n\vert … Read more