Multi-linear functions appear in many global optimization problems, including reformulated quadratic and polynomial optimization problems. There is a extended formulation for the convex hull of the graph of a multi-linear function that requires the use of an exponential number of variables. Relying on this result, we study an approach that generates relaxations for multiple terms simultaneously, as opposed to methods that relax the nonconvexity of each term individually. In some special cases, we are able to establish analytic bounds on the ratio of the strength of the term-by-term and convex hull relaxations. To our knowledge, these are the first approximation-ratio results for the strength of relaxations of global optimization problems. The results lend insight into the design of practical (non-exponentially sized) relaxations. Computations demonstrate that the bounds obtained in this manner are competitive with the well-known semi-definite programming based bounds for these problems.

I will present a geometric principle that implies a polynomial-time algorithm to minimize a two-dimensional convex function over the integers.

Invex functions offer global optimality guarantees by generalizing the concept of convexity. We propose an introduction on invex relaxations in integer programming. While second order cone formulations fail to model unbounded disjunctions, invex functions represent a powerful alternative modeling tool. Such functions can also be used for generating integer feasible points to large MIPs. Numerical experiments on facility location problems will be presented.

This paper introduces LocalSolver, a black-box local-search solver for general 0-1 programming. This software allows OR practitioners to focus on the modeling of the problem using a simple formalism, and then to defer its actual resolution to a solver based on effcient and reliable local-search techniques. Started in 2007, the goal of the LocalSolver project is to offer a model-and-run approach to combinatorial optimization problems which are out of reach of existing black-box tree-search solvers (integer or constraint programming). Having outlined the modeling formalism and the main technical features behind LocalSolver, its effectiveness is demonstrated through an extensive computational study. The version 1.1 of LocalSolver can be freely downloaded at http://www.localsolver.com and used for educational, research, or commercial purposes. A commercial 2.0 version able to tackle 0-1 programs with 10 millions of variables is planned for early 2012.

The first exact approach for separating the tight metric inequalities for the Network Loading problem is presented. A bilevel programming formulation for the separation problem is given and a corresponding separation algorithm is developed.

In recent years, branch-and-cut algorithms have become firmly established as the most effective method for solving generic mixed integer linear programs (MILPs). Methods for automatically generating inequalities valid for the convex hull of solutions to such MILPs are a critical element of branch-and-cut. This paper examines the nature of the so-called separation problem, which is that of generating a valid inequality violated by a given real vector, usually arising as the solution to a relaxation of the original problem. We show that the problem of generating a maximally violated valid inequality often has a natural interpretation as a bilevel program. In some cases, this bilevel program can be easily reformulated as a single-level mathematical program, yielding a standard mathematical programming formulation for the separation problem. In other cases, no reformulation exists. We illustrate the principle by considering the separation problem for two well-known classes of valid inequalities.

In this paper we derive strong linear inequalities for sets of the form {(x, q) \in Rd \times R : q \geq Q(x), x \in Rd - int(P)}, where Q(x) : Rd \rightarrow R is a quadratic function, P \subset Rd and "int" denotes interior. Of particular but not exclusive interest is the case where P denotes a closed convex set. In this paper, we present several cases where it is possible to characterize the convex hull by efficiently separable linear inequalities.

A set is mixed-integer representable if it is the projection of a mixed-integer linear set. We give geometric conditions that characterize the mixed-integer representable sets. This extends a result of Jeroslow.

