Extended formulations in combinatorial optimization

This survey is concerned with the size of perfect formulations for combinatorial optimization problems. By “perfect formulation”, we mean a system of linear inequalities that describes the convex hull of feasible solutions, viewed as vectors. Natural perfect formulations often have a number of inequalities that is exponential in the size of the data needed to describe the problem. Here we are particularly interested in situations where the addition of a polynomial number of extra variables allows a formulation with a polynomial number of inequalities. Such formulations are called “compact extended formulations”. We survey various tools for deriving and studying extended formulations, such as Fourier’s procedure for projection, Minkowski-Weyl’s theorem, Balas’ theorem for the union of polyhedra, Yannakakis’ theorem on the size of an extended formulation, dynamic programming, and variable discretization. For each tool that we introduce, we present one or several examples of how this tool is applied. In particular, we present compact extended formulations for several graph problems involving cuts, trees, cycles and matchings, and for the mixing set, and we present the proof of Fiorini, Massar, Pokutta, Tiwary and de Wolf of an exponential lower bound for the cut polytope. We also present Bienstock’s approximate compact extended formulation for the knapsack problem, Goemans’ result on the size of an extended formulation for the permutahedron, and the Faenza-Kaibel extended formulation for orbitopes.     

Bulk-Robust combinatorial optimization

Mathematical Programming - We commence an algorithmic study of Bulk-Robustness, a new model of robustness in combinatorial optimization. Unlike most existing models, Bulk-Robust combinatorial...     

Extended formulations for radial cones

This paper studies extended formulations for radial cones at vertices of polyhedra, which are the polyhedra defined by the constraints that are active at the vertex. While the perfect-matching polytope cannot be described by subexponential-size extended formulations (Rothvoß 2014), Ventura & Eisenbrand (2003) showed that its radial cones can be described by polynomial-size extended formulations. The authors also asked whether this extends to odd-cut polyhedra, which are related to matching polyhedra by polarity. We answer this question negatively.     

Extended formulations for convex heptagons

Results related to extended formulations for convex polygons are discussed. In particular, it turns out that six linear inequalities are sufficient to describe a convex heptagon up to linear projection.     

Parallel computing in combinatorial optimization

This is a review of the literature on parallel computers and algorithms that is relevant for combinatorial optimization. We start by describing theoretical as well as realistic machine models for parallel computations. Next, we deal with the complexity theory for parallel computations and illustrate the resulting concepts by presenting a number of polylog parallel algorithms andP-completeness results. Finally, we discuss the use of parallelism in enumerative methods.     

Semidefinite programming in combinatorial optimization

We discuss the use of semidefinite programming for combinatorial optimization problems. The main topics covered include (i) the Lovász theta function and its applications to stable sets, perfect graphs, and coding theory, (ii) the automatic generation of strong valid inequalities, (iii) the maximum cut problem and related problems, and (iv) the embedding of finite metric spaces and its relationship to the sparsest cut problem. Part of this work is supported by NSF contract 9623859-CCR, a Sloan Foundation Fellowship, and ARPA Contract N00014-95-1-1246.     

Inverse multi-objective combinatorial optimization

Inverse multi-objective combinatorial optimization consists of finding a minimal adjustment of the objective functions coefficients such that a given set of feasible solutions becomes efficient. An algorithm is proposed for rendering a given feasible solution into an efficient one. This is a simplified version of the inverse problem when the cardinality of the set is equal to one. The adjustment is measured by the Chebyshev distance. It is shown how to build an optimal adjustment in linear time based on this distance, and why it is right to perform a binary search for determining the optimal distance. These results led us to develop an approach based on the resolution of mixed-integer linear programs. A second approach based on a branch-and-bound is proposed to handle any distance function that can be linearized. Finally, the initial inverse problem is solved by a cutting plane algorithm.     

Extended formulations for stochastic lot-sizing problems

In this paper, extended formulations for stochastic uncapacitated lot-sizing problems with and without backlogging are developed in higher dimensional spaces that provide integral solutions. Moreover, physical meanings of the decision variables in the extended formulations are explored and special cases with more efficient formulations are studied.     

Extended formulations for the A-cut problem

LetG=(V, E) be an undirected graph andA⊆V. We consider the problem of finding a minimum cost set of edges whose deletion separates every pair of nodes inA. We consider two extended formulations using both node and edge variables. An edge variable formulation has previously been considered for this problem (Chopra and Rao (1991), Cunningham (1991)). We show that the LP-relaxations of the extended formulations are stronger than the LP-relaxation of the edge variable formulation (even with an extra class of valid inequalities added). This is interesting because, while the LP-relaxations of the extended formulations can be solved in polynomial time, the LP-relaxation of the edge variable formulation cannot. We also give a class of valid inequalities for one of the extended formulations. Computational results using the extended formulations are performed.     

Extended formulations for Gomory Corner polyhedra

We present several types of extended formulations for integer programs, based on irreducible integer solutions to Gomory's group relaxations. We present algorithmic schemes based on an iterative reformulation technique using these extended formulations. We give computational results for benchmark problems, which illustrate the primal and dual effect of the reformulation.     

Algorithmic extremal problems in combinatorial optimization

An efficient approximation algorithm generator for the generalized maximum ψ-satisfiability problem is presented which produces an efficient approximation algorithm ψ-MAXMEAN¹ for each finite set ψ of relations. The algorithms ψ-MAXMEAN¹ are shown to be best-possible in the class of polynomial algorithms (if P ≠ NP), in both absolute and relative terms. The algorithms are of wide applicability, because of the central position of the generalized maximum satisfiability problem among the class of combinatorial optimization problems.     

Adaptive stability in combinatorial optimization problems

We consider a general approach to the construction of necessary, sufficient, and necessary and sufficient conditions that allow to ‘adapt’ a known optimal solution of an abstract combinatorial problem with a certain structure to a change in the initial data set for a fixed cost function ‘easily’ from the combinatorial point of view. We call this approach adaptive stability. Apparently, it is the first time that the approach is described for an abstract problem in a rigorous mathematical formalization.