This work is joint with Amitabh Basu and Francois Margot. We consider MILPs where free integer variables are expressed in terms of nonnegative continuous variables. When this model has only two integer variables, Santanu Dey and Quentin Louveaux characterized the intersection cuts that have infinite split rank. We show that, for any number of integer variables, the split rank of an intersection cut generated from a bounded convex set P is finite if and only if the integer points on the boundary of P satisfy a certain "2-hyperplane property". The Dey-Louveaux characterization is a consequence of this more general result.

We present a family of asymmetric disjunctions for mixed-integer polyhedra called crooked cross disjunctions. Cuts generated from these asymmetric disjunctions subsume 2-dimensional lattice-free cuts as well as S-free cuts. We show that crooked cross cuts give the convex hull of mixed-integer sets when there are only two integer variables or when the coefficients of the integer variables form a matrix of rank 2. We also present computational results showing that these cuts can be effective in practice. Joint work with Sanjeeb Dash, Santanu Dey and Juan-Pablo Vielma.

We define the integral lattice-free closure L(P) of a rational polyhedron P as the set obtained from P by adding all inequalities obtained from disjunctions associated with integral lattice-free sets. We show that L(P) is again a polyhedron, and that repeatedly taking the integral lattice-free closure of P gives its mixed integer hull after a finite number of iterations.

A longstanding open problem in integer programming is the question whether the additive gap of the Gilmore-Gomory formulation for cutting stock is bounded by a constant. Despite a lot of research and thinking about this problem, the O(log n)^2 bound of Karmarkar and Karp from the 80's is still the best known today whereas the "Modified Integer Roundup Conjecture" has not been falsified. In this talk I will re-visit this "Modified Integer Roundup Conjecture" and also discuss a prominent conjecture from Discrepancy theory stated by Beck. The surprise is: If Becks conjecture holds, then the integrality gap for bin-packing, where all items are larger than 1/4 is a constant. The result establishes thus a link between IP and Discrepancy Theory. Joint work with T. Rothvoss and D. Palvolgyi Paper appears at SODA 11

Dantzig-Wolfe decomposition is well-known to provide strong dual bounds for specially structured mixed integer programs (MIPs) in practice. However, the method is not part of any state-of-the-art MIP solver: it needs tailoring to the particular problem; the typical bordered block-diagonal matrix structure determines the decomposition; the resulting column generation subproblems need to be solved efficiently; branching and cutting decisions need special attention; etc. We perform an extensive computational study on the 0-1 dynamic knapsack problem (without block-diagonal structure) and on general MIPLIB2003 instances in order to (in-)validate such reservations against the method. We present a tool which, given an LP file, automatically detects an exploitable matrix structure, accordingly performs a Dantzig-Wolfe type reformulation of subsets of the constraints (partial convexification), and performs column generation to obtain an optimal LP relaxation. Our results strongly support that Dantzig-Wolfe decomposition holds more promise as a general-purpose tool than previously acknowledged by the research community.

The best known method for determining lower bounds on the vertex coloring number of a graph is the linear-programming column-generation technique first employed by Mehrotra and Trick in 1996. We present an implementation of the method that provides numerically safe results, independent of the floating-point accuracy of linear-programming software. Our work includes an improved branch-and-bound algorithm for maximum-weight stable sets and a parallel branch-and-price framework for graph coloring. Computational results are presented on a collection standard test instances, including the unsolved challenge problems created by David S. Johnson in 1989. This is joint work with Edward C. Sewell and William Cook

Construction and Applications of Significant Polyhedra by K. Truemper Abstract: Consider a process E from which a data set X = {(x,t) instances} has been collected, where x is a vector in R^n and t is a scalar called the target. We want pairs (I,P) where I is an interval for the target t and P is a (full-dimensional) polyhedron P for which the following holds: (1) The inequalities of each case of P can be comprehended by humans in terms of the process E. (2) For all (x,t) of X: if t is not in interval I, then x is not in P. (3) The points (x,t) with x in P represent with high probability an unusual (non-random) aspect of process E relative to target t. The polyhedron P is called significant for process E, relative to target t. Collectively, the pairs (I,P) must represent all unusual aspects of process E relative to target t. We present an approach for constructing the desired intervals I and polyhedra P, and discuss applications in oncology, neurology, and engineering.