Dynamic optimization problems are widely studied in many areas of mathematics and control theory. However, relatively little is known about dynamic counterparts of purely combinatorial problems, except for specific structures such as network flows and scheduling problems. In this talk, we will introduce a general setting for over-time versions of combinatorial optimization problems, and provide a complexity study that includes a widely applicable oracle-based approximation algorithm. In a combinatorial problem P we are given a groundset A and a collection X of its subsets, and we are asked to find a solution S in X that maximizes some given linear weight function. Given a time window W = {1,...,T} and durations t_a for each a in A, in the temporal extension of P we are interested in solutions over time that maximize some given linear weight function. We define a solution over time as a collection of static solutions St in X, one for each t in W, with the following property: For each groundset element a in A, the set of time points {t in W : a in St} at which a is selected is a disjoint union of intervals of length t_a. Informally, each element a can be selected any number of times within the time window W, but only in "groups" of duration t_a. Our main result is an alpha-beta-approximation algorithm, with alpha=1.691030, for the rather general case in which (A,X) is an independence system and P admits a beta-approximation algorithm. This algorithm considerably generalizes the alpha-approximation total-value heuristic by Kohli and Krishnamurti (1992) for integer knapsack, which turns out to be a special case of dynamic optimization problem. We discuss the connection to the integer knapsack and mention applications to scheduling and orthogonal rectangle packing.

We consider two important deterministic inventory control problems: the One-Warehouse Multi-Retailer (OWMR) problem and its special case the Joint Replenishment Problem (JRP). Namely we want to optimize the distribution of a single item over a network composed of one warehouse and N different retailers over a discrete finite planning horizon of T periods. Each retailer is facing deterministic demands that have to be fulfilled on time by ordering those units from the warehouse, which in turn have to be ordered from an external supplier of infinite capacity. The objective of the OWMR problem is to find a planning for the orders at each location (i.e. period and quantity) that minimizes the sum of the fixed ordering costs and holding costs in the system. The cost of ordering is ?xed, independent of the number of products, while a per-unit holding cost is paid at each location to keep an item in stock. This problem is NP-hard but efficient 1.8- and 2-approximation algorithms have been proposed in the literature. The corresponding algorithms are based on sophisticated LP techniques (randomized rounding and primal dual). In this talk we present a simple 2-approximation algorithm that is purely combinatorial and that can be implemented to run in linear time. While we do not match the best known 1.8-approximation guarantee, we believe however that the simplicity of the method and its computational complexity make it both a valuable theoretical approach and a practical tool.

Spare parts for cars are stored in hierarchical warehouse networks. Maintaining optimal inventories for all individual warehouses is usually not optimal for the whole network. We give a short overview of existing paradigms and present the new stochastic guaranteed service model SGSM. The SGSM is a stochastic enhancement of the classical guaranteed service model GSM that accounts for emergency actions like sending parts by a courier service under unusually high demand – situations that are not covered by the GSM. Joint work with Konrad Schade, who received his PhD. for this at the University of Bayreuth and works now for Volkswagen AG.

In this talk we study a variant of makespan-minimizing flexible job shop scheduling with work centers (FJc) that is motivated by an application to rail car maintenance. The crucial difference to standard FJc where a work center consists of parallel machines is that in our variant the machines of a work center are located sequentially along a line (rail track). In this case, a machine could be blocked although it is not processing an operation (maintenance step for a rail car). This happens if a rail car can not reach or leave this machine due to other rail cars on the same track. In particular, we reveal the computational complexity of the problem, we introduce a mixed integer linear programming model, and we present solution methods (heuristical and exact). The exact method is a Branch&Bound-implementation where the dual and primal bounds are generated combinatorially by longest paths. We exploit the fact that we may discard schedules that do not satisfy a particular structure without losing optimality. At the end of the talk, we discuss computational results for several data sets. In particular, we compare the quality of our results with those obtained with the commercial solvers CPLEX and Gurobi.

We consider a robust network design problem in which optimum integral capacities need to be installed on the edges of a network such that the supplies and demands in each of the explicitly known traffic scenarios are satisfied by a single-commodity flow. In Buchheim et al. (LNCS 6701, 7 - 17 (2011)), an integer-programming (IP) formulation of polynomial size was given that uses both flow and capacity variables. In this work, we introduce an IP formulation that only uses capacity variables and exponentially many constraints that can be separated in polynomial time. We argue that the latter formulation has advantageous features when used within branch and cut and evaluate preliminary computational results for the bounds in the root node. We introduce a class of instances that is difficult for IP-based solution approaches. We design and implement a heuristic solution approach based on the definition and exploration of large neighborhoods of carefully selected size. The per- formance of the heuristic is evaluated on the difficult class of instances.

