Polyhedral study of the connected subgraph problem

In this paper, we study the connected subgraph polytope which is the convex hull of the solutions to a related combinatorial optimization problem called the maximum weight connected subgraph problem. We strengthen a cut-based formulation by considering some new partition inequalities for which we give necessary and sufficient conditions to be facet defining. Based on the separation problem associated with these inequalities, we give a complete polyhedral characterization of the connected subgraph polytope on cycles and trees.     

The generalized assignment problem: Valid inequalities and facets

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.Partial financial support under NSF grant #CCR-8812736.Partial financial support under NSF grant #DMS-8606188.     

The relation of time indexed formulations of single machine scheduling problems to the node packing problem

 The relation of time indexed formulations of nonpreemptive single machine scheduling problems to the node packing problem is established and then used to provide simple and intuitive alternate proofs of validity and maximality for previously known results on the facial structure of the scheduling problem. Previous work on the facial structure has focused on describing the convex hull of the set of feasible partial schedules, schedules in which not all jobs have to be started. The equivalence between the characteristic vectors of this set and those of the set of feasible node packings in a graph whose structure is determined by the parameters of the scheduling problem is established. The main contribution of this paper is to show that the facet inducing inequalities for the convex hull of the set of feasible partial schedules that have integral coefficients and right hand side 1 or 2 are the maximal clique inequalities and the maximally and sequentially lifted 5-hole inequalities of the convex hull of the set of feasible node packings in this graph respectively. Received: September 10, 2000 / Accepted: April 20, 2002 Published online: September 27, 2002 Key words. scheduling – node packing – polyhedral methods – facet defining graphs – lifted valid inequalities – facet inducing inequalities}     

On Facets of Knapsack Equality Polytopes

The 0/1 knapsack equality polytope is, by definition, the convex hull of 0/1 solutions of a single linear equation. A special form of this polytope, where the defining linear equation has nonnegative integer coefficients and the number of variables having coefficient one exceeds the right-hand side, is considered. Equality constraints of this form arose in a real-world application of integer programming to a truck dispatching scheduling problem. Families of facet defining inequalities for this polytope are identified, and complete linear inequality representations are obtained for some classes of polytopes.     

A polyhedral approach to single-machine scheduling problems

We report new results for a time-indexed formulation of nonpreemptive single-machine scheduling problems. We give complete characterizations of all facet inducing inequalities with integral coefficients and right-hand side 1 or 2 for the convex hull of the set of feasible partial schedules, i.e., schedules in which not all jobs have to be started. Furthermore, we identify conditions under which these facet inducing inequalities are also facet inducing for the original polytope, which is the convex hull of the set of feasible complete schedules, i.e., schedules in which all jobs have to be started. To obtain insight in the effectiveness of these classes of facet-inducing inequalities, we develop a branch-and-cut algorithm based on them. We evaluate its performance on the strongly NP-hard single machine scheduling problem of minimizing the weighted sum of the job completion times subject to release dates. Received March 24, 1994 / Revised version received February 13, 1997 Published online June 28, 1999     

Facets of the balanced (acyclic) induced subgraph polytope

A signed graph is a graph whose edges are labelled positive or negative. A signed graph is said to be balanced if the set of negative edges form a cut. The balanced induced subgraph polytopeP(G) of a graphG is the convex hull of the incidence vectors of all node sets that induce balanced subgraphs ofG. In this paper we exhibit various (rank) facet defining inequalities. We describe several methods with which new facet defining inequalities ofP(G) can be constructed from known ones. Finding a maximum weighted balanced induced subgraph of a series parallel graph is a polynomial problem. We show that for this class of graphsP(G) may have complicated facet defining inequalities. We derive analogous results for the polytope of acyclic induced subgraphs.Research supported in part by the Natural Sciences and Engineering Research Council of Canada; the second author has also been supported by C.P. Rail.     

A new formulation for the Traveling Deliveryman Problem

The Traveling Deliveryman Problem is a generalization of the Minimum Cost Hamiltonian Path Problem where the starting vertex of the path, i.e. a depot vertex, is fixed in advance and the cost associated with a Hamiltonian path equals the sum of the costs for the layers of paths (along the Hamiltonian path) going from the depot vertex to each of the remaining vertices. In this paper, we propose a new Integer Programming formulation for the problem and computationally evaluate the strength of its Linear Programming relaxation. Computational results are also presented for a cutting plane algorithm that uses a number of valid inequalities associated with the proposed formulation. Some of these inequalities are shown to be facet defining for the convex hull of feasible solutions to that formulation. These inequalities proved very effective when used to reinforce Linear Programming relaxation bounds, at the nodes of a Branch and Bound enumeration tree.     

Lifting the facets of zero–one polytopes

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).     

Generating Convex Polynomial Inequalities for Mixed 0–1 Programs

We develop a method for generating valid convex quadratic inequalities for mixed0–1 convex programs. We also show how these inequalities can be generated in the linear case by defining cut generation problems using a projection cone. The basic results for quadratic inequalities are extended to generate convex polynomial inequalities.     

New facets for the two-stage uncapacitated facility location polytope

The two-stage uncapacitated facility location problem is considered. This problem involves a system providing a choice of depots and plants, each with an associated location cost, and a set of demand points which must be supplied, in such a way that the total cost is minimized. The formulations used until now to approach the problem were symmetric in plants and depots. In this paper the asymmetry inherent to the problem is taken into account to enforce the formulation which can be seen like a set packing problem and new facet defining inequalities for the convex hull of the feasible solutions are obtained. A computational study is carried out which illustrates the interest of the new facets. A new family of facets recently developed, termed lifted fans, is tested with success.     

Projection with a Minimal System of Inequalities

