Search

In this paper we reconsider a known technique for constructing strong MIP formulations for disjunctive constraints of the form x ∈ ⋃ i = 1 m P i , where the P i are polytopes. The formulation is based on the Cayley Embedding of the union of polytopes, namely, Q : = conv (⋃ i = 1 m P i × { ϵ i }) , where ϵ i is the ith unit vector in R m . Our main contribution is a full characterization of the facets of Q, provided it has a certain network representation. In the second half of the paper, we work-out a number of applications from the literature, e.g., special ordered sets of type 2, logical constraints, the cardinality indicating polytope, union of simplicies, etc., along with a more complex recent example. Furthermore, we describe a new formulation for piecewise linear functions defined on a grid triangulation of a rectangular region D ⊂ R d using a logarithmic number of auxilirary variables in the number of gridpoints in D for any fixed d. The series of applications demonstrates the richness of the class of disjunctive constraints for which our method can be applied. [ABSTRACT FROM AUTHOR]

Given polyhedron P and and a point x ∗ , the separation problem for polyhedra asks to certify that x ∗ ∈ P and if not, to determine an inequality that is satisfied by P and violated by x ∗ . This problem is repeatedly solved in cutting plane methods for Integer Programming and the quality of the violated inequality is an essential feature in the performance of such methods. In this paper we address the problem of finding efficiently an inequality that is violated by x ∗ and either defines an improper face or a facet of P. We show that, by solving a single linear program, one almost surely obtains such an improper face or facet. [ABSTRACT FROM AUTHOR]

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

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

The Maximum Benefit Chinese Postman Problem (MBCPP) is an NP-hard problem that considers several benefits associated with each edge, one for each time the edge is traversed with a service. The objective is to find a closed walk with maximum benefit. We propose an IP formulation for the undirected MBCPP and, based on the description of its associated polyhedron, we propose a branch-and-cut algorithm and present computational results on instances with up to 1,000 vertices and 3,000 edges. [ABSTRACT FROM AUTHOR]

The mixing set with a knapsack constraint arises in deterministic equivalent of chance-constrained programming problems with finite discrete distributions. We first consider the case that the chance-constrained program has equal probabilities for each scenario. We study the resulting mixing set with a cardinality constraint and propose facet-defining inequalities that subsume known explicit inequalities for this set. We extend these inequalities to obtain valid inequalities for the mixing set with a knapsack constraint. In addition, we propose a compact extended reformulation (with polynomial number of variables and constraints) that characterizes a linear programming equivalent of a single chance constraint with equal scenario probabilities. We introduce a blending procedure to find valid inequalities for intersection of multiple mixing sets. We propose a polynomial-size extended formulation for the intersection of multiple mixing sets with a knapsack constraint that is stronger than the original mixing formulation. We also give a compact extended linear program for the intersection of multiple mixing sets and a cardinality constraint for a special case. We illustrate the effectiveness of the proposed inequalities in our computational experiments with probabilistic lot-sizing problems. [ABSTRACT FROM AUTHOR]

In this paper, we study the Windy Postman Problem (WPP). This is a well-known Arc Routing Problem that contains the Mixed Chinese Postman Problem (MCPP) as a special case. We extend to arbitrary dimension some new inequalities that complete the description of the polyhedron associated with the Windy Postman Problem over graphs with up to four vertices and ten edges. We introduce two new families of facet-inducing inequalities and prove that these inequalities, along with the already known odd zigzag inequalities, are Chvátal-Gomory inequalities of rank at most 2. Moreover, a branch-and-cut algorithm that incorporates two new separation algorithms for all the previously mentioned inequalities and a new heuristic procedure to obtain upper bounds are presented. Finally, the performance of a branch-and-cut algorithm over several sets of large WPP and MCPP instances, with up to 3,000 nodes and 9,000 edges (and arcs in the MCPP case), shows that, to our knowledge, this is the best algorithm to date for the exact resolution of the WPP and the MCPP. [ABSTRACT FROM AUTHOR]

The polyhedral structure of the K-median problem is examined. We present an extended formulation that is integral but grows exponentially with the number of nodes. Then, some extra variables are projected out. Based on the reduced formulation, we develop two basic properties for facets of K-median problem. By applying the two properties, we generalize two known classes of facets, de Vries facets and de Farias facets. The computational study illustrates that the generalization is significant. [ABSTRACT FROM AUTHOR]