We explore implementation aspects of the recently proposed new cut generation paradigm which can be used to obtain in a non-recursive fashion deep cutting planes that would require several iterations of a standard cut generating procedure.

(Joint work with Egon Balas and Francois Margot) We study the recent generalized intersection cut generating paradigm introduced in Balas and Margot (2011). A major component of this paradigm involves intersecting edges of a non-conic polyhedron with the boundary of a lattice-free convex set to generate intersection points. The standard implementation of this method can lead to an exponential number of intersection points, and is computationally expensive. We introduce a polynomial time algorithm to generate generalized intersection cuts that overcomes the above issue. Preliminary computational results are also presented.

A main result in combinatorial optimization is that clique and chromatic number of a perfect graph can be computed in polynomial time (Groetschel, Lovasz and Schrijver 1981). This result relies on polyhedral characterizations of perfect graphs involving the stable set polytope of the graph, a linear relaxation de?ned by clique constraints, and a semi-de?nite relaxation, the Theta-body of the graph. A natural question is whether the algorithmic results for perfect graphs can be extended to graph classes with similar polyhedral properties. We consider a superclass of perfect graphs, the a-perfect graphs, whose stable set polytope is given by constraints associated with generalized cliques. We show that for such graphs the clique number can be computed in polynomial time as well. The result strongly relies upon Fulkersons’s antiblocking theory for polyhedra and Lovasz’s Theta function.

On a perfect graph $G(V, E)$ with a strictly positive integer weight function on the vertices $w(v)$, $v\in V$, the minimum weight clique cover problem is the dual problem of the maximum weight stable set and it consists of building a collection of cliques $\mathcal{C}$, each one with a non negative weight $y_C$, such that, for each $v\in V$, $\sum_{C\in\mathcal{C}:v\in C}y_C\geq w(v)$, and $\sum_{C\in\mathcal{C}}y_C$ is minimum. The minimum weight clique cover can be solved in polynomial time on perfect graphs with the ellipsoid method, however, for particular classes of perfect graphs, there also exist poly-time combinatorial algorithms. This is the case, for instance, for claw-free perfect graphs, where a combinatorial algorithm has been proposed by Hsu and Nemhauser. (A graph is claw-free if none of its vertices has a stable set of size three in its neighborhood.) To the best of our knowledge, this is so far the only available combinatorial algorithm to solve the problem in claw-free perfect graphs. The algorithm in by Hsu and Nemhauser is then heavily based on the solution of the maximum weight stable set, so, in a way, the algorithm it is essentially a dual algorithm. In this paper, we propose an algorithm for the minimum weight clique cover for a relevant subclass of claw-free perfect graphs which is essentially primal. The algorithm exploits an algorithmic decomposition theorem by Faenza, Oriolo and Stauffer for quasi-line graphs. A graph is quasi-line if the neighborhood of each vertex can be covered by two cliques. Quasi-line graphs are a generalization of line graphs and a subclass of claw-free graphs, and it is well known that a graph is claw-free perfect if and only if it is quasi-line perfect. Our new algorithm is designed for the case in which the claw-free perfect graph $G$ is the composition of some simple graphs called strips. We are now dealing with the remaining case, that is a subclass of quasi-line net-free perfect graphs.

Given a graph, the edge formulation of the stable set problem is defined by two-variable constraints, one for each edge, 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 simplex pivots in terms of simple graphic operations, that turn a given basis into an adjacent one. Between all possible pivots, we characterize degenerate and nondegenerate ones, and we differentiate those leading to an integer or to a fractional vertex. The graphic characterization of bases is crucial to prove another structural property of the fractional stable set polytope, concerning the adjacency of its vertices. In particular, we extend a necessary and sufficient condition due to Chvàtal for adjacency of (integer) vertices of the stable set polytope to arbitrary (and possibly fractional) vertices of the fractional stable set polytope. These results lead us to prove that the Hirsch Conjecture is true for the fractional stable set polytope, i.e. the combinatorial diameter of this fractional polytope is at most equal to the number of edges of the given graph. This is joint work with Antonio Sassano.