We describe results of our computational experiments with cross cuts, also known as 2-branch split cuts in the literature. We are able to verify for a number of MIPLIB instances that the cross cut closure bounds are stronger than the split closure bounds. We also show that cross cuts obtained from pairs of tableau rows significantly improve the bound obtained by GMI cuts from the same tableau rows. This is joint work with Oktay Gunluk and Juan Pablo Vielma

Hoffman and Schwartz developed (1978) the Lattice Polyhedron model and proved that it is totally dual integral, and so has integral optimal solutions. The model generalizes many important combinatorial optimization problems such as polymatroid intersection, cut covering polyhedra, mincost arborescences, etc., but has lacked a combinatorial algorithm. The problem can be seen as the blocking dual of Hoffman's Weighted Abstract Flow (WAF) model, or as an abstraction of ordinary Shortest Path and its cut packing dual, so we call it Weighted Abstract Cut Packing (WACP). We develop the first combinatorial algorithm for WACP, based on the Primal-Dual framework. (Joint work with Tom McCormick.)

(joint work with Bjoern Geissler, Alexander Martin, and Antonio Morsi) We present methods to formulate and solve MINLPs originating in stationary gas network optimization. To this aim we use a hierachy of MIP-relaxations and a graph decomposition approach. Thus, we are able to give tight relaxations of the underlying MINLP. The methods we present can be generalized to other non-linear network optimization problems with binary decisions. We give computational results for a number of real world instances.

There are many examples of optimization problems whose associated polyhedra can be described much nicer, and with way less inequalities, by projections of higher dimensional polyhedra than this would be possible in the original space. However, currently not many general tools to construct such extended formulations are available. In this paper, we develop a framework of polyhedral relations that generalizes inductive constructions of extended formulations via projections, and we particularly elaborate on the special case of reflection relations. The latter ones provide polynomial size extended formulations for several polytopes that can be constructed as convex hulls of the unions of (exponentially) many copies of an input polytope obtained via sequences of reflections at hyperplanes. We demonstrate the use of the framework by deriving small extended formulations for the $G$-permutahedra of all finite reflection groups~ $G$ (generalizing both Goeman's~\cite{Goe09} extended formulation of the permutahedron of size $\bigO{n\log n}$ and Ben-Tal and Nemirovski's~\cite{BN01} extended formulation with $\bigO{k}$ inequalities for the regular $2^k$-gon) and for Huffman-polytopes (the convex hulls of the weight-vectors of Huffman codes).

In social choice theory, a vast amount of literature deals with quantifying the probability of certain election outcomes. This is in particular the case for so-called ``voting paradoxes''. One way of computing the probability of a specific voting situation is via counting integer points in associated polyhedra. Here, Ehrhart theory can help, but unfortunately the dimension and complexity of the involved polyhedra grows rapidly with the number of candidates. However, if we exploit available polyhedral symmetries, some computations become possible that otherwise seem infeasible. We exemplarily show this in two very well known examples: Condorcet's paradox and in plurality voting vs plurality runoff.

It is well known that the Birkhoff polytope provides a symmetric extended formulation of the permutahedron Pi_n of size Theta(n^2). Recently, Goemans described asymptotically minimal extended formulation of Pi_n of size Theta(n log(n)). In this paper, we prove that Omega(n^2) is a lower bound for the size of symmetric extended formulations of Pi_n. Thus, it is possible to determine tight lower bounds Omega(n^2) and Omega(n log(n)) on the sizes of symmetric and non-symmetric extended formulations of Pi_n .

In a landmark paper from 1986, Kawaguchi and Kyan showed that scheduling jobs on parallel machines according to Smith's rule has a performance guarantee of 1.207, and this bound is tight. We consider the stochastic variant of the same problem in which the processing times are exponentially distributed random variables. We show, somehow counterintuitively, that the performance guarantee of the WSEPT rule, the stochastic analogue of WSPT, is not better than 1.243.

We consider the Steiner tree problem under a 2-stage stochastic model with recourse and finitely many scenarios (SSTP). Thereby, edges are purchased in the first stage when only probabilistic information on the set of terminals and the future edge costs is known. In the second stage, one of the given scenarios is realized and additional edges are purchased to interconnect the set of (now known) terminals. The goal is to choose an edge set to be purchased in the first stage while minimizing the overall expected cost of the solution. We provide a new semi-directed cut-set based integer programming formulation that is stronger than the previously known undirected model. To solve the formulation to provable optimality, we suggest a two-stage branch-and-cut framework, facilitating (integer) L-shaped cuts. The framework itself is also applicable to a range of other stochastic problems. As SSTP has yet been investigated only from the theoretical point of view, we also present the first computational study for SSTP, showcasing the applicability of our approach and its benefits over solving the extensive form of the deterministic equivalent directly.