We introduce a new class of second-order cover inequalities whose members are generally stronger than the classical knapsack cover inequalities that are commonly used to enhance the performance of branch-and-cut methods for 0–1 integer programming problems. These inequalities result by focusing attention on a single knapsack constraint in addition to an inequality that bounds the sum of all variables, or in general, that bounds a linear form containing only the coefficients 0, 1, and –1. We provide an algorithm that generates all non-dominated second-order cover inequalities, making use of theorems on dominance relationships to bypass the examination of many dominated alternatives. Furthermore, we derive conditions under which these non-dominated second-order cover inequalities would be facets of the convex hull of feasible solutions to the parent constraints, and demonstrate how they can be lifted otherwise. Numerical examples of applying the algorithm disclose its ability to generate valid inequalities that are sometimes significantly stronger than those derived from traditional knapsack covers. Our results can also be extended to incorporate multiple choice inequalities that limit sums over disjoint subsets of variables to be at most one. [ABSTRACT FROM AUTHOR]

The polyhedral structure of the K-median problem on a tree is examined. Even for very small connected graphs, we show that additional constraints are needed to describe the integer polytope. A complete description is given of those trees for which an optimal integer LP solution is guaranteed to exist. We present a new and simpler demonstration that an LP characterization of the 2-median problem is complete. Also, we provide a simpler proof of the value of a tight worst case bound for the LP relaxation. A new class of valid inequalities is identified. These inequalities describe a subclass of facets for the K-median problem on a general graph. Also, we provide polyhedral descriptions for several types of trees. As part of this work, we summarize most known results for the K-median problem on a tree. [ABSTRACT FROM AUTHOR]

The Graphical Traveling Salesman Polyhedron (GTSP) has been proposed by Naddef and Rinaldi to be viewed as a relaxation of the Symmetric Traveling Salesman Polytope (STSP). It has also been employed by Applegate, Bixby, Chvátal, and Cook for solving the latter to optimality by the branch-and-cut method. There is a close natural connection between the two polyhedra. Until now, it was not known whether there are facets in TT-form of the GTSP polyhedron which are not facets of the STSP polytope as well. In this paper we give an affirmative answer to this question for n ≥ 9. We provide a general method for proving the existence of such facets, at the core of which lies the construction of a continuous curve on a polyhedron. This curve starts in a vertex, walks along edges, and ends in a vertex not adjacent to the starting vertex. Thus there must have been a third vertex on the way. [ABSTRACT FROM AUTHOR]

In this paper we introduce a new class of facet-inducing inequalities for the Windy Rural Postman Problem and the Windy General Routing Problem. These inequalities are called Zigzag inequalities because they cut off fractional solutions containing a zigzag associated with variables with 0.5 value. Two different types of inequalities, the Odd Zigzag and the Even Zigzag inequalities, are presented. Finally, their application to other known Arc Routing Problems is discussed. [ABSTRACT FROM AUTHOR]

We consider the polyhedral approach to solving the capacitated facility location problem. The valid inequalities considered are the knapsack cover, flow cover, effective capacity, single depot, and combinatorial inequalities. The flow cover, effective capacity and single depot inequalities form subfamilies of the general family of submodular inequalities. The separation problem based on the family of submodular inequalities is NP-hard in general. For the well known subclass of flow cover inequalities, however, we show that if the client set is fixed, and if all capacities are equal, then the separation problem can be solved in polynomial time. For the flow cover inequalities based on an arbitrary client set and general capacities, and for the effective capacity and single depot inequalities we develop separation heuristics. An important part of these heuristics is based on the result that two specific conditions are necessary for the effective cover inequalities to be facet defining. The way these results are stated indicates precisely how structures that violate the two conditions can be modified to produce stronger inequalities. The family of combinatorial inequalities was originally developed for the uncapacitated facility location problem, but is also valid for the capacitated problem. No computational experience using the combinatorial inequalities has been reported so far. Here we suggest how partial output from the heuristic identifying violated submodular inequalities can be used as input to a heuristic identifying violated combinatorial inequalities. We report on computational results from solving 60 medium size problems. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V. [ABSTRACT FROM AUTHOR]

