Search

We present the first exact approach to separate tight metric inequalities for the Network Loading problem. We give a bilevel programming formulation for the separation problem, develop an algorithm based on the proposed formulation and discuss computational results.

We prove several complexity results about the gap inequalities for the max-cut problem, including (i) the gap- 1 inequalities do not imply the other gap inequalities, unless NP = Co NP ; (ii) there must exist non-redundant gap inequalities with exponentially large coefficients, unless NP = Co NP ; (iii) the associated separation problem can be solved in finite (doubly exponential) time.

Given a graph G=(V,E) with edge costs and an integer vector [email protected]?Z"+^V associated with the nodes of V, the survivable network design problem is to find a minimum cost subgraph of G such that between every pair of nodes s,t of V, there are at least min{r(s),r(t)} edge-disjoint paths. In this paper we consider that problem when [email protected]?{1,2}^V. This case is of particular interest to the telecommunication industry. We show that the separation problem for the so-called partition inequalities reduces to minimizing a submodular function. This yields a polynomial time separation algorithm for these inequalities in that case.

Crowder et al. (Oper. Res. 31 (1983) 803-834) conjectured that the separation problem for cover inequalities for binary integer programs is polynomially solvable. We show that the general problem is NP-hard but a special case is solvable in linear time.