In this talk, we introduce the two-stage stochastic minimum s?t cut problem. We derive two alternative definitions for the stochastic version, based on two classical formulation of the minimum s-t cut problem and we can show that those definitions differ for the stochastic case. Furthermore, we use a classical linear 0–1 programming model for the deterministic minimum s?t cut problem to derive a mathematical programming formulation for the proposed problem. We show that its constraint matrix looses its total unimodularity property, however, preserves it if the considered graph is a tree.

Working in an extended variable space allows one to develop tight reformulations for mixed integer programs. However, the size of the extended formulation grows rapidly too large for a direct treatment by a MIP-solver. Then, one can use projection tools to derive valid inequalities for the original formulation and implement a cutting plane approach. Or, one can approximate the reformulation, using techniques such as variable aggregation or by reformulating a submodel only. Such approaches result in outer approximation of the intended extended formulation. The alternative considered here is an inner approximation obtained by generating dynamically the variables of the extended formulation. It assumes that the extended formulation stems from a decomposition principle: a subproblem admits an extended formulation from which an extended formulation for the original problem can be derived. Then, one can implement column generation for the extended formulation of the original problem by transposing the equivalent procedure for the Dantzig-Wolfe reformulation. Pricing subproblem solutions are expressed in the variables of the extended formulation and added to the current restricted version of the extended formulation along with the subproblem constraints that are active for the subproblem solution. The paper reviews the applications of the literature of such ``column-and-row generation'' procedure and analyses this approach's potential benefits compared to a standard column generation approach. Numerical experiments highlight a key observation: lifting pricing problem solutions in the space of the extended formulation permits their recombination into new subproblem solutions and results in faster convergence.

(Joint work with E. Amaldi and S. Gualandi) Successful implementations of cutting plane methods usually include a first phase where a large number of cuts are generated according to some objective function (e.g., cut violation), and a second phase in which a subset of those cuts are selected according to different criteria (e.g., depth, cut parallelism, objective function gradient parallelism,...) and then added to the current linear programming relaxation. Motivated by the computational experience reported in the recent literature and by some simple properties, we consider two cut selection criteria: cut violation and a measure of diversity between successive cuts. We propose a multi-objective separation problem with priority aiming at cuts that simultaneously meet both selection criteria. Since the cuts generated via multi-objective separation depend on previously added cuts, our method introduces a form of cut coordination. Different versions of the multi-objective separation problem are considered and investigated. In this work we focus on valid inequalities with 0-1 coefficients in the left-hand side. We show that, in this case, the most promising versions of the multi-objective separation problem retain the same combinatorial structure of the classical separation problem, where violation is maximized, though involving a different objective function gradient. Multi-objective separation can thus be solved with the same separation algorithms that are used for classical separation. The impact of our cut coordination scheme is assessed in a pure cutting plane setting on max clique (stable set inequalities) and min Steiner tree (cut set inequalities). Computational experiments show that multi-objective separation, compared to the classical separation, can typically close a larger fraction of the duality gap in a considerably smaller number of rounds, generating fewer cuts, and obtaining a final relaxation which is numerically more stable.

Split cuts constitute a class of cutting planes that has been successfully employed by the majority of Branch-and-Cut solvers for Mixed Integer Linear Programs. Given a basis of the LP relaxation and a split disjunction, the corresponding split cut can be computed with a closed form expression. In this paper, we use the Lift-and-Project framework to provide the basis, and the Reduce-and-Split algorithm to compute the split disjunction. We propose a cut generation algorithm that starts from a Gomory Mixed Integer cut and alternates between Lift-and-Project and Reduce-and-Split in order to strengthen it. This paper has two main contributions. First, we extend the Balas and Perregaard procedure for strengthening cuts arising from split disjunctions involving one variable, to split disjunctions on multiple variables. Second, we apply the Reduce-and-Split algorithm to non-optimal bases of the LP relaxation. We provide detailed computational testing of the proposed methods.