This paper deals with the 0/1 knapsack polytope. In particular, we introduce the class of weight inequalities. This class of inequalities is needed to describe the knapsack polyhedron when the weights of the items lie in certain intervals. A generalization of weight inequalities yields the so-called “weight-reduction principle” and the class of extended weight inequalities. The latter class of inequalities includes minimal cover and (l, k)-configuration inequalities. The properties of lifted minimal cover inequalities are extended to this general class of inequalities. [ABSTRACT FROM AUTHOR]

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

Let G=( V, E) be a graph and T⊆ V be a node set. We call an edge set S a Steiner tree for T if S connects all pairs of nodes in T. In this paper we address the following problem, which we call the weighted Steiner tree packing problem. Given a graph G=( V, E) with edge weights w , edge capacities c , e∈ E, and node set T ,..., T , find edge sets S ,..., S such that each S is a Steiner tree for T , at most c of these edge sets use edge e for each e∈ E, and the sum of the weights of the edge sets is minimal. Our motivation for studying this problem arises from a routing problem in VLSI-design, where given sets of points have to be connected by wires. We consider the Steiner tree packing problem from a polyhedral point of view and define an associated polyhedron, called the Steiner tree packing polyhedron. The goal of this paper is to (partially) describe this polyhedron by means of inequalities. It turns out that, under mild assumptions, each inequality that defines a facet for the (single) Steiner tree polyhedron can be lifted to a facet-defining inequality for the Steiner tree packing polyhedron. The main emphasis of this paper lies on the presentation of so-called joint inequalities that are valid and facet-defining for this polyhedron. Inequalities of this kind involve at least two Steiner trees. The classes of inequalities we have found form the basis of a branch & cut algorithm. This algorithm is described in our companion paper (in this issue). [ABSTRACT FROM AUTHOR]

Many applications of the traveling salesman problem require the introduction of additional constraints. One of the most frequently occurring classes of such constraints are those requiring that certain cities be visited before others (precedence constraints). In this paper we study the Precedence-Constrained Asymmetric Traveling Salesman (PCATS) polytope, i.e. the convex hull of incidence vectors of tours in a precedence-constrained directed graph. We derive several families of valid inequalities, and give polynomial time separation algorithms for important subfamilies. We then establish the dimension of the PCATS polytope and show that, under reasonable assumptions, the two main classes of inequalities derived are facet inducing. [ABSTRACT FROM AUTHOR]

In this paper we give some integer programming formulations for the Steiner tree problem on undirected and directed graphs and study the associated polyhedra. We give some families of facets for the undirected case along with some compositions and extensions. We also give a projection that relates the Steiner tree polyhedron on an undirected graph to the polyhedron for the corresponding directed graph. This is used to show that the LP-relaxation of the directed formulation is superior to the LP-relaxation of the undirected one. [ABSTRACT FROM AUTHOR]

This paper studies the problem of finding a two-edge connected spanning subgraph of minimum weight. This problem is closely related to the widely studied traveling salesman problem and has applications to the design of reliable communication and transportation networks. We discuss the polytope associated with the solutions to this problem. We show that when the graph is series-parallel, the polytope is completely described by the trivial constraints and the so-called cut constraints. We also give some classes of facet defining inequalities of this polytope when the graph is general. [ABSTRACT FROM AUTHOR]

This is the second part of two papers addressing the study of the facial structure of the Steiner tree polyhedron. In this paper we identify several classes of facet defining inequalities and relate them to special classes of graphs on which the Steiner tree problem is known to be NP-hard. [ABSTRACT FROM AUTHOR]

We consider the vertex-weighted version of the undirected Steiner tree problem. In this problem, a cost is incurred both for the vertices and the edges present in the Steiner tree. We completely describe the associated polytope by linear inequalities when the underlying graph is series-parallel. For general graphs, this formulation can be interpreted as a (partial) extended formulation for the Steiner tree problem. By projecting this formulation, we obtain some very large classes of facet-defining valid inequalities for the Steiner tree polytope. [ABSTRACT FROM AUTHOR]