One of the fundamental open problems in optimization and discrete geometry is the question whether the diameter of a polyhedron can be bounded by a polynomial in the dimension and the number of its defining inequalities. We study polyhedra whose sub-determinants of its constraint matrix are bounded by some number D, and derive a a new upper bound on the diameter of those polyhedra. If n is the number of defining inequalities, our diameter bound is O(D^2 n^4 log(nD)). For the special case of polyhedra defined by totally unimodular matrices, our bound is O(n^4 log(n)), improving on the previously best bound of m^16 n^3 (log mn)^3 by Dyer and Frieze (m being the dimension of the polyhedron). Joint work with Nicolas Bonifas, Marco Di Summa, Friedrich Eisenbrand and Nicolai Hähnle.

Let $G=(V,E)$ be an undirected graph with a set $V$ of vertices and a set $E$ of edges. A subset $W$ of $V$ is a dominating set of $G$ if, for every vertex $i \in V \setminus W$, an edge $e \in E$ exists with one endpoint in $i$ and the other in $j \in W$. The dominating set is connected if the subgraph $G_{W}=(W,E(W))$ it induces in $G$ is connected. In particular, the dominating set is $k$-edge-connected (respect. $k$-vertex-connected) if $G_{W}$ remains connected when fewer than $k$ edges (respect. vertices) are removed from it. The presentation describes our ongoing research on $k$-connected dominating sets and will be focused on the Minimum Connected Dominating Set Problem (i.e., the $1$-Edge-Connected Minimum Dominating Set Problem) and on some problems defined over particular subgraphs of $G_W$, such as spanning trees and circuits. Specifically, for $G$ as previously defined, we also investigate the Minimum Dominating Tree Problem and the Minimum Dominating Circuit Problem. For the problem involved we introduce formulations, valid inequalities and branch and cut algorithms. Additionally we also present a new formulation for the Cycle Problem, together with corresponding computational results. In the literature, $\{1,2\}$-connected dominating sets have been suggested as models for ad-hoc wireless networks. The Dominating Circuit Problem, in spite of implying an attractive topology for telecommunications networks, does not appear to have been previously investigated. However, it could be seen as the basic underlying structure for the Ring-Star Problem. Our computational results for the Minimum Connected Dominating Set Problem are competitive with those quoted for the closely related Maximum Leaf Spanning Tree Problem. This work is joint with Alexandre Salles da Cunha and Luidi Simonetti.

In the 1-d infinite group relaxation, the celebrated 2-Slope Theorem gives a sufficient condition for a minimal function to be extreme. This is an important tool for building and analyzing valid inequalities. Extending this result, and a recent generalization by Cornuejols and Molinaro, we show that in the k-d case, minimal piecewise linear functions with k+1 slopes (satisfying a necessary regularity condition) are extreme. This is practically motivated by increasing interest in multi-row cuts.

Let L be a family of lattice-free polyhedra containing the splits. Given a polyhedron P, we characterize when a valid inequality for the mixed integer hull of P can be obtained with a finite number of disjunctive cuts corresponding to the polyhedra in L. We also characterize the lattice-free polyhedra M such that all the disjunctive cuts corresponding to M can be obtained with a finite number of disjunctive cuts corresponding to the polyhedra in L, for every polyhedron P. Our results imply interesting consequences, related to split rank and to integral lattice-free polyhedra, that extend recent research findings.