Intersection cuts are generated from a polyhedral cone and a convex set S whose interior contains no feasible integer point. We generalize these cuts by replacing the cone with a more general polyhedron C. The resulting generalized intersection cuts dominate the original ones. This leads to a new cutting plane paradigm under which one generates and stores the intersection points of the extreme rays of C with the boundary of S rather than the cuts themselves. These intersection points can then be used to generate in a non-recursive fashion cuts that would require several recursive applications of some standard cut generating routine. A procedure is also given for strengthening the coefficients of the integer-constrained variables of a generalized intersection cut. The new cutting plane paradigm yields a new characterization of the closure of intersection cuts and their strengthened variants. This talk is based on joint work with Francois Margot If possible, I would like to speak early in the weak, and I am willing to speak on Monday afternoon. Also, if possible, I would like to have about 40 minutes.

Inspired by online ad allocation, we study online stochastic packing integer programs from theoretical and practical standpoints. We first present a near-optimal online algorithm for a general class of packing integer programs which model various online resource allocation problems including online variants of routing, ad allocations, generalized assignment, and combinatorial auctions. As our main theoretical result, we prove that a simple dual training-based algorithm achieves a $(1-o(1))$-approximation guarantee in the random order stochastic model. We then focus on the online display ad allocation problem and study the efficiency and fairness of various training-based and online allocation algorithms on data sets collected from real-life display ad allocation system. Our experimental evaluation confirms the effectiveness of training-based algorithms on real data sets, and also indicates an intrinsic trade-off between fairness and efficiency.

We address an optimization problem in which two agents, each with a set of weighted items, compete in order to maximize resp. minimize the total weight of their solution sets. The latter are built according to a sequential game consisting in a fixed number of rounds. In every round each agent submits one item that may be included in its solution set. We study two natural rules to decide which item between the two will be included. The problem is addressed from a strategic point of view, that is finding the best moves for one agent against the opponent, in two distinct scenarios. We consider preventive or maximin resp. minimax strategies, optimizing the objective of the agent in the worst case, and best-response strategies, where the items submitted by the opponent are known in advance in each round. Several exact and approximate algorithms with worst-case performance guarantees will be presented.

We study flows over time in networks with transit times on the arcs. Transit times describe how long it takes to traverse an arc. A flow over time specifies for each arc a time-dependent flow rate that must always be bounded by the arc’s capacity. Only recently, Melkonian introduced an alternative model where so-called bridge capacities bound the total amount of flow traveling along an arc, at any point of time. Our contribution is twofold. Firstly, we introduce a common generalization of both the classical flow over time model and Melkonian’s model. Secondly, we present a non-trivial extension of an FPTAS by Fleischer and Skutella to our new flow model. Prior to this, no approximation algorithm was known for Melkonian’s model. This is joint work with my PhD student Daniel Dressler.

We will present the problem class of mixed-integer nonlinear optimal control. We will present a comprehensive approach to solve this problem class based on outer convexification with respect to integer control functions, a first discretize - than optimize approach and application of an approximation theorem. We will discuss how this approach leads to MILP subproblems, discuss solution properties with respect to the nonlinear problem and present an efficient algorithm to solve these structed optimization problems for the special case of switching constraints.

The fixed-charge transportation problem is a fixed-charge network flow problem on a bipartite graph. This problem appears as a subproblem in many hard transportation problems, and is also both a special case and a strong relaxation of the challenging big-bucket multi-item lot-sizing problem. In this paper, we provide a polyhedral analysis of the polynomially solvable special case in which the associated bipartite graph is a path. We describe a new class of inequalities that we call "path-modular" inequalities. We give two distinct proofs of their validity. The first one is direct and crucially relies on sub- and super-modularity of an associated set function, thereby providing an interesting link with flow-cover type inequalities. The second proof is by showing that the projection of an O(n2)-size extended linear programming formulation onto the original variable space yields exactly the polyhedron described by the path-modular inequalities. Thus we also show that these inequalities suce to describe the convex hull of the feasible solutions to this problem. We finally show how to solve the separation problem associated to the path-modular inequalities in O(n3) time.

The graph embedding problem consists in finding an embedding x:V->R^K of a simple weighted undirected graph G=(V,E,d) such that for each edge {u,v} we have ||x(u) - x(v)|| = d(u,v). Although the problem in general requires a search in continuous space, we restrict attention to a subclass of instances for which there is a vertex order that allows for a discrete search. This subclass is still NP-hard. Here's a strange occurrence which we noticed in 2005: every instance yields a number of solutions which is a power of two. Five years since, we managed to prove that this conjecture holds with probability 1. Using the same theoretical set-up we also exhibit some sufficient conditions for which the problem is in P. Interestingly, all tested protein graphs satisfy these conditions, thus providing an important application to this problem.

