Integer Programming and Combinatorial Optimization

The best exact algorithms for the Capacitated Vehicle Routing Problem (CVRP) have been based on either branch-and-cut or Lagrangean relaxation/column generation. This paper presents an algorithm that combines both approaches: it works over the intersection of two polytopes, one associated with a traditional Lagrangean relaxation over q-routes, the other defined by bound, degree and capacity constraints. This is equivalent to a linear program with exponentially many variables and constraints that can lead to lower bounds that are superior to those given by previous methods. The resulting branch-and-cut-and-price algorithm can solve to optimality all instances from the literature with up to 135 vertices. This doubles the size of the instances that can be consistently solved.

Given a simple graph G(V,E) and a set of traffic demands between the nodes of G, the Network Loading Problem consists of installing minimum cost integer capacities on the edges of G allowing routing of the traffic demands.In this paper we study the Capacity Formulation of the Network Loading Problem, introducing the new class of the Tight Metric Inequalities, that completely characterize the convex hull of the integer feasible solutions of the problem. We present separation algorithms for Tight Metric Inequalities and a cutting plane algorithm, reporting on computational experience.

In this paper we use facets of the convex hull of mixed-integer sets with two and three variables to derive valid inequalities for integer sets defined by a single equation. These inequalities also define facets of the master cyclic group polyhedron of Gomory. In particular, our inequalities generalize the 2slope facets of Araoz, Gomory, Johnson and Evans (2003). In addition, they dominate the strong fractional cuts of Letchford and Lodi (2002).

In this paper we characterize the “price of anarchy”, i.e., the inefficiency between user and system optimal solutions, when costs are non-separable, asymmetric and nonlinear, generalizing earlier work that has addressed “the price of anarchy” under separable costs. This generalization models traffic equilibria, competitive multi-period pricing and competitive supply chains. The bounds established in this paper are tight and explicitly account for the degree of asymmetry and nonlinearity of the cost function. We introduce an alternate proof method for providing bounds that uses ideas from semidefinite optimization. Finally, in the context of multi-period pricing our analysis establishes that user and system optimal solutions coincide.

We study the problem of minimizing the maximum latency of flows in networks with congestion. We show that this problem is NP-hard, even when all arc latency functions are linear and there is a single source and sink. Still, one can prove that an optimal flow and an equilibrium flow share a desirable property in this situation: all flow-carrying paths have the same length; i.e., these solutions are “fair,” which is in general not true for the optimal flow in networks with nonlinear latency functions. In addition, the maximum latency of the Nash equilibrium, which can be computed efficiently, is within a constant factor of that of an optimal solution. That is, the so-called price of anarchy is bounded. In contrast, we present a family of instances that shows that the price of anarchy is unbounded for instances with multiple sources and a single sink, even in networks with linear latencies. Finally, we show that an s-t-flow that is optimal with respect to the average latency objective is near optimal for the maximum latency objective, and it is close to being fair. Conversely, the average latency of a flow minimizing the maximum latency is also within a constant factor of that of a flow minimizing the average latency.

The problem of finding the value and optimal strategies of players in cyclic games is studied. A polynomial time algorithm for solving cyclic games is proposed.

We propose a general methodology based on robust optimization to address the problem of optimally controlling a supply chain subject to stochastic demand in discrete time. The attractive features of the proposed approach are: (a) It incorporates a wide variety of phenomena, including demands that are not identically distributed over time and capacity on the echelons and links; (b) it uses very little information on the demand distributions; (c) it leads to qualitatively similar optimal policies (basestock policies) as in dynamic programming; (d) it is numerically tractable for large scale supply chain problems even in networks, where dynamic programming methods face serious dimensionality problems; (e) in preliminary computational experiments, it often outperforms dynamic programming based solutions for a wide range of parameters.