The Gale-Hoffman inequalities characterize feasible external flow in a (capacitated) network. Among these inequalities, those that are redundant can be identified through a simple arc-connectedness criterion. [ABSTRACT FROM AUTHOR]

The network loading problem (NLP) is a specialized capacitated network design problem in which prescribed point-to-point demand between various pairs of nodes of a network must be met by installing (loading) a capacitated facility. We can load any number of units of the facility on each of the arcs at a specified arc dependent cost. The problem is to determine the number of facilities to be loaded on the arcs that will satisfy the given demand at minimum cost. This paper studies two core subproblems of the NLP. The first problem, motivated by a Lagrangian relaxation approach for solving the problem, considers a multiple commodity, single arc capacitated network design problem. The second problem is a three node network; this specialized network arises in larger networks if we aggregate nodes. In both cases, we develop families of facets and completely characterize the convex hull of feasible solutions to the integer programming formulation of the problems. These results in turn strengthen the formulation of the NLP. [ABSTRACT FROM AUTHOR]

The Steiner arborescence (or Steiner directed tree) problem concerns the connection of a set of target vertices of a digraph to a given root vertex. This problem is known to be NP-hard. In the present paper we study the facial structure of two polyhedra associated with the problem. Several classes of valid inequalities are considered, and a new class with arbitrarily large coefficients is introduced. All these inequalities are shown to define distinct facets of both the Steiner polyhedra considered. This is achieved by exploiting two lifting theorems which also allow generalization of the new inequalities. Composition theorems are finally given and used to derive large families of new facet-inducing inequalities with exponentially large coefficients. [ABSTRACT FROM AUTHOR]

Several procedures for the identification of facet inducing inequalities for the symmetric traveling salesman polytope are given. An identification procedure accepts as input the support graph of a point which does not belong to the polytope, and returns as output some of the facet inducing inequalities violated by the point. A procedure which always accomplishes this task is called exact, otherwise it is called heuristic. We give exact procedures for the subtour elimination and the 2-matching constraints, based on the Gomory-Hu and Padberg-Rao algorithms respectively. Efficient reduction procedures for the input graph are proposed which accelerate these two algorithms substantially. Exact and heuristic shrinking conditions for the input graph are also given that yield efficient procedures for the identification of simple and general comb inequalities and of some elementary clique tree inequalities. These procedures constitute the core of a polytopal cutting plane algorithm that we have devised and programmed to solve a substantial number of large-scale problem instances with sizes up to 2392 nodes to optimality. [ABSTRACT FROM AUTHOR]

Three classes of valid inequalities based upon multiple knapsack constraints are derived for the generalized assignment problem. General properties of the facet defining inequalities are discussed and, for a special case, the convex hull is completely characterized. In addition, we prove that a basic fractional solution to the linear programming relaxation can be eliminated by a facet defining inequality associated with an individual knapsack constraint. [ABSTRACT FROM AUTHOR]

class of facet defining inequalities for the generalized assignment problem is derived. These inequalities are based upon multiple knapsack constraints and are derived from (1, k)-configuration inequalities. [ABSTRACT FROM AUTHOR]

We consider ternary matrices, i.e., integer matrices having all entries 0, 1 or 2. Three associated problems-the group problem, covering, and packing-are studied. General classes of vertices and facets are discussed in each case. Certain lifting procedures are also described. For all three problems techniques used are natural extensions of those used in the binary case. [ABSTRACT FROM AUTHOR]

We study unconstrained quadratic zero-one programming problems having n variables from a polyhedral point of view by considering the Boolean quadric polytope QP in n( n+1)/2 dimensions that results from the linearization of the quadratic form. We show that QP has a diameter of one, descriptively identify three families of facets of QP and show that QP is symmetric in the sense that all facets of QP can be obtained from those that contain the origin by way of a mapping. The naive linear programming relaxation QP of QP is shown to possess the Trubin-property and its extreme points are shown to be {0,1/2,1}-valued. Furthermore, O( n) facet-defining inequalities of QP suffice to cut off all fractional vertices of QP, whereas the family of facets described by us has at least O(3) members. The problem is also studied for sparse quadratic forms (i.e. when several or many coefficients are zero) and conditions are given for the previous results to carry over to this case. Polynomially solvable problem instances are discussed and it is shown that the known polynomiality result for the maximization of nonnegative quadratic forms can be obtained by simply rounding the solution to the linear programming relaxation. In the case that the graph induced by the nonzero coefficients of the quadratic form is series-parallel, a complete linear description of the associated Boolean quadric polytope is given. The relationship of the Boolean quadric polytope associated to sparse quadratic forms with the vertex-packing polytope is discussed as well. [ABSTRACT FROM AUTHOR]