The Maximum Benefit Chinese Postman Problem (MBCPP) is an arc routing problem that considers the collection of a profit when edges are serviced. Associated with each edge, the MBCPP considers a cost of traversal if the edge is serviced, a deadhead cost associated with its traversal when it is not serviced, and several benefits (one per each time the edge is traversed with service). The objective is to find a closed walk starting and ending at the depot with maximum net benefit. Unlike the classical CPP, the MBCPP is NP-hard and generalizes other arc routing problems as the Rural Postman Problem (RPP) and the Prize-Collecting RPP. Although the MBCPP was introduced in 1993, we propose here for the first time an IP formulation for the undirected case. We also study its associated polyhedron and introduce several families of valid inequalities inducing facets of it. Based on this polyhedron description, we propose a branch-and-cut algorithm for the MBCPP and present computational results on different sets of instances with up to 1000 vertices and 3000 edges.

The Traveling Salesman Problem with Time Windows (TSPTW) is the problem of finding, in a weighted digraph, a least cost tour starting from a selected vertex, visiting each vertex exactly once within its time window, and returning back to the starting vertex. In this talk, we present two tour relaxations, called ng-tour and ngL-tour, to compute valid lower bounds obtained, via column generation, as the costs of near optimal dual solutions of a problem that seeks a minimum-weight convex combination of tours. The tour relaxations and the dual solutions obtained are used to solve to optimality the problem using dynamic programming. We present an extensive computational analysis on several classes of both real-world and random instances taken from the literature, showing that the proposed algorithm outperforms the state-of-the-art exact methods.

This paper concerns a vehicle routing problem where each vehicle has upper and lower capacities. We assume one depot, an homogeneous fleet of vehicles and all customers requiring the same demand of a product. A feasible solution for this problem requires that all routes should visit a number of customers within a given interval specified by the lower and upper capacities. The problem is called "Balanced Vehicle Routing Problem" (BVRP). In this paper we adapt the single-commodity-flow formulation known in the literature for the so-called Capacitated Vehicle Routing Problem (CVRP). We also discuss some new inequalities that are irrelevant for the CVRP but which play a fundamental role for the BVRP. These are the so-called "Reverse Multistar inequalities" that are related to the "Multistar inequalities", well known from the literature on the CVRP. This paper also proposes other new families of inequalities and analyzes computational experiments that show the convenience of using these new inequalities when solving BVRP instances. The experiments are based on variations of CVRP instances with up to 100 customers. In addition this paper studies the impact of using the new inequalities for solving CVRP instances where the number of vehicles is fixed. Although empirically these inequalities do not always reduce the computational time to solve larger instances when compared to other approaches in the literature, the paper analyzes several theoretical properties and motivates the idea that lower bound information might be useful for some other variations of the CVRP. Joint work with Luis Gouveia (Lisbon) and Jorge Riera (Tenerife).

We regard a traveling salesman problem with quadratic cost terms depending on any two successive arcs in the tour in a directed (QATSP) and an undirected (QSTSP) setting. This problem is motivated by a real world application in biology, the recognition of transcription factor binding sites in gene regulation. For both, QATSP and QSTSP, we study the polytopes of the linearized models, present valid inequalities and investigate the computational complexity of the corresponding separation problems. Using these cuts, real world instances from biology can be solved up to 80 cities in less than 13 minutes. Random instances turn out to be difficult, but on these semidefinite relaxations help to reduce the gap in the root node significantly. This is a joint work with Christoph Helmberg.

We summarize our experience in solving combinatorial optimization problems arising in railway planning, illustrating all of these problems as integer multicommodity flow ones and discussing the main features of the mathematical programming models that were successfully used in the 1990s and in recent years to solve them.