We study the design of approximation algorithms for stochastic combinatorial optimization problems. We formulate the problems in the framework of two-stage stochastic optimization, and provide nearly tight approximations. Our problems range from the simple (shortest path, vertex cover, bin packing) to complex (facility location, set cover), and contain representatives with different approximation ratios.The approximation ratio of the stochastic variant of a typical problem is of the same order of magnitude as its deterministic counterpart. Furthermore, common techniques for designing approximation algorithms such as LP rounding, the primal-dual method, and the greedy algorithm, can be carefully adapted to obtain these results.

Managing an industrial production facility requires carefully allocating limited resources, and gives rise to large, potentially complicated scheduling problems. In this paper we consider a specific instance of such a problem: planning efficient utilization of the facilities and technicians that maintain the United States nuclear stockpile. A detailed study of this problem yields a complicated mixed-integer programming (MIP) model with upward of hundreds of thousands of variables and even more constraints. Consistently and quickly solving such a model exactly is impossible using today’s algorithms and computers, and, in addition to branch-and-bound, requires good heuristics and approximation algorithms. In an effort to design such algorithms, we study several different methods of generating good solutions given the solution to the LP relaxation. We design a suite of sample data and test the algorithms.The goals of this project were twofold. First, we wanted to develop a program that could efficiently and accurately help with the Pantex planning problem. Second, we wanted to experimentally test various ideas, designed originally for “cleaner” problems, in this more challenging context. In summary, we demonstrate the value of using α-points as a way to quickly and cheaply generate, from one solution of an LP relaxation, many feasible solutions to an integer program. In this particular environment, the use of α-points, combined with other heuristics, outperforms local search. We also see the value of finding combinatorially-structured subproblems as opposed to using simple greedy approaches.

In 1963, Tibor Gallai [9] asked whether every strongly connected directed graph D is spanned by α directed circuits, where α is the stability of D. We give a proof of this conjecture using a new structure for digraphs called cyclic orders. Three min-max theorems for cyclic orders are derived.

We give a TDI description for a class of polytopes, which corresponds to a restricted 2-matching problem. The perfect matching polytope, triangle-free perfect 2-matching polytope and relaxations of the travelling salesman polytope are members of this class. The paper shows that 2-matching problems for which the unweighted problem was known to be tractable, the weighted is also tractable.

We consider the problems of enumerating all minimal strongly connected subgraphs and all minimal dicuts of a given directed graph G=(V,E). We show that the first of these problems can be solved in incremental polynomial time, while the second problem is NP-hard: given a collection of minimal dicuts for G, it is NP-complete to tell whether it can be extended. The latter result implies, in particular, that for a given set of points ${\mathcal A}\subseteq{\mathbb R}^n$, it is NP-hard to generate all maximal subsets of ${\mathcal A}$ contained in a closed half-space through the origin. We also discuss the enumeration of all minimal subsets of ${\mathcal A}$ whose convex hull contains the origin as an interior point, and show that this problem includes as a special case the well-known hypergraph transversal problem.

We study the convex hull of the feasible set of the semi-continuous knapsack problem, in which the variables belong to the union of two intervals. Besides being important in its own right, the semi-continuous knapsack problem is a relaxation of general mixed-integer programming. We show how strong inequalities that are valid for the semi-continuous knapsack polyhedron can be derived and used as cuts in a branch-and-cut scheme for mixed-integer programming and problems with semi-continuous variables. We present computational results that demonstrate the effectiveness of these inequalities, which we call collectively semi-continuous cuts. Our computational experience also shows that dealing with semi-continuous constraints directly in the branch-and-cut algorithm through a specialized branching scheme and semi-continuous cuts is considerably more practical than the “textbook” approach of modeling semi-continuous constraints through the introduction of auxiliary binary variables in the model.

