Dantzig-Wolfe Relaxation

Straddles and the Dantzig–Wolfe Bound of Cardinality-Indexed Knapsack Formulations

Categories (Mixed) Integer Linear Programming, Graphs and Matroids, Polyhedra Tags , , ,

Many integer programs assign indivisible items to capacitated resources, each contributing a knapsack constraint with a setup variable. Cardinality-indexed formulations copy the variables of each resource once for every number of items it may serve; they have been used for generalized assignment, concentrator location, capacitated Steiner arborescence and unsplittable network design. We characterize when their … Read more

On the Exactness of Dantzig-Wolfe Relaxation for Rank Constrained Optimization Problems

Categories Integer Programming Tags , , , , , ,

In the rank-constrained optimization problem (RCOP), it minimizes a linear objective function over a prespecified closed rank-constrained domain set and $m$ generic two-sided linear matrix inequalities. Motivated by the Dantzig-Wolfe (DW) decomposition, a popular approach of solving many nonconvex optimization problems, we investigate the strength of DW relaxation (DWR) of the RCOP, which admits the … Read more