We present an approach based on semidefinite programs (SDP) to tackle the multi-level crossing minimization problem. Thereby, we are given a layered graph (i.e., the graph's vertices are assigned to multiple parallel levels) and ask for an ordering of the nodes on their levels such that, when drawing the graph with straight lines, the resulting number of crossings is minimized. Solving this step is crucial in the probably most widely used graph drawing scheme, the so-called Sugiyama framework. The problem has received a lot of attention both in the field of heuristics and exact methods. For a long time, integer linear programming (ILP) approaches were the only exact algorithms applicable at least to small graphs. Recently, SDP formulations for the special case of two levels were proposed and dominated the ILP for dense instances. In this paper, we present a new SDP formulation for the general multi-level version that, for two-levels, is even stronger than the aforementioned specialized SDP. As a side-product, we also obtain an SDP-based heuristic which in practice always gives (near-)optimal solutions. We conduct a large set of experiments, both on randomized and on real-world instances, and compare our approach to a state-of-the-art ILP-based branch-and-cut implementation. The SDP clearly dominates for denser graphs, while the ILP approach is usually faster for sparse instances. However, even for such sparse graphs, the SDP solves more instances to optimality than the ILP. In fact, there is no single instance the ILP solved, which the SDP did not. Overall, our experiments reveal that for sparse graphs, one should usually try to find an optimal solution with the ILP first. If this approach does not solve the instance to optimality within reasonable time, the SDP still has a good chance to do so. Being able to solve larger real-world instances than reported before, we are also able to evaluate heuristics for this problem. In this paper we do so for the traditional barycenter-heuristic (showing that it leaves a large gap to the true optimum) and the state-of-the-art upward-planarization method (showing that it is usually close to the optimum).

Grothendieck inequalities are fundamental inequalities which are frequently used in many areas of mathematics and computer science. They can be interpreted as upper bounds for the integrality gap between two optimization problems: A difficult semidefinite program with rank-1 constraint and its easy semidefinite relaxation where the rank constrained is dropped. For instance, the integrality gap of the Goemans-Williamson approximation algorithm for MAX CUT can be seen as a Grothendieck inequality. In this tak I will consider Grothendieck inequalities for ranks greater than 1 and we give one application in statistical mechanics: Approximating ground states in the n-vector model. http://arxiv.org/abs/1011.1754 joint work with Jop Briet, Fernando Oliveira

We propose an algorithm for solving the maximum weighted stable set problem on claw-free graphs that runs in O(n^3)-time, drastically improving the previous best known complexity bound. This algorithm is based on a novel decomposition theorem for claw-free graphs, which we also present in this talk. Despite being weaker than the well-known structure result for claw-free graphs given by Chudnovsky and Seymour, our decomposition theorem is, on the other hand, algorithmic, i.e. it is coupled with an O(n^3)-time procedure that actually produces the decomposition. We also sketch some polyhedral consequences of this result. Joint work with Gianpaolo Oriolo and Gautier Stauffer (the slides will be updated later)

The pooling problem consists of finding the optimal quantity of final products to obtain by blending different compositions of raw materials in pools. Bilinear terms are required to model the quality of products in the pools, making the pooling problem a non-convex continuous optimization problem. In this work we study a generalization of the standard pooling problem where binary variables are used to model fixed costs associated with using a raw material in a pool. We derive four classes of strong valid inequalities for the problem and demonstrate that the inequalities dominate classic flow cover inequalities. The inequalities can be separated in polynomial time. Computational results are reported that demonstrate the utility of the inequalities when used in a global optimization solver. (joint work with J. Linderoth and J. Luedtke from University of Wisconsin - Madison)

In a seminal paper, Yannakakis (1991) proved that the minimum number of facets in an extended formulation of a given polytope is the non-negative rank of its slack matrix. He also obtained a subexponential size extended formulation for the stable set polytope of a perfect graph from a log^2(n) complexity deterministic communication protocol deciding the corresponding slack matrix. We show that the non-negative rank of a non-negative matrix is (up to small constants) determined by the minimum complexity of a randomized communication protocol computing the matrix on average. We then use this connection to prove novel conditional lower bounds on the sizes of extended formulations, in particular, for perfect matching polytopes. This is joint work with Michele Conforti, Yuri Faenza, Roland Grappe and Hans Raj Tiwary.

Branch-and-bound is a classical method to solve integer programming feasibility problems. On the theoretical side, it is considered inefficient: it can provably take an exponential number of nodes to prove the infeasibility of a simple integer program. In this work we show that branch-and-bound is surprisingly efficient from the theoretical viewpoint, if we apply a simple transformation in advance to the constraint matrix of the problem which makes the columns short and near orthogonal. We analyze two such reformulation methods, called the rangespace and the nullspace methods. We prove that if the coefficients of the problem are drawn from {1, ..., M} for a sufficiently large M, then for almost all such instances the number of subproblems that need to be enumerated by branch-and-bound is at most one. Besides giving an analysis of branch-and-bound, our main result generalizes a result of Furst and Kannan on the solvability of subset sum problems to bounded integer programs. We also present some numerical values of M which make sure that 90 and 99 percent of the reformulated problems solve at the root node. These values turned out to be surprisingly small for moderate values of n (the number of variables) and m (the number of constraints). This is joint work with Mustafa Tural (Columbia University) and Erick B. Wong (University of British Columbia).

We consider set covering problems where the underlying set system satisfies a particular replacement property w.r.t. a given partial order on the elements: Whenever a set is in the set system then a set stemming from it via the replacement of an element by a smaller element is also in the set system. Many variants of Bin Packing that have appeared in the literature are such set covering problems with ordered replacement. We provide a rigorous account on the additive and multiplicative integrality gap and approximability of set covering with replacement. In particular we provide a polylogarithmic upper bound on the additive integrality gap that also yields a polynomial time additive approximation algorithm if the linear programming relaxation can be efficiently solved. We furthermore present an extensive list of covering problems that fall into our framework and consequently have polylogarithmic additive gaps as well. Joint work with: Friedrich Eisenbrand, Naonori Kakimura, Thomas Rothvoß.

Let $G=(V,E)$ be a graph. A \textit{matching} is an edge subset of $E$ meeting each vertex at most once. A \textit{perfect matching} is a matching that meets exactly once each vertex. Conversely, an \textit{edge cover} is an edge subset of $E$ meeting each vertex at least once. From Jack Edmonds's pioneering work in polyhedral combinatorics, we know a complete and ``good'' linear description of the \textit{matching polytope} (the convex hull of the incidence vectors associated to matchings) and also the \textit{matching algorithm} (which finds maximum matching or minimum weight perfect matching). Similar results for edge cover can be proved by mainly using a result of Gallai which states that the sum of the cardinality of maximum matching and the cardinality of minimum edge cover is equal to $|V|$.\\ In this talk, we propose a generalization of matching and edge cover. Let $H$ be a family of odd subsets of $V$ which contains all the singletons of $V$ such that for any $U \cap W= \emptyset$ or $U \subseteq W$ or $W \subseteq U$ for all $U,W \in H$. Such an $H$ is called a \textit{odd laminar family}. We define an \textit{$H$-matching} as an edge subset of $E$ meeting each subset in $H$ at most once and an \textit{H-perfect matching} as an $H$-matching that meets exactly once each subset in $H$. Similarly, an \textit{$H$-edge cover} is an edge subset of $E$ meeting each subset in $H$ at least once. We can see that a matching (respectively an edge cover) in $v$ is an $H$-matching (respectively an $H$-edge cover) when $H$ is the family of the singletons in $V$. We give a complete characterization of the $H$-matching polytope as well as an $H$-matching algorithm. We derive then similar results for $H$-edge cover.\\ As an application of the above results, we consider the \textit{Minimum Weight Triangle Edge Cover Problem (MWTECP)} which aims to find a minimum weight edge subset meeting all triangles (cycles of length 3) in $G$. The problem is known to be $NP$-hard and approximation algorithms have been designed for only the unweighted case. We show that for the case when $G$ is planar, the MWTECP is equivalent to find a minimum weight $H$-edge cover in the dual graph of $G$ and hence can be solved in polynomial time.

Given an undirected graph G and set of pairs of vertices D, the SNDH problem consists in finding a minimum cost subgraph of G containing, for each d in D, K(d) edge-disjoint paths with length at most H(d) linking the pair of vertices in d. The input data K(d) control the desired level of survivability, while inputs H(d) are related to quality of service requirements. The existing formulation (hop-MCF) for this very general network design problem is based on multi-commodity flows, one for each demand over a suitable layered graph. This formulation is quite large and has integrality gaps in the range of 5% to 25% on the instances from the literature. This work proposes a new family of formulations called hop-level-MCF(L), having about (L+1) times more variables and constraints than hop-MCF = hop-level(0), the strength of the formulation increasing with L. It is remarkable that small values of L already yield much stronger formulations, the integrality gaps on the literature instances are in the range of 0% to 5%, allowing the solution of larger and harder instances. Joint work with A. Ridha Mahjoub and L. Simonetti

The Two-level Network Design (TLND) problem arises in the topological design of hierarchical communication, transportation, and electric power distribution networks. We are given two types of customers (primary and secondary), an additional set of Steiner nodes and fixed costs for installing either a primary or a secondary technology on each edge. The TLND problem seeks a minimum cost connected subgraph obeying a tree-tree topology, i.e., the primary nodes are connected by a rooted primary tree; the secondary nodes can be connected using both primary and secondary technology. In this talk we study an important extension of TLND in which additional transition costs need to be paid for {\em intermediate facilities} placed at the transition nodes, i.e., nodes where the change of technology takes place. We call this problem TLNDF. The introduction of transition node costs leads to a problem with a reach structure permitting us to put in evidence reformulation techniques such as modeling in higher dimensional graphs (which in this case are based on a node splitting technique). We first provide a compact way of modeling intermediate facilities. We then present several generalizations of the facility-based inequalities involving an exponential number of constraints. Finally we show how to model the problem in a more sophisticated graph based on node splitting. As the main result we show that connectivity constraints on the splitted graph, projected back into the original model, provide a new family of inequalities that implies, and even strictly dominates, all previously described constraints. We compare the proposed models both theoretically and computationally.

(Communication and transportation) Networks play a fundamental role in every-day life. In order to avoid congestion due to traffic fluctuations and traffic bottlenecks, network robustness is a crucial issue. Robustness however is often not addressed by the designer when installing the network. In this talk, we will address the robust network design problem. Let a directed network G=(V,E) be given. For k different network states (say: k different times of day) a traffic matrix is given that specifies for each pair of nodes the amount of unsplittable flow they need to exchange. The task is to determine the minimum-cost edge capacities such that the flow can be routed through the net at all times. We present an exact branch-and-cut algorithm for its solution. The solution approach is based on optimizing a non-linear objective function over flow variables. We show the method's effectiveness by presenting results on realistic instances. This is joint work with Christoph Buchheim and Laura Sanita.

The Kiel Canal connects the North and Baltic seas and is ranked among the world's three major canals. In terms of number of passages, it is the busiest artifical waterway in the world. Since free bi-directional ship traffic with current ship dimensions is not possible, passing and overtaking within the canal is constrained, depending on the size category of the respective ships and the meeting point. If a conflict occurs, ships have to wait at designated, capacitated places, so-called turnouts or sidings (just as in railroads). Hence, decisions must be taken about which ships have to wait where and for how long such that small passage times are guaranteed. This is currently done by experienced planners. In order to cope with the ever increasing traffic the canal and its bounding lock chambers are going to be enlarged. Therefore, advices about the effect of enlargement measurements and enlargement procedures are needed, which can be get by evaluating simulations of the ship traffic in different settings. In order to do so, interesting optimization problems must be solved. In this talk, developed models and algorithms enabling us to do the simulations, to indicate some bottlenecks within the canal and to get lower bounds will be presented.

Lagrangian decomposition is an indispensable tool for practical large scale optimization problems. Most classical parallelization approaches evaluate all subproblems in parallel for each update of the Lagrange multipliers. In contrast, we propose a bundle algorithm which selects dynamically disjoint subspaces of the dual variables along with subproblems influenced by these multipliers and optimizes over those subspaces asynchronously in parallel. Interdependencies between different subspaces that may endanger global convergence are detected automatically and are respected in future subspace selections. The basic algorithm is designed to handle loosely coupled problems in which most constraints act only on a small number of different subproblems. This is extended further to stronger coupled problems where the active influence of each multiplier during the run of the algorithm is traced dynamically. During the subspace selection only those subproblems are considered whose current optimal solution interacts with the active coupling constraints of the subspace. Preliminary numerical experiments on several test-instances show that the parallel bundle algorithm not only reduces the number of subproblem evaluations dramatically by more than a factor of ten but also produces solutions within a relative accuracy of $10^{-6}$ as opposed to only $10^{-3}$ for the traditional approach.

One step in a branch-and-bound-and-cut process is to describe an intermediate polyhedron P which is not explicitly defined (for example a disjunctive one) and we develop the basic theory for that. Facets of P are described by its polar but, when separation comes into play, it is rather the reverse polar of P that is involved. We discuss the pros and contras of both approaches. N.B.- If this talk is selected, I can speak any day (including Monday and Friday) but NOT on Wednesday, where I'll have to be in Grenoble. I am now attaching my slides