Mixed-Integer Programs (MIP’s) involving logical implications modelled through big-M coefficients, are notoriously among the hardest to solve. In this paper we propose and analyze computationally an automatic problem reformulation of quite general applicability, aimed at removing the model dependency on the big-M coefficients. Our solution scheme defines a master Integer Linear Problem (ILP) with no continuous variables, which contains combinatorial information on the integer-variable feasible combinations that can be “distilled” from the original MIP model. The master solutions are sent to a slave Linear Program (LP), which validates them and possibly returns combinatorial inequalities to be added to the current master ILP. The inequalities are associated to minimal (or irreducible) infeasible subsystems of a certain linear system, and can be separated efficiently in case the master solution is integer. This produces an LP relaxation of the master problem which can be considerably tighter than the one associated with original MIP formulation. Computational results on two specific classes of hard-to-solve MIP’s indicate the new method produces a reformulation which can be solved some orders of magnitude faster than the original MIP model.

In 1982, Padberg and Rao gave a polynomial-time separation algorithm for b-matching polyhedra. The current best known implementations of their separation algorithm run in ${\cal O}(|V|^2|E| \log (|V|^2/|E|))$ time when there are no edge capacities, but in ${\cal O}(|V||E|^2 \log (|V|^2/|E|))$ time when capacities are present.We propose a new exact separation algorithm for the capacitated case which has the same running time as for the uncapacitated case. For the sake of brevity, however, we will restrict our introduction to the case of perfect 1-capacitated b-matchings, which includes, for example, the separation problem for perfect 2-matchings. As well as being faster than the Padberg-Rao approach, our new algorithm is simpler and easier to implement.

There has been a great deal of recent work on approximation algorithms for facility location problems [9]. We consider the capacitated facility location problem with hard capacities. We are given a set of facilities, ${\mathcal F}$, and a set of clients ${\mathcal D}$ in a common metric space. Each facility i has a facility opening costf _i and capacityu _i that specifies the maximum number of clients that may be assigned to this facility. We want to open some facilities from the set ${\mathcal F}$ and assign each client to an open facility so that at most u _i clients are assigned to any open facility i. The cost of assigning client j to facility i is given by their distance c _ij , and our goal is to minimize the sum of the facility opening costs and the client assignment costs.

We present a multi-exchange local search algorithm for approximating the capacitated facility location problem (CFLP), where a new local improvement operation is introduced that possibly exchanges multiple facilities simultaneously. We give a tight analysis for our algorithm and show that the performance guarantee of the algorithm is between $3+2\sqrt{2}-\epsilon$ and $3+2\sqrt{2}+\epsilon$ for any given constant ε> 0. Previously known best approximation ratio for the CFLP is 7.88, due to Mahdian and Pál (2003), based on the operations proposed by Pál, Tardos and Wexler (2001). Our upper bound $3+2\sqrt{2}+\epsilon$ also matches the best known ratio, obtained by Chudak and Williamson (1999), for the CFLP with uniform capacities. In order to obtain the tight bound of our new algorithm, we make interesting use of the notion of exchange graph of Pál et al. and techniques from the area of parallel machine scheduling.

We show how to approximate a separable concave minimization problem over a general closed ground set by a single piecewise linear minimization problem. The approximation is to arbitrary 1+ε precision in optimal cost. For polyhedral ground sets in $\mathbb{R}^n_+$ and nondecreasing cost functions, the number of pieces is polynomial in the input size and proportional to 1/log(1+ε). For general polyhedra, the number of pieces is polynomial in the input size and the size of the zeroes of the concave objective components.We illustrate our approach on the concave-cost uncapacitated multicommodity flow problem. By formulating the resulting piecewise linear approximation problem as a fixed charge, mixed integer model and using a dual ascent solution procedure, we solve randomly generated instances to within five to twenty percent of guaranteed optimality. The problem instances contain up to 50 nodes, 500 edges, 1,225 commodities, and 1,250,000 flow variables.

This paper presents three kinds of algebraic-analytic algorithms for solving integer and mixed integer programming problems. We report both theoretical and experimental results. We use the generating function techniques introduced by A. Barvinok.

