This paper is the first of a series of two devoted to the polyhedral study of a strongly NP-hard resource-constrained scheduling problem, referred to as the process move programming problem. This problem arises in relation to the operability of certain high-availability real time distributed systems. After a brief introduction to the problem as well as … Read more
This paper is the second of a series of two devoted to the polyhedral study of a strongly NP-hard resource-constrained scheduling problem, referred to as the process move programming problem. In the present paper, we put back into the picture the capacity constraints which were ignored in the first paper. In doing so, we introduce … Read more
We introduce a continuous analogue of the Hirsch conjecture and a discrete analogue of the result of Dedieu, Malajovich and Shub. We prove a continuous analogue of the result of Holt and Klee, namely, we construct a family of polytopes which attain the conjectured order of the largest total curvature. Citation AdvOL-Report #2006/09 Advanced Optimization … Read more
An explicit description of the convex hull of solutions to the uncapacitated lot-sizing problem with backlogging, in its natural space of production, setup, inventory and backlogging variables, has been an open question for many years. In this paper, we identify facet-defining inequalities that subsume all previously known valid inequalities for this problem. We show that … Read more
Perfect graphs constitute a well-studied graph class with a rich structure, reflected by many characterizations w.r.t different concepts. Perfect graphs are, e.g., characterized as precisely those graphs G where the stable set polytope STAB(G) coincides with the clique constraint stable set polytope QSTAB(G). For all imperfect graphs STAB(G) \subset QSTAB(G) holds and, therefore, it is … Read more
While dealing with uncertainty in linear programs, the robust optimization framework proposed by Bertsimas and Sim appears as relevant. In particular, it can readily be extended for integer linear programming. This paper outlines the polyhedral impacts of this robust model for the 0-1 knapsack problem. It shows especially how the classical cover cuts can be … Read more
We introduce orbitopes as the convex hulls of 0/1-matrices that are lexicographically maximal sub ject to a group acting on the columns. Special cases are packing and partitioning orbitopes, which arise from restrictions to matrices with at most or exactly one 1-entry in each row, respectively. The goal of investigating these polytopes is to gain … Read more
Let $G=(V,E)$ be a simple graph on $n$ nodes. We show how to construct a partial subgraph $D$ of the line graph of $G$ satisfying the identity: $\overline \chi(G)+\alpha(D)=n$, where $\overline \chi(G)$ denotes the minimum number of cliques in a clique partition of $G$ and $\alpha(D)$ denotes the maximum size of a stable set of … Read more
In this paper we consider a well known class of valid inequalities for the p-median and the uncapacitated facility location polytopes, the odd cycle inequalities. It is known that their separation problem is polynomially solvable. We give a new polynomial separation algorithm based on a reduction from the original graph. Then, we define a nontrivial … Read more
We further study the effect of odd cycle inequalities in the description of the polytopes associated with the p-median and uncapacitated facility location problems. We show that the obvious integer linear programming formulation together with the odd cycle inequalities completely describe these polytopes for the class of restricted Y-graphs. This extends our results for the … Read more