The topic of this paper are integer programming models in which a subset of 0/1-variables encode a partitioning of a set of objects into disjoint subsets. Such models can be surprisingly hard to solve by branch-and-cut algorithms if the permutation of the subsets of the partition is irrelevant. This kind of symmetry unnecessarily blows up … Read more
We prove that cutting-plane proofs which use split cuts have exponential length in the worst case. Split cuts, defined by Cook, Kannan, Schrijver (1993), are known to be equivalent to a number of other classes of cuts, namely mixed-integer rounding (MIR) cuts, Gomory mixed-integer cuts, and disjunctive cuts. Our result thus implies the exponential worst-case … Read more
The aim of this paper is to study how efficiently we evaluate a system of multivariate polynomials and their partial derivatives in homotopy continuation methods. Our major tool is an extension of the Hornor scheme, which is popular in evaluating a univariate polynomial, to a multivariate polynomial. But the extension is not unique, and there … Read more
This paper is devoted to the study of the reroute sequence planning problem in multi-protocol label switching networks from the polyhedral viewpoint. The reroute sequence plan polytope, defined as the convex hull of the incidence vectors of the reroute sequences which do not violate the network link capacities, is introduced and some of its properties … Read more
This paper is devoted to the exact resolution of a strongly NP-hard resource-constrained scheduling problem, the Process Move Programming problem, which arises in relation to the operability of certain high availability real time distributed systems. Based on the study of the polytope defined as the convex hull of the incidence vectors of the admissible process … Read more
The polyhedral homotopy method, which has been known as a powerful numerical method for computing all isolated zeros of a polynomial system, requires all mixed cells of the support of the system to construct a family of homotopy functions. Finding the mixed cells is formulated in terms of a linear inequality system with an additional … Read more
We consider two (0,1)-linear programming formulations of the graph (vertex-)coloring problem, in which variables are associated to stable sets of the input graph. The first one is a set covering formulation, where the set of vertices has to be covered by a minimum number of stable sets. The second is a set packing formulation, in … Read more
We address a multi-item capacitated lot-sizing problem with setup times and shortage costs that arises in real-world production planning problems. Demand cannot be backlogged, but can be totally or partially lost. The problem is NP-hard. A mixed integer mathematical formulation is presented. Our approach in this paper is to propose some classes of valid inequalities … Read more
Given a complete graph K = (V , E), with edge weight ce on each edge, we consider the problem of partitioning the vertices of graph K into subcliques that each have at least S vertices, so as to minimize the total weight of the edges that have both endpoints in the same subclique. It … Read more
The sports team realignment problem can be modelled as $k$-way equipartition: given a complete graph $K_{n}=(V,E)$, with edge weight $c_{e}$ on each edge, partition the vertices $V$ into $k$ divisions that have exactly $S$ vertices, so as to minimize the total weight of the edges that have both endpoints in the same division. In this … Read more