We prove Edmonds-Gallai type structure theorems for Mader’s edge- and vertex-disjoint paths including also capacitated variants, and state a conjecture generalizing Mader’s minimax theorems on path packings and Cunningham and Geelen’s path-matching theorem.

We further develop the 0/1 ILP formulation of Lee for edge coloring where colors are encoded in binary. With respect to that formulation, our main contributions are: (i) an efficient separation algorithm for general block inequalities, (ii) an efficient LP-based separation algorithm for stars (i.e., the all-different polytope), (iii) introduction of matching inequalities, and (iv) introduction of switched path inequalities and their efficient separation, (v) a complete description for paths, (vi) promising computational results.

We discuss the problem of sequencing precedence-constrained jobs on a single machine to minimize the average weighted completion time. This problem has attracted much attention in the mathematical programming community since Sidney’s pioneering work in 1975. We look at the problem from a polyhedral perspective and uncover a relation between Sidney’s decomposition theorem and different linear programming relaxations. More specifically, we present a generalization of Sidney’s result, which particularly allows us to reason that virtually all known 2-approximation algorithms comply with his decomposition. Moreover, we establish a connection between the single-machine scheduling problem and the vertex cover problem. Indeed, in the special case of series-parallel precedence constraints, we prove that the sequencing problem can be seen as a special case of vertex cover. We also argue that this result is true for general precedence constraints if one can show that a certain integer program represents a valid formulation of the sequencing problem. Finally, we provide a characterization of the active inequalities of a linear programming relaxation in completion time variables.

We consider the problem of minimizing the weighted sum of job completion times on a single machine (subject to certain job weights) with an additional side constraint on the weighted sum of job completion times (with respect to different job weights). This problem is NP-hard, and we provide a polynomial time approximation scheme for this problem. Our method is based on Lagrangian relaxation mixed with carefully guessing the positions of certain jobs in the schedule.

We propose the first theoretical approach to global routing that takes coupling between adjacent wires, bounds on delays along critical paths, and overall capacitance (power consumption) into account. It consists of an efficient combinatorial fully polynomial approximation scheme to a fractional relaxation, followed by randomized rounding. The overall deviation from the optimum can be bounded. The model could also be used for routing traffic flows with congestion-dependent travel times.

We discuss the Max-flow Quotient-cut Improvement (MQI) algorithm, a flow-based method for improving graph cuts when cut quality is measured by quotient-style metrics such as expansion or conductance. Given a cut $(S,\overline{S})$, this algorithm finds the best improvement among all cuts $(S',\overline{S'})$ such that S′ is a strict subset of S. This idea has already been used by theorists to give improved bounds for graph bisection and for finding hierarchical oblivous routing schemes. Here we investigate the practical utility of the idea and find that MQI can be combined with Metis to obtain a heuristic graph partitioner that does an extremely good job on classic benchmark graphs, VLSI circuits, and four different tasks from the Information Retrieval domain. We also find empirically that Metis+MQI runs in nearly linear time, so it is applicable to very large problems.

We show that any rational polytope is polynomial-time representable as a “slim” r× c × 3 three-way line-sum transportation polytope. This universality theorem has important consequences for linear and integer programming and for confidential statistical data disclosure.It provides polynomial-time embedding of arbitrary linear programs and integer programs in such slim transportation programs and in bipartite biflow programs. It resolves several standing problems on 3-way transportation polytopes. It demonstrates that the range of values an entry can attain in any slim 3-way contingency table with specified 2-margins can contain arbitrary gaps, suggesting that disclosure of k-margins of d-tables for 2≤ k<d is confidential.Our construction also provides a powerful tool in studying concrete questions about transportation polytopes and contingency tables; remarkably, it enables to automatically recover the famous “real-feasible integer-infeasible” 6× 4× 3 transportation polytope of M. Vlach, and to produce the first example of 2-margins for 6× 4× 3 contingency tables where the range of values a specified entry can attain has a gap.

