Closures

Aggregated quadratic formulations and semidefinite relaxations of the stable set polytope

Categories Combinatorial Optimization, Semi-definite Programming Tags , , ,

The stable set problem admits various binary linear and quadratic formulations. The Shor relaxation of a particular quadratic formulation is the well-known theta body. We consider aggregations of quadratic constraints of this formulation, yielding exact and inexact quadratic formulations of the stable set problem, and then establish conditions under which the aggregated quadratic formulation is … Read more

On Multi-Disjunctive Valid Inequalities for Chance-Constrained Stochastic Problems with Finite Support

Categories (Mixed) Integer Linear Programming, Stochastic Programming Tags , , , ,

We consider mixed-integer linear chance-constrained problems for which the random vector that parameterizes the feasible region has finite support. Our key objective is to improve branch-and-bound or -cut approaches by introducing new types of valid inequalities that improve the dual bound and, by this, the overall performance of such methods. We introduce so-called multi-disjunctive valid … Read more