We present computational experience with a cutting plane algorithm for 0-1 quadratic programming without constraints. Our approach is based on a reduction of this problem to a max-cut problem in a graph and on a partial linear description of the cut polytope. [ABSTRACT FROM AUTHOR]

While the set packing polytope, through its connection with vertex packing, has lent itself to fruitful investigations, little is known about the set covering polytope. We characterize the class of valid inequalities for the set covering polytope with coefficients equal to 0, 1 or 2, and give necessary and sufficient conditions for such an inequality to be minimal and to be facet defining. We show that all inequalities in the above class are contained in the elementary closure of the constraint set, and that 2 is the largest value of k such that all valid inequalities for the set covering polytope with integer coefficients no greater than k are contained in the elementary closure. We point out a connection between minimal inequalities in the class investigated and certain circulant submatrices of the coefficient matrix. Finally, we discuss conditions for an inequality to cut off a fractional solution to the linear programming relaxation of the set covering problem and to improve the lower bound given by a feasible solution to the dual of the linear programming relaxation. [ABSTRACT FROM AUTHOR]

A comprehensive class of cutting planes for the symmetric travelling salesman problem (TSP) is proposed which contains the known 'comb inequalities', the 'path inequalities' and the '3-star constraints' as special cases. Its relation to the 'clique tree inequalities' is discussed. The cutting planes are shown to be valid for a relaxed version of the TSP, the travelling salesman problem on a road network, and-under certain conditions-to define facets of the polyhedron associated with this problem. [ABSTRACT FROM AUTHOR]

We relate the simple plant location problem to the vertex packing problem and derive several classes of facets of their associated integer polytopes. [ABSTRACT FROM AUTHOR]

A new class of facets for knapsack polytopes is obtained. This class of inequalities is shown to define a polytope with zero-one vertices only. A combinatorial inequality is obtained from Fulkerson's max-max inequality. [ABSTRACT FROM AUTHOR]

We investigate several classes of inequalities for the symmetric travelling salesman problem with respect to their facet-defining properties for the associated polytope. A new class of inequalities called comb inequalities is derived and their number shown to grow much faster with the number of cities than the exponentially growing number of subtour-elimination constraints. The dimension of the travelling salesman polytope is calculated and several inequalities are shown to define facets of the polytope. In part II ('On the travelling salesman problem II: Lifting theorems and facets') we prove that all subtour-elimination and all comb inequalities define facets of the symmetric travelling salesman polytope. [ABSTRACT FROM AUTHOR]

Four lifting theorems are derived for the symmetric travelling salesman polytope. They provide constructions and state conditions under which a linear inequality which defines a facet of the n-city travelling salesman polytope retains its facetial property for the ( n + m)-city travelling salesman polytope, where m ≥ 1 is an arbitrary integer. In particular, they permit a proof that all subtour-elimination as well as comb inequalities define facets of the convex hull of tours of the n-city travelling salesman problem, where n is an arbitrary integer. [ABSTRACT FROM AUTHOR]

Methods are described and APL-codes are supplied to find vertices, edges, other faces and facets of polytopes given by point sets. The basic subroutine is a simplicial decomposition version of least distance, i.e. quadratic, programming. Computational experience indicates high efficiency. [ABSTRACT FROM AUTHOR]

We discuss a procedure to obtain facets and valid inequalities for the convex hull of the set of solutions to a general zero-one programming problem. Basically, facets and valid inequalities defined on lower dimensional subpolytopes are lifted into the space of the original problem. The procedure generalizes the previously known techniques for lifting facets in two respects. First, the general zero-one programming problem is considered rather than various special cases. Second, the procedure is exhaustive in the sense that it accounts for all the facets (valid inequalities) which are liftings of a given lower dimensional facet (valid inequality). [ABSTRACT FROM AUTHOR]