This paper presents a faster algorithm for the M-convex submodular flow problem, which is a generalization of the minimum-cost flow problem with an M-convex cost function for the flow-boundary, where an M-convex function is a nonlinear nonseparable discrete convex function on integer points. The algorithm extends the capacity scaling approach for the submodular flow problem by Fleischer, Iwata and McCormick (2002) with the aid of a novel technique of changing the potential by solving maximum submodular flow problems.

A convex triangular grid is a planar digraph G embedded in the plane so that each bounded face is an equilateral triangle with three edges and their union ${\cal R}$ forms a convex polygon. A function $h:E(G)\to{\mathbb R}$ is called a concave cocirculation if h(e)=g(v)–g(u) for each edge e=(u,v), where g is a concave function on ${\cal R}$ which is affinely linear within each bounded face of G. Knutson and Tao obtained an integrality result on so-called honeycombs implying that if an integer-valued function on the boundary edges is extendable to a concave cocirculation, then it is extendable to an integer one.We show a sharper property: for any concave cocirculation h, there exists an integer concave cocirculation h′ satisfying h′(e)=h(e) for each edge e with $h(e)\in{\mathbb Z}$ contained in the boundary or in a bounded face where h is integer on all edges.Also relevant polyhedral and algorithmic results are presented.

We provide a polynomial algorithm that determines for any given undirected graph, positive integer k and various objective functions on the edges or on the degree sequences, as input, k edges that minimize the given objective function. The tractable objective functions include linear, sum of squares, etc. The source of our motivation and at the same time our main application is a subset of k vertices in a line graph, that cover as many edges as possible (maxfix cover). Besides the general algorithm and connections to other problems, the extension of the usual improving paths for graph factors could be interesting in itself: the objects that take the role of the improving walks for b-matchings or other general factorization problems turn out to be edge-disjoint unions of pairs of alternating walks. The algorithm we suggest also works if for any subset of vertices upper, lower bound constraints or parity constraints are given. In particular maximum (or minimum) weight b-matchings of given size can be determined in polynomial time, combinatorially, in more than one way.

Let P be a random 0/1-polytope in ℝd with n(d) vertices, and denote by ϕ _k (P) the k-face density of P, i.e., the quotient of the number of k-dimensional faces of P and $\binom{n(d)}{k+1}$. For each k≥ 2, we establish the existence of a sharp threshold for the k-face density and determine the values of the threshold numbers τ _k such that, for all ε> 0, $$ {\mathbb{E}}[\varphi_k(P)]\ =\ \begin{cases} 1-{\mathrm o}(1) & \text{ if $n(d)\le 2^{(\tau_k-\varepsilon)d}$ for all~$d$} \\ {\mathrm o}(1) & \text{ if $n(d)\ge 2^{(\tau_k+\varepsilon)d}$ for all~$d$} \\ \end{cases} $$ holds for the expected value of ϕ _k (P). The threshold for k=1 has recently been determined in [1].In particular, these results indicate that the high face densities often encountered in polyhedral combinatorics (e.g., for the cut-polytopes of complete graphs) should be considered more as a phenomenon of the general geometry of 0/1-polytopes than as a feature of the special combinatorics of the underlying problems.

As a common generalization of matchings and matroid intersection, W.H. Cunningham and J.F. Geelen introduced the notion of path-matching, which they generalized even further by introducing even factors of weakly symmetric digraphs. Later, a purely combinatorial approach to even factors was given by Gy. Pap and L. Szegő, who showed that the maximum even factor problem remains tractable in the class of hardly symmetric digraphs. The present paper shows a direct polyhedral way to derive weighted integer min-max formulae generalizing those previous results.

Let G=(V,E) be a complete graph. Then the semimetric polytope${\cal M}(G)$ associated with G is defined by the following system of inequalities called the triangle inequalities.