Invited Session Thu.2.H 0104

Thursday, 13:15 - 14:45 h, Room: H 0104

Cluster 11: Integer & mixed-integer programming [...]

Strong relaxations for stable set and lot sizing


Chair: Jeff Linderoth



Thursday, 13:15 - 13:40 h, Room: H 0104, Talk 1

Monia Giandomenico
An ellipsoidal relaxation for the stable set problem

Coauthors: Adam N. Letchford, Fabrizio Rossi, Stefano Smriglio


A relevant amount of research has been focused on investigating strong relaxations for the stable set problem. In fact, polyhedral combinatorics techniques have been intensively developed since the early seventies in order to strengthen the natural linear formulation. Shortly afterwards, Lovász introduced a celebrated semidefinite programming relaxation, known as theta relaxation. Later on, several attempts to strengthen it by adding linear inequalities have been investigated. The resulting upper bounds turn out to be very strong, but hardly accessible in practice. In this talk, we show that the Lovász theta relaxation can be used to derive a new convex programming relaxation having the same optimal value. Moreover, the new relaxation has a more friendly structure, as its feasible region takes the form of an ellipsoid. We also investigate possible extension of this methodology to stronger relaxations.



Thursday, 13:45 - 14:10 h, Room: H 0104, Talk 2

Fabrizio Rossi
A branch-and-cut for the stable set problem based on an ellipsoidal relaxation

Coauthors: Monia Giandomenico, Adam N. Letchford, Stefano Smriglio


The stable set problem gives rise to difficult integer programs. One major reason is that linear relaxations provide weak bounds (even though at low computational cost), while semidefinite relaxations give good (sometimes excellent) bounds but too demanding to compute. The Lovász theta relaxation seems to provide the right compromise between strength and computational tractability, even if embedding it within an enumeration scheme is not straightforward. In this talk, we
present a new convex programming relaxation having the theta bound as optimal value, whose feasible region takes the form of an ellipsoid. In principle, this allows us to resort to a branch-and-cut algorithm in which each subproblem includes one convex quadratic constraint. However, the ellipsoid can also be used to derive valid inequalities for the stable set polytope: a hyperplane tangent to the ellipsoid can be exploited to generate strong cutting planes by a sequential strengthening procedure. We discuss the performance of the resulting (LP-based) branch-and-cut algorithm through extensive experiments.



Thursday, 14:15 - 14:40 h, Room: H 0104, Talk 3

Laurence Wolsey
The one warehouse multiple retailer problem with start-ups and constant capacities

Coauthors: Mathieu Van Vyve, Hande Yaman


For the uncapacitated OWMR problem with K clients and T periods,
a multi-commodity reformulation solves instances with K,T=100 to optimality. We consider a new relaxation
motivated by the Wagner-Whitin relaxation that is effective for single level problems. The relaxed solution set
X decomposes into X =∩t=1TYt, each set Yt having the same structure, denoted Y.

  1. When K=1 and uncapacitated at warehouse and client, we give a tight and compact extended formulation for conv(Y), an inequality description in the original space, and an O(T) separation algorithm.
  2. A similar result with start-up costs at both levels.
  3. With multiple clients (K>1), the convex hull of Y is essentially the intersection of the convex hulls for each client individually,
    providing an O(KT2) formulation for X and OWMR.
  4. When uncapacitated at the warehouse and constant capacity for each retailer, we give an extended formulation for Y
    that is conjectured to be tight.

For OWMR with start-ups, our formulation improves computationally on the multicommodity formulation, and with capacities it solves to optimality instances with K,T=25.


  Getting Payday Loans In California should be thought of many times. Of course, the choice is not that easy, as there exist great number of different preparations. Notwithstanding, Cialis is the one that definitely differs from all other products.