Projection of a polyhedron involves the use of a cone whose extreme rays induce the inequalities defining the projection. These inequalities need not be facet defining. We introduce a transformation that produces a cone whose extreme rays induce facets of the projection.     

A complete characterization of disjunctive conic cuts for mixed integer second order cone optimization

We study the convex hull of the intersection of a disjunctive set defined by parallel hyperplanes and the feasible set of a mixed integer second order cone optimization (MISOCO) problem. We extend our prior work on disjunctive conic cuts (DCCs), which has thus far been restricted to the case in which the intersection of the hyperplanes and the feasible set is bounded. Using a similar technique, we show that one can extend our previous results to the case in which that intersection is unbounded. We provide a complete characterization in closed form of the conic inequalities required to describe the convex hull when the hyperplanes defining the disjunction are parallel.     

Maximizing a submodular function by integer programming: Polyhedral results for the quadratic case

We give a new mixed integer programming (MIP) formulation for the quadratic cost partition problem that is derived from a MIP formulation for maximizing a submodular function. Several classes of valid inequalities for the convex hull of the feasible solutions are derived using the valid inequalities for the node packing polyhedron. Facet defining conditions and separation algorithms are discussed and computational results are reported.     

The symmetric quadratic traveling salesman problem

In the quadratic traveling salesman problem a cost is associated with any three nodes traversed in succession. This structure arises, e.g., if the succession of two edges represents energetic conformations, a change of direction or a possible change of transportation means. In the symmetric case, costs do not depend on the direction of traversal. We study the polyhedral structure of a linearized integer programming formulation of the symmetric quadratic traveling salesman problem. Our constructive approach for establishing the dimension of the underlying polyhedron is rather involved but offers a generic path towards proving facetness of several classes of valid inequalities. We establish relations to facets of the Boolean quadric polytope, exhibit new classes of polynomial time separable facet defining inequalities that exclude conflicting configurations of edges, and provide a generic strengthening approach for lifting valid inequalities of the usual traveling salesman problem to stronger valid inequalities for the symmetric quadratic traveling salesman problem. Applying this strengthening to subtour elimination constraints gives rise to facet defining inequalities, but finding a maximally violated inequality among these is NP-complete. For the simplest comb inequality with three teeth the strengthening is no longer sufficient to obtain a facet. Preliminary computational results indicate that the new cutting planes may help to considerably improve the quality of the root relaxation in some important applications.     

Optimal relay node placement in delay constrained wireless sensor network design

The Delay Constrained Relay Node Placement Problem (DCRNPP) frequently arises in the Wireless Sensor Network (WSN) design. In WSN, Sensor Nodes are placed across a target geographical region to detect relevant signals. These signals are communicated to a central location, known as the Base Station, for further processing. The DCRNPP aims to place the minimum number of additional Relay Nodes at a subset of Candidate Relay Node locations in such a manner that signals from various Sensor Nodes can be communicated to the Base Station within a pre-specified delay bound. In this paper, we study the structure of the projection polyhedron of the problem and develop valid inequalities in form of the node-cut inequalities. We also derive conditions under which these inequalities are facet defining for the projection polyhedron. We formulate a branch-and-cut algorithm, based upon the projection formulation, to solve DCRNPP optimally. A Lagrangian relaxation based heuristic is used to generate a good initial solution for the problem that is used as an initial incumbent solution in the branch-and-cut approach. Computational results are reported on several randomly generated instances to demonstrate the efficacy of the proposed algorithm.     

On the polyhedral structure of a multi–item production planning model with setup times

 We present and study a mixed integer programming model that arises as a substructure in many industrial applications. This model generalizes a number of structured MIP models previously studied, and it provides a relaxation of various capacitated production planning problems and other fixed charge network flow problems. We analyze the polyhedral structure of the convex hull of this model, as well as of a strengthened LP relaxation. Among other results, we present valid inequalities that induce facets of the convex hull under certain conditions. We also discuss how to strengthen these inequalities by using known results for lifting valid inequalities for 0–1 continuous knapsack problems. Received: 30 October 2000 / Accepted: 25 March 2002 Published online: September 27, 2002 Key words. mixed integer programming – production planning – polyhedral combinatorics – capacitated lot–sizing – fixed charge network flow Some of the results of this paper have appeared in condensed form in ``Facets, algorithms, and polyhedral characterizations of a multi-item production planning model with setup times', Proceedings of the Eighth Annual IPCO conference, pp. 318-332, by the same authors. This paper presents research results of the Belgian Program on Interuniversity Poles of Attraction initiated by the Belgian State, Prime Minister's Office, Science Policy Programming. The scientific responsibility is assumed by the authors. This research was also supported by NSF Grant No. DMI-9700285 and by Philips Electronics North America.     

On formulations of the stochastic uncapacitated lot-sizing problem

We consider two formulations of a stochastic uncapacitated lot-sizing problem. We show that by adding (?,S) inequalities to the one with the smaller number of variables, both formulations give the same LP bound. Then we show that for two-period problems, adding another class of inequalities gives the convex hull of integral solutions.     

Analyzing linear systems containing strict inequalities via evenly convex hulls

The evenly convex hull of a given set is the intersection of all the open halfspaces which contain such set (hence the convex hull is contained in the evenly convex hull). This paper deals with finite dimensional linear systems containing strict inequalities and (possibly) weak inequalities as well as equalities. The number of inequalities and equalities in these systems is arbitrary (possibly infinite). For such kind of systems a consistency theorem is provided and those strict inequalities (weak inequalities, equalities) which are satisfied for every solution of a given system are characterized. Such results are formulated in terms of the evenly convex hull of certain sets which depend on the coefficients of the system.