We consider the question of how to generate cutting planes from arbitrary multi-row mixed-integer relaxations. In general, these cutting planes can be obtained by row generation, i.e. solving a ("master") LP whose constraint are iteratively constructed by solving ("slave") MIPs. We show how to reduce the size of both problems by adopting a two-phases approach exploiting the bounds on variables and performing sequential lifting whenever possible. We use these results to implement a separator for arbitrary multi-row mixed-integer relaxations and perform computational tests in order to evaluate and compare the strength of some important multi-row relaxations. This is joint work with Quentin Louveaux and Domenico Salvagnin.

We consider optimization problems under the assumption that there is private information. Next to the problem itself, also incentive constraints have to be taken into account. These reflect the fact that jobs need to be induced, by side payments, to behave truthfully. We consider a classical, polytime solvable single machine scheduling problem, but with private job data. While it is well known how this problem can be solved when private data is single-dimensional, not much is known for multi- dimensional mechanism design problems. We use integer linear programming to find optimal scheduling mechanisms for a 2-dimensional mechanism design problem. So far, this approach is prohibitive for all but toy problems, yet it allows to generate and test hypotheses on small scale problems. This way, we gain new insights into optimal mechanisms.

joint work with Andrea Lodi, Nicolas Stier-Moses, Tommaso Bonino We consider the problem of an Agency who contracts a public transport service to a private Operator. We address the informative asymmetry between the two players from a game theoretical perspective, and propose an optimized control strategy based on the solution of a price collecting routing model. We show that an improved control results in an incentive, for the Operator, to provide reliable information about its own performance.

We present the Integrated Size and Price Optimization Problem (ISPO) for a fashion discounter with many branches. Branches are supplied by pre-packaged bundles consisting of items of different size and number – so-called lot-types. Our goal is to find a revenue-maximizing supply strategy. Based on a two-stage stochastic programming model including the effect of markdowns as recourse, we developed an exact branch-and-bound algorithm where dual bounds are obtained by combinatorical bounds combined with LP-relaxations. For practical purposes we developed a production-compliant heuristic, the so-called ping-pong-heuristic, that uses the special structure of the problem by alternately solving price and size optimization. In all tested cases we obtain very small optimality gaps (< 0.03 %). In a field study we show that a distribution of supply over branches and sizes based on ISPO solutions is significantly better than a one-stage optimization of the distribution ignoring the possibility of optimal pricing.

In the talk we define the bilevel lot-sizing problem, and provide two alternative MIP formulations. The first formulation is based on a characterization of the optimal solutions of the parametric uncapacitated lot-sizing problem, where the parameters are the demands. The second formulation is based on a shortest path formulation of ULSB. To strengthen the formulations, non-trivial bounds on the variables, as well as cutting planes are derived. The two alternative formulations are compared on benchmark instances.

We solve a 20-year old problem posed by M. Yannakakis and prove that there exists no polynomial-size linear program (LP) whose feasible region projects to the traveling salesman polytope, even if the LP is not required to be symmetric. Moreover, we prove that this holds also for the maximum cut polytope and the stable set polytope. These results follow from a new connection that we make between one-way quantum communication protocols and semidefinite programming reformulations of LPs. This is joint work with Samuel Fiorini, Serge Massar, Hans Raj Tiwary, and Ronald de Wolf.

We consider the intersection of a convex set and a linear disjunction. Under mild assumptions, the convex hull of that intersection can be enclosed in a cone K. In the special case of mixed integer second order cone optimization, we give a closed form representation of K and a procedure to generate second order conic cuts.

"Preliminary abstract" We show how to solve MINLPs originating in gas network optimization to global optimality. Building on previous work we can give tight MILP relaxations of the underlying MINLP. We can solve the problem to compute the cost-optimal switching configuration to fulfill transport demand on a real world network (ca. 600 nodes). We give computational results for a number of real world instances on this network.

