Search

Many practical integer programming problems involve variables with one or two-sided bounds. Dunkel and Schulz (A refined Gomory–Chvatal closure for polytopes in the unit cube, http://www.optimization-online.org/DB_FILE/2012/03/3404.pdf , 2012) considered a strengthened version of Chvatal–Gomory (CG) inequalities that use 0–1 bounds on variables, and showed that the set of points in a rational polytope that satisfy all these strengthened inequalities is a polytope. Recently, we generalized this result by considering strengthened CG inequalities that use all variable bounds. In this paper, we generalize further by considering not just variable bounds, but general linear constraints on variables. We show that all points in a rational polyhedron that satisfy such strengthened CG inequalities form a rational polyhedron. We also extend this polyhedrality result to mixed-integer sets defined by linear constraints.

We propose a dynamic version of the classical node packing problem, also called the stable set or independent set problem. The problem is defined by a node set, a node weight vector, and an edge probability vector. For every pair of nodes, an edge is present or not according to an independent Bernoulli random variable defined by the corresponding entry in the probability vector. At each step, the decision maker selects an available node that maximizes the expected weight of the final packing, and then observes edges adjacent to this node. We formulate the problem as a Markov decision process and show that it is NP-Hard even on star graphs. Next, we introduce relaxations of the problem’s achievable probabilities polytope, analogous to the linear and bilinear edge-based formulations in the deterministic case; we show that these relaxations can be weak, motivating a polyhedral study. We derive classes of valid inequalities arising from cliques, paths, and cycles. For cliques, we completely characterize the polytope and show that it is a submodular polyhedron. For both paths and cycles, we give an implicit representation of the polytope via a cut-generating linear program of polynomial size based on a compact dynamic programming formulation. Our computational results show that our inequalities can greatly reduce the upper bound and improve the linear relaxation’s gap, particularly when the instance’s expected density is high.

The network reconfiguration problem seeks to find a rooted tree $T$ such that the energy of the (unique) feasible electrical flow over $T$ is minimized. The tree requirement on the support of the flow is motivated by operational constraints in electricity distribution networks. The bulk of existing results on convex optimization over vertices of polytopes and on the structure of electrical flows do not easily give guarantees for this problem, while many heuristic methods have been developed in the power systems community as early as 1989. Our main contribution is to give the first provable approximation guarantees for the network reconfiguration problem. We provide novel lower bounds and corresponding approximation factors for various settings ranging from $\min\{O(m-n), O(n)\}$ for general graphs, to $O(\sqrt{n})$ over grids with uniform resistances on edges, and $O(1)$ for grids with uniform edge resistances and demands. To obtain the result for general graphs, we propose a new method for (approximate) spectral graph sparsification, which may be of independent interest. Using insights from our theoretical results, we propose a general heuristic for the network reconfiguration problem that is orders of magnitude faster than existing methods in the literature, while obtaining comparable performance., 37 pages, 11 figures

The Nemhauser-Trotter theorem states that the standard linear programming (LP) formulation for the stable set problem has a remarkable property, also known as (weak) persistency: for every optimal LP solution that assigns integer values to some variables, there exists an optimal integer solution in which these variables retain the same values. While the standard LP is defined by only non-negativity and edge constraints, a variety of other LP formulations have been studied and one may wonder whether any of them has this property as well. We show that any other formulation that satisfies mild conditions cannot have the persistency property on all graphs, unless it is always equal to the stable set polytope., Comment: 17 pages, 6 figures

In this paper, we devise new relaxations for composite functions, which improve the prevalent factorable relaxations, without introducing additional variables, by exploiting the inner-function structure. We outer-approximate inner-functions using arbitrary under- and over-estimators and then convexify the outer-function over a polytope P, which models the ordering relationships between the inner-functions and their estimators and utilizes bound information on the inner-functions as well as on the estimators. We show that there is a subset Q of P, with significantly simpler combinatorial structure, such that the separation problem of the graph of the outer-function over P is polynomially equivalent, via a fast combinatorial algorithm, to that of its graph over Q. We specialize our study to consider the product of two inner-functions with one non-trivial underestimator for each inner-function. For the corresponding polytope P, we show that there are eight valid inequalities besides the four McCormick inequalities, which improve the factorable relaxation. Finally, we show that our results generalize to simultaneous convexification of a vector of outer-functions.

In this paper we present a scaling algorithm for minimizing arbitrary functions over vertices of polytopes in an oracle model of computation which includes an augmentation oracle. For the binary case, when the vertices are 0–1 vectors, we show that the oracle time is polynomial. Also, this algorithm allows us to generalize some concepts of combinatorial optimization concerning performance bounds of greedy algorithms and leads to new bounds for the complexity of the simplex method.

The maximum weighted stable set problem in claw-free graphs is a well-known generalization of the maximum weighted matching problem, and a classical problem in combinatorial optimization. In spite of the recent development of fast(er) combinatorial algorithms and some progresses in the characterization of the corresponding stable set polytope, the problem of “providing a decent linear description” for this polytope (Grotschel et al. in Geometric algorithms and combinatorial optimization, Springer, New York, 1988) is still open. The main contribution of this paper is to propose an algorithmic answer to that question by providing a polynomial-time and computationally attractive separation routine for the stable set polytope of claw-free graphs, that only requires a combinatorial decomposition algorithm, the solution of (moderate sized) compact linear programs, and Padberg and Rao’s algorithm for separating over the matching polytope. In particular, it is a generalization of the latter and avoids the heavy computational burden of resorting to the ellipsoid method, on which the only poly-time separation routine known so far relied. Besides, our separation routine comes with a ‘small’ (but not polynomial) extended linear programming formulation and a procedure to derive a linear description of the stable set polytope of claw-free graphs in the original space.

A celebrated theorem of Balas gives a linear mixed-integer formulation for the union of two nonempty polytopes whose relaxation gives the convex hull of this union. The number of inequalities in Balas formulation is linear in the number of inequalities that describe the two polytopes and the number of variables is doubled. In this paper we show that this is best possible: in every dimension there exist two nonempty polytopes such that if a formulation for the convex hull of their union has a number of inequalities that is polynomial in the number of inequalities that describe the two polytopes, then the number of additional variables is at least linear in the dimension of the polytopes. We then show that this result essentially carries over if one wants to approximate the convex hull of the union of two polytopes and also in the more restrictive setting of lift-and-project.

We study the following problem: given a rational polytope with Chvatal rank 1, does it contain an integer point? Boyd and Pulleyblank observed that this problem is in the complexity class NP $$\cap $$ co-NP, an indication that it is probably not NP-complete. It is open whether there is a polynomial time algorithm to solve the problem, and we give several special classes where this is indeed the case. We show that any compact convex set whose Chvatal closure is empty has an integer width of at most n, and we give an example showing that this bound is tight within an additive constant of 1. This determines the time complexity of a Lenstra-type algorithm. However, the promise that a polytope has Chvatal rank 1 seems hard to verify. We prove that deciding emptiness of the Chvatal closure of a rational polytope given by its linear description is NP-complete, even when the polytope is contained in the unit hypercube or is a rational simplex and it does not contain any integer point.

This is mostly a survey on some mathematical results concerning volumes of polytopes of interest in non-convex optimization. Our motivation is in geometrically comparing relaxations in the context of mixed-integer linear and nonlinear optimization, with the goal of gaining algorithmic and modeling insights. We consider relaxations of: fixed-charge formulations, vertex packing polytopes, boolean-quadric polytopes, and relaxations of graphs of monomials on box domains. Besides surveying the area, we do give a few new results, and we provide many directions for further work.

There is often a significant trade-off between formulation strength and size in mixed integer programming (MIP). When modelling convex disjunctive constraints (e.g. unions of convex sets) this trade-off can be resolved by adding auxiliary continuous variables. However, adding these variables can result in a deterioration of the computational effectiveness of the formulation. For this reason, there has been considerable interest in constructing strong formulations that do not use continuous auxiliary variables. We introduce a technique to construct formulations without these detrimental continuous auxiliary variables. To develop this technique we introduce a natural nonpolyhedral generalization of the Cayley embedding of a family of polytopes and show it inherits many geometric properties of the original embedding. We then show how the associated formulation technique can be used to construct small and strong formulation for a wide range of disjunctive constraints. In particular, we show it can recover and generalize all known strong formulations without continuous auxiliary variables., National Science Foundation (U.S.) (grant CMMI-1351619)

This paper investigates a polyhedral approach to handle symmetries in mixed-binary programs. We study symretopes, i.e., the convex hulls of all binary vectors that are lexicographically maximal in their orbit with respect to the symmetry group. These polytopes turn out to be quite complex. For practical use, we therefore develop an integer programming formulation with ternary coefficients, based on knapsack polytopes arising from a single lexicographic order enforcing inequality. We show that for these polytopes, the optimization as well as the separation problem of minimal cover inequalities can be solved in almost linear time. We demonstrate the usefulness of this approach by computational experiments, showing that it is competitive with state-of-the-art methods and is considerably faster for specific problem classes.

Even and odd pairs are important tools in the study of perfect graphs and were instrumental in the proof of the Strong Perfect Graph Theorem. We suggest that such pairs impose a lot of structure also in arbitrary, not just perfect graphs. To this end, we show that the presence of even or odd pairs in graphs imply a special structure of the stable set polytope. In fact, we give a polyhedral characterization of even and odd pairs.

We consider the Multilinear set $${\mathcal {S}}$$ defined as the set of binary points (x, y) satisfying a collection of multilinear equations of the form $$y_I = \prod _{i \in I} x_i$$ , $$I \in {\mathcal {I}}$$ , where $${\mathcal {I}}$$ denotes a family of subsets of $$\{1,\ldots , n\}$$ of cardinality at least two. Such sets appear in factorable reformulations of many types of nonconvex optimization problems, including binary polynomial optimization. A great simplification in studying the facial structure of the convex hull of the Multilinear set is possible when $${\mathcal {S}}$$ is decomposable into simpler Multilinear sets $${\mathcal {S}}_j$$ , $$j \in J$$ ; namely, the convex hull of $${\mathcal {S}}$$ can be obtained by convexifying each $${\mathcal {S}}_j$$ , separately. In this paper, we study the decomposability properties of Multilinear sets. Utilizing an equivalent hypergraph representation for Multilinear sets, we derive necessary and sufficient conditions under which $${\mathcal {S}}$$ is decomposable into $${\mathcal {S}}_j$$ , $$j \in J$$ , based on the structure of pair-wise intersection hypergraphs. Our characterizations unify and extend the existing decomposability results for the Boolean quadric polytope. Finally, we propose a polynomial-time algorithm to optimally decompose a Multilinear set into simpler subsets. Our proposed algorithm can be easily incorporated in branch-and-cut based global solvers as a preprocessing step for cut generation.

In many network applications, one searches for a connected subset of vertices that exhibits other desirable properties. To this end, this paper studies the connected subgraph polytope of a graph, which is the convex hull of subsets of vertices that induce a connected subgraph. Much of our work is devoted to the study of two nontrivial classes of valid inequalities. The first are the a, b-separator inequalities, which have been successfully used to enforce connectivity in previous computational studies. The second are the indegree inequalities, which have previously been shown to induce all nontrivial facets for trees. We determine the precise conditions under which these inequalities induce facets and when each class fully describes the connected subgraph polytope. Both classes of inequalities can be separated in polynomial time and admit compact extended formulations. However, while the a, b-separator inequalities can be lifted in linear time, it is NP-hard to lift the indegree inequalities.

We introduce a strong extended formulation of the convex recoloring problem on a tree, which has an application in analyzing phylogenetic trees. The extended formulation has only a polynomial number of constraints, but dominates the conventional formulation and the exponentially many valid inequalities introduced by Campelo et al. (Math Progr 156:303–330, 2016). We show that all valid inequalities introduced by Campelo et al. can be derived from the extended formulation. We also show that the natural restriction of the extended formulation provides a complete inequality description of the polytope of subtrees of a tree. The solution time using the extended formulation is much smaller than that with the conventional formulation. Moreover the extended formulation solves all the problem instances attempted in Campelo et al. (2016) and larger sized instances at the root node of the branch-and-bound tree without branching.

We show that the complexity of computing the second order moment bound on the expected optimal value of a mixed integer linear program with a random objective coefficient vector is closely related to the complexity of characterizing the convex hull of the points $$\{{1 \atopwithdelims (){\varvec{x}}}{1 \atopwithdelims (){\varvec{x}}}' \ | \ {\varvec{x}} \in {\mathcal {X}}\}$${1x1xź|xźX} where $${\mathcal {X}}$$X is the feasible region. In fact, we can replace the completely positive programming formulation for the moment bound on $${\mathcal {X}}$$X, with an associated semidefinite program, provided we have a linear or a semidefinite representation of this convex hull. As an application of the result, we identify a new polynomial time solvable semidefinite relaxation of the distributionally robust multi-item newsvendor problem by exploiting results from the Boolean quadric polytope. For $${\mathcal {X}}$$X described explicitly by a finite set of points, our formulation leads to a reduction in the size of the semidefinite program. We illustrate the usefulness of the reduced semidefinite programming bounds in estimating the expected range of random variables with two applications arising in random walks and best---worst choice models.

As renewable energy penetration rates continue to increase in power systems worldwide, new challenges arise for system operators in both regulated and deregulated electricity markets to solve the security-constrained coal-fired unit commitment problem with intermittent generation (due to renewables) and uncertain load, in order to ensure system reliability and maintain cost effectiveness. In this paper, we study a security-constrained coal-fired stochastic unit commitment model, which we use to enhance the reliability unit commitment process for day-ahead power system operations. In our approach, we first develop a deterministic equivalent formulation for the problem, which leads to a large-scale mixed-integer linear program. Then, we verify that the turn on/off inequalities provide a convex hull representation of the minimum-up/down time polytope under the stochastic setting. Next, we develop several families of strong valid inequalities mainly through lifting schemes. In particular, by exploring sequence independent lifting and subadditive approximation lifting properties for the lifting schemes, we obtain strong valid inequalities for the ramping and general load balance polytopes. Finally, branch-and-cut algorithms are developed to employ these valid inequalities as cutting planes to solve the problem. Our computational results verify the effectiveness of the proposed approach.

In this paper we give an exponential lower bound for Cunningham's least recently considered (round-robin) rule as applied to parity games, Markov decision processes and linear programs. This improves a recent subexponential bound of Friedmann for this rule on these problems. The round-robin rule fixes a cyclical order of the variables and chooses the next pivot variable starting from the previously chosen variable and proceeding in the given circular order. It is perhaps the simplest example from the class of history-based pivot rules. Our results are based on a new lower bound construction for parity games. Due to the nature of the construction we are also able to obtain an exponential lower bound for the round-robin rule applied to acyclic unique sink orientations of hypercubes (AUSOs). Furthermore these AUSOs are realizable as polytopes. We believe these are the first such results for history based rules for AUSOs, realizable or not. The paper is self-contained and requires no previous knowledge of parity games.

We show the existence of a polynomial-size extended formulation for the base polytope of a $(k,\ell)$-sparsity matroid. For an undirected graph $G=(V,E)$, the size of the formulation is $O(|V||E|)$ when $k \geq \ell$ and $O(|V|^2 |E|)$ when $k \leq \ell$. To this end, we employ the technique developed by Faenza et al. recently that uses a randomized communication protocol., Comment: 10 pages

In this paper, we study how well one can approximate arbitrary polytopes using sparse inequalities. Our motivation comes from the use of sparse cutting-planes in mixed-integer programing (MIP) solvers, since they help in solving the linear programs encountered during branch-&-bound more efficiently. However, how well can we approximate the integer hull by just using sparse cutting-planes? In order to understand this question better, given a polyope $$P$$P (e.g. the integer hull of a MIP), let $$P^k$$Pk be its best approximation using cuts with at most k non-zero coefficients. We consider $${\text {d}}(P, P^k) = \max _{x \in P^k} \left( \min _{y \in P} \Vert x - y\Vert \right) $$d(P,Pk)=maxx?Pkminy?P?x-y? as a measure of the quality of sparse cuts.In our first result, we present general upper bounds on $${\text {d}}(P, P^k)$$d(P,Pk) which depend on the number of vertices in the polytope. Our bounds imply that if $$P$$P has polynomially many vertices, using half sparsity already approximates it very well. Second, we present a lower bound on $${\text {d}}(P, P^k)$$d(P,Pk) for random polytopes that show that the upper bounds are quite tight. Third, we show that for a class of hard packing IPs, sparse cutting-planes do not approximate the integer hull well, that is $$d(P, P^k)$$d(P,Pk) is large for such instances unless k is very close to n. Finally, we show that using sparse cutting-planes in extended formulations is at least as good as using them in the original polyhedron, and give an example where the former is actually much better.

We give strong formulations of ramping constraints--used to model the maximum change in production level for a generator or machine from one time period to the next--and production limits. For the two-period case, we give a complete description of the convex hull of the feasible solutions. The two-period inequalities can be readily used to strengthen ramping formulations without the need for separation. For the general case, we define exponential classes of multi-period variable upper bound and multi-period ramping inequalities, and give conditions under which these inequalities define facets of ramping polyhedra. Finally, we present exact polynomial separation algorithms for the inequalities and report computational experiments on using them in a branch-and-cut algorithm to solve unit commitment problems in power generation.

We introduce the simple extension complexity of a polytope P as the smallest number of facets of any simple (i.e., non-degenerate in the sense of linear programming) polytope which can be projected onto P. We devise a combinatorial method to establish lower bounds on the simple extension complexity and show for several polytopes that they have large simple extension complexities. These examples include both the spanning tree and the perfect matching polytopes of complete graphs, uncapacitated flow polytopes for non-trivially decomposable directed acyclic graphs, hypersimplices, and random 0/1-polytopes with vertex numbers within a certain range. On our way to obtain the result on perfect matching polytopes we generalize a result of Padberg and Rao's on the adjacency structures of those polytopes. To complement the lower bounding techniques we characterize in which cases known construction techniques yield simple extensions., 28 pages, 13 figures. Accepted for publication in a special issue on IPCO 2014 of the journal Mathematical Programming (Series B), to appear 2015

An extended formulation of a polytope is a linear description of this polytope using extra variables besides the variables in which the polytope is defined. The interest of extended formulations is due to the fact that many interesting polytopes have extended formulations with a lot fewer inequalities than any linear description in the original space. This motivates the development of methods for, on the one hand, constructing extended formulations and, on the other hand, proving lower bounds on the sizes of extended formulations. Network flows are a central paradigm in discrete optimization, and are widely used to design extended formulations. We prove exponential lower bounds on the sizes of uncapacitated flow-based extended formulations of several polytopes, such as the (bipartite and non-bipartite) perfect matching polytope and TSP polytope. We also give new examples of flow-based extended formulations, e.g., for 0/1-polytopes defined from regular languages. Finally, we state a few open problems.

Let X be the set of integer points in some polyhedron. We investigate the smallest number of facets of any polyhedron whose set of integer points is X. This quantity, which we call the relaxation complexity of X, corresponds to the smallest number of linear inequalities of any integer program having X as the set of feasible solutions that does not use auxiliary variables. We show that the use of auxiliary variables is essential for constructing polynomial size integer programming formulations in many relevant cases. In particular, we provide asymptotically tight exponential lower bounds on the relaxation complexity of the integer points of several well-known combinatorial polytopes, including the traveling salesman polytope and the spanning tree polytope., 17 pages, accepted for publication in Math. Program. (Ser. B): Special issue on IPCO 2014

The tropical arithmetic operations on $$\mathbb {R}$$R, defined as $$\oplus :(a,b)\rightarrow \min \{a,b\}$$?:(a,b)?min{a,b} and $$\otimes :(a,b)\rightarrow a+b$$?:(a,b)?a+b, arise from studying the geometry over non-Archimedean fields. We present an application of tropical methods to the study of extended formulations for convex polytopes. We propose a non-Archimedean generalization of the well known Boolean rank bound for the extension complexity. We show how to construct a real polytope with the same extension complexity and combinatorial type as a given non-Archimedean polytope. Our results allow us to develop a method of constructing real polytopes with large extension complexity.

Padberg (Math Program 137:593---599, 2013) introduced a geometric notion of ranks for (mixed) integer rational polyhedrons and conjectured that the geometric rank of the matching polytope is one. In this work, we prove that this conjecture is true.

An extended formulation of a polyhedron $$P$$P is a linear description of a polyhedron $$Q$$Q together with a linear map $$\pi $$? such that $$\pi (Q)=P$$?(Q)=P. These objects are of fundamental importance in polyhedral combinatorics and optimization theory, and the subject of a number of studies. Yannakakis' factorization theorem (Yannakakis in J Comput Syst Sci 43(3):441---466, 1991) provides a surprising connection between extended formulations and communication complexity, showing that the smallest size of an extended formulation of $$P$$P equals the nonnegative rank of its slack matrix $$S$$S. Moreover, Yannakakis also shows that the nonnegative rank of $$S$$S is at most $$2^c$$2c, where $$c$$c is the complexity of any deterministic protocol computing $$S$$S. In this paper, we show that the latter result can be strengthened when we allow protocols to be randomized. In particular, we prove that the base-$$2$$2 logarithm of the nonnegative rank of any nonnegative matrix equals the minimum complexity of a randomized communication protocol computing the matrix in expectation. Using Yannakakis' factorization theorem, this implies that the base-$$2$$2 logarithm of the smallest size of an extended formulation of a polytope $$P$$P equals the minimum complexity of a randomized communication protocol computing the slack matrix of $$P$$P in expectation. We show that allowing randomization in the protocol can be crucial for obtaining small extended formulations. Specifically, we prove that for the spanning tree and perfect matching polytopes, small variance in the protocol forces large size in the extended formulation.

We introduce a concept of dual consistency of systems of linear inequalities with full generality. We show that a cardinality constrained polytope is represented by a certain system of linear inequalities if and only if the systems of linear inequalities associated with the cardinalities are dual consistent. Typical dual consistent systems of inequalities are those which describe polymatroids, generalized polymatroids, and dual greedy polyhedra with certain choice functions. We show that the systems of inequalities for cardinality-constrained ordinary bipartite matching polytopes are not dual consistent in general, and give additional inequalities to make them dual consistent. Moreover, we show that ordinary systems of inequalities for the cardinality-constrained (poly)matroid intersection are not dual consistent, which disproves a conjecture of Maurras, Spiegelberg, and Stephan about a linear representation of the cardinality-constrained polymatroid intersection.

expressing the simple condition that two adjacent nodes cannot belong to a stable set. We study the fractional stable set polytope, i.e. the polytope defined by the linear relaxation of the edge formulation. Even if this polytope is a weak approximation of the stable set polytope, its simple geometrical structure provides deep theoretical insight as well as interesting algorithmic opportunities. Exploiting a graphic characterization of the bases, we first redefine pivots in terms of simple graphic operations, that turn a given basis into an adjacent one. These results lead us to prove that the combinatorial diameter of the fractional stable set polytope is at most the number of nodes of the given graph. As a corollary, the Hirsch bound holds for this class of polytopes., Mathematical Programming, 147 (1-2), ISSN:0025-5610, ISSN:1436-4646

This special issue is dedicated to the geometry and complexity of lifts or extended formulations of convex sets which has been an active area of research in recent years. This developing field lies at the intersection of several areas such as convex geometry, polyhedral theory, real algebraic geometry, combinatorics, optimization, and computer science, among others. The idea of finding efficient representations of convex sets (especially polytopes) by expressing them as projections of simple convex sets in higher dimensions is not new and is well-known in areas such as integer programming and real algebraic geometry. The current view of the topic is inspired by the 1991 paper of Mihalis Yannakakis who showed that the matching polytope does not admit a small “symmetric” polyhedral lift, in striking contrast to the classical result of Jack Edmonds that linear optimization over the matching polytope is possible in polynomial time. Yannakakis also showed that there is a precise connection between the nonnegative rank of the slack matrix of a polytope and the size of the smallest polyhedral lift that is possible for this polytope. Both of these results have been extended in multiple directions in recent papers. The restrictions imposed by symmetry on the size of lifts has been explored in multiple papers by now. Also, the connection between lifts and nonnegative ranks have been extended to general convex sets and closed cones. In particular, positive semidefinite lifts of polytopes have received a fair bit of attention lately, while the older notion of