We study the t-branch split cuts introduced by Li and Richard (2008). They presented a family of mixed-integer programs with n integer variables and a single continuous variable and conjectured that the convex hull of integer solutions for any n has unbounded rank with respect to $(n-1)$-branch split cuts. It was shown earlier by Cook, Kannan and Schrijver (1990) that this conjecture is true when n=2, and Li and Richard proved the conjecture when n=3. We show that this conjecture is also true for all n>3. In the second part, we show that every facet-defining inequality of the convex hull of a rational mixed-integer polyhedral set with $n$ integer variables is a rank-1 t-branch split cut for some positive integer t which is a function of n, and not of the data defining the polyhedral set. This result also leads to a finitely convergent, pure cutting-plane algorithm to solve mixed-integer programs. **Joint work with Dash, Dobbs, Nowicki, and Swirszcz

Gomory Mixed-Integer (GMI) cuts are one of the key components of Branch-and-Cut solvers for Mixed-Integer Linear Programs (MILPs). It is therefore surprising that no rigorous investigation on the numerical issues arising from their utilization in practice is available in the literature. In this paper we study the GMI cut generation procedure. We propose a randomized method for testing the safety of cut generators in a Branch-and-Cut framework, and discuss key related issues, such as checking validity of cutting planes. We identify the parameters involved in cut generation and present a method to heuristically optimize over the parameter space. The goal is to find the combination of cut generation parameters that rejects the fewest cuts while achieving a desired level of safety. This is joint work (in progress) with Gerard Cornuejols and Francois Margot

The first split closure has been proven in practice to be a very tight approximation of the ideal convex hull formulation of a generic Mixed Integer Linear Program. Since exact separation procedures for optimizing over it have unacceptable computing times, in the last years many different heuristic strategies have been proposed. In this talk we survey the most successful among these strategies, and we present a new overall framework for approximating the first split closure, that merges many ideas from the previous approaches. Computational results prove the effectiveness of the proposed procedure compared to the state of the art, indeed showing that a good approximation of the first split closure can be obtained nowadays with reasonable computing times.

V. Cacchiani, A. Caprara, P. Toth We consider the following general scheduling problem. We are given a set of fixed tasks, each one having a start time, an end time and a weight. We are also given a set of single-thread processors, each one having a capacity and capable of executing at most one task at a time. Each task must be executed from its start to its end time by a set of processors with overall capacity at least equal to the task weight. There may be also upper bounds (e.g., one or two) on the number of processors on which each task can be executed. Finally, there is a setup time from the end of a task to the beginning of the next one on a processor, which in general depends on the two tasks. The goal is to determine the minimum number of processors needed to execute all the tasks. In a former work we considered an ILP model for the problem with one variable for each possible schedule of each processor. A diving heuristic based on this model produced lower bounds and heuristic solutions of good quality, but turned out to be fairly time consuming. In this work we propose a heuristic algorithm based on the optimal solution of the restricted problem associated with a peak period, i.e., with a subset of simultaneous tasks that must be executed on distinct processors. The peak period is determined by computing a maximum-weight stable set on a suitable comparability graph. The heuristic is tested on a real-world Train Unit Assignment Problem arising in the planning of a railway passenger system. The results show that the new method is much faster than the previous one, being usable within a real-time scheduling context, and sometimes provides heuristic solutions of better quality.

A fasciagraph of size n is a graph constituted by a sequence of n copies of the same graph, each one being linked to the next one following the same scheme, and a rotagraph is a fasciagraph where the last copy is linked to the first one. For example, grids are fasciagraphs and toroidal grids are rotagraphs. We characterize optimization problems which can be solved for rota- and fasciagraphs using a generic algorithm. For a fixed duplicated graph this algorithm may provide the optimal value in constant time (independent of the number of copies).

We prove that every $(6k+2\ell,2k)$-connected simple graph contains $k$ rigid and $\ell$ connected edge-disjoint spanning subgraphs. This implies a theorem of Jackson and Jord\'an (2009) and a theorem of Jord\'an (2005) on packing of rigid spanning subgraphs. Both these results are generalizations of the classical result of Lov\'asz and Yemini saying that every $6$-connected graph is rigid for which our approach provides a transparent proof. Our result also gives two improved upper bounds on the connectivity of graphs that have interesting properties: (1) every $8$-connected graph packs a spanning tree and a $2$-connected spanning subgraph; (2) every $14$-connected graph has a $2$-connected orientation.

We recently started the ambitious project of solving to proven optimality (at least, some of) the largest “esc” instances of the famous quadratic assignment problem (QAP). These are extremely hard instances that remained unsolved—even allowing for a tremendous computing power—by using all previous techniques from the literature. During this challenging task we tested a number of ideas, and found that three of them were particularly useful and qualified as a breakthrough for our approach. This talk is about describing these ideas and the status of our attempt. So far our method was able to solve, in a matter of seconds or minutes on a single PC, all the easy cases (all esc16* plus esc32e and esc32g). Almost all the previously-unsolved esc instances, namely esc32c, esc32d, esc32h, esc64a and esc128 were solved in less than 3 hours, all together, on a single PC. We also report the solution of the previously-unsolved tai64c, again within very reasonable computing time. To the best of our knowledge, esc128 is the largest QAP instance ever solved by an exact method. (joint work with Matteo Fischetti and Domenico Salvagnin)

In 1996, Laurent and Poljak introduced an extremely general class of cutting planes for the max-cut problem, called gap inequalities. We prove several results about them, including the following: (i) the gap inequalities with gap equal to 1 do not imply all other gap inequalities, unless NP = CoNP; (ii) there must exist gap inequalities with exponentially large coecients that are not implied by other gap inequalities, unless NP = CoNP; (iii) the separation problem for gap inequalities can be solved in finite (doubly exponential) time.

In this paper we examine the impact of using the Sherali-Adams procedure on highly symmetric integer programming problems. Linear relaxations of the extended formulations generated by Sherali-Adams can be very large, containing on the order of n choose d many variables for the level-d closure. When large amounts of symmetry are present in the problem instance however, the symmetry can be used to generate a much smaller linear program that has an identical objective value. We demonstrate this by computing the bound associated with the level 1, 2, and 3 relaxations of several highly symmetric binary integer programming problems. We also present a class of constraints, called counting constraints, that further improves the bound, and in some cases provides a tight formulation. A major advantage of the Sherali-Adams formulation over the traditional formulation is that symmetry-breaking constraints can be more efficiently implemented. We show that using the Sherali-Adams formulation in conjunction with the symmetry breaking tool isomorphism pruning can lead to the pruning of more nodes early on in the branch-and-bound process

Until recently, LP relaxations have only played a very limited role in the design of approximation algorithms for the Steiner tree problem. This changed when Byrka, Grandoni, Rothvoss and Sanità demonstrated a ln(4) approximation algorithm based on a component-based relaxation (one of a family of "hypergraphic" relaxations). Surprisingly, even though their approach is LP based, they do not obtain a matching bound on the integrality gap, showing only a weaker 1.55 bound by other methods. We show that indeed the integrality gap is bounded by ln(4). In the process, we obtain a much better structural understanding of these hypergraphic LPs, as well as more efficient and simpler algorithms. Techniques from the theory of matroids and submodular functions play a crucial role. (Joint work with Michel Goemans, Thomas Rothvoss and Rico Zenklusen.)

A 1991 paper by Queyranne and Wang proposed three classes of valid constraints for the convex hull of feasible completion times for schedules on a single machine subject to precedence constraints. These classes are called the parallel constraints, serial constraints, and Z constraints. These constraints have been very useful in many contexts. Queyranne and Wang showed how to separate the parallel constraints, but the complexity of separating the serial and Z constraints has remained open. Wolsey gave a compact extended formulation that is stronger than the QW formulation. Here we show that it is NP Hard to separate the serial class of constraints, despite the fact that the stronger compact formulation has a trivial separation algorithm. We also show a polynomial separation routine when the precedence constraints are series-parallel.