Valid inequalities and facets of the capacitated plant location problem

Recently, several successful applications of strong cutting plane methods to combinatorial optimization problems have renewed interest in cutting plane methods, and polyhedral characterizations, of integer programming problems. In this paper, we investigate the polyhedral structure of the capacitated plant location problem. Our purpose is to identify facets and valid inequalities for a wide range of capacitated fixed charge problems that contain this prototype problem as a substructure.The first part of the paper introduces a family of facets for a version of the capacitated plant location problem with a constant capacity for all plants. These facet inequalities depend on the capacity and thus differ fundamentally from the valid inequalities for the uncapacited version of the problem.We also introduce a second formulation for a model with indivisible customer demand and show that it is equivalent to a vertex packing problem on a derived graph. We identify facets and valid inequalities for this version of the problem by applying known results for the vertex packing polytope.This research was partially supported by Grant # ECS-8316224 from the National Science Foundation's Program in Systems Theory and Operations Research.     

On discrete lot-sizing and scheduling on identical parallel machines

We consider the multi-item discrete lot-sizing and scheduling problem on identical parallel machines. Based on the fact that the machines are identical, we introduce aggregate integer variables instead of individual variables for each machine. For the problem with start-up costs, we show that the inequalities based on a unit flow formulation for each machine can be replaced by a single integer flow formulation without any change in the resulting LP bound. For the resulting integer lot-sizing with start-ups subproblem, we show how inequalities for the unit demand case can be generalized and how an approximate version of the extended formulation of Eppen and Martin can be constructed. The results of some computational experiments carried out to compare the effectiveness of the various mixed-integer programming formulations are presented.     

Mixing mixed-integer inequalities

Mixed-integer rounding (MIR) inequalities play a central role in the development of strong cutting planes for mixed-integer programs. In this paper, we investigate how known MIR inequalities can be combined in order to generate new strong valid inequalities.?Given a mixed-integer region S and a collection of valid “base” mixed-integer inequalities, we develop a procedure for generating new valid inequalities for S. The starting point of our procedure is to consider the MIR inequalities related with the base inequalities. For any subset of these MIR inequalities, we generate two new inequalities by combining or “mixing” them. We show that the new inequalities are strong in the sense that they fully describe the convex hull of a special mixed-integer region associated with the base inequalities.?We discuss how the mixing procedure can be used to obtain new classes of strong valid inequalities for various mixed-integer programming problems. In particular, we present examples for production planning, capacitated facility location, capacitated network design, and multiple knapsack problems. We also present preliminary computational results using the mixing procedure to tighten the formulation of some difficult integer programs. Finally we study some extensions of this mixing procedure. Received: April 1998 / Accepted: January 2001?Published online April 12, 2001     

The multi-item capacitated lot-sizing problem with setup times and shortage costs

We address a multi-item capacitated lot-sizing problem with setup times and shortage costs that arises in real-world production planning problems. Demand cannot be backlogged, but can be totally or partially lost. The problem is NP-hard. A mixed integer mathematical formulation is presented. Our approach in this paper is to propose some classes of valid inequalities based on a generalization of Miller et al. [A.J. Miller, G.L. Nemhauser, M.W.P. Savelsbergh, On the polyhedral structure of a multi-item production planning model with setup times, Mathematical Programming 94 (2003) 375–405] and Marchand and Wolsey [H. Marchand, L.A. Wolsey, The 0–1 knapsack problem with a single continuous variable, Mathematical Programming 85 (1999) 15–33] results. We also describe fast combinatorial separation algorithms for these new inequalities. We use them in a branch-and-cut framework to solve the problem. Some experimental results showing the effectiveness of the approach are reported.     

A cutting plane algorithm for the Capacitated Connected Facility Location Problem

We consider a network design problem that arises in the cost-optimal design of last mile telecommunication networks. It extends the Connected Facility Location problem by introducing capacities on the facilities and links of the networks. It combines aspects of the capacitated network design problem and the single-source capacitated facility location problem. We refer to it as the Capacitated Connected Facility Location Problem. We develop a basic integer programming model based on single-commodity flows. Based on valid inequalities for the capacitated network design problem and the single-source capacitated facility location problem we derive several (new) classes of valid inequalities for the Capacitated Connected Facility Location Problem including cut set inequalities, cover inequalities and combinations thereof. We use them in a branch-and-cut framework and show their applicability and efficacy on a set of real-world instances.     

Partition inequalities for capacitated survivable network design based on directed p-cycles

We study the design of capacitated survivable networks using directed p-cycles. A p-cycle is a cycle with at least three arcs, used for rerouting disrupted flow during edge failures. Survivability of the network is accomplished by reserving sufficient slack on directed p-cycles so that if an edge fails, its flow can be rerouted along the p-cycles.

We describe a model for designing capacitated survivable networks based on directed p-cycles. We motivate this model by comparing it with other means of ensuring survivability, and present a mixed-integer programming formulation for it. We derive valid inequalities for the model based on the minimum capacity requirement between partitions of the nodes and give facet conditions for them. We discuss the separation for these inequalities and present results of computational experiments for testing their effectiveness as cutting planes when incorporated in a branch-and-cut algorithm. Our experiments show that the proposed inequalities reduce the computational effort significantly.     

Two-edge connected subgraphs with bounded rings: Polyhedral results and Branch-and-Cut

We consider the network design problem which consists in determining at minimum cost a 2-edge connected network such that the shortest cycle (a “ring”) to which each edge belongs, does not exceed a given length K. We identify a class of inequalities, called cycle inequalities, valid for the problem and show that these inequalities together with the so-called cut inequalities yield an integer programming formulation of the problem in the space of the natural design variables. We then study the polytope associated with that problem and describe further classes of valid inequalities. We give necessary and sufficient conditions for these inequalities to be facet defining. We study the separation problem associated with these inequalities. In particular, we show that the cycle inequalities can be separated in polynomial time when K≤4. We develop a Branch-and-Cut algorithm based on these results and present extensive computational results.     

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.     

An exact solution framework for a broad class of vehicle routing problems

This paper presents an exact solution framework for solving some variants of the vehicle routing problem (VRP) that can be modeled as set partitioning (SP) problems with additional constraints. The method consists in combining different dual ascent procedures to find a near optimal dual solution of the SP model. Then, a column-and-cut generation algorithm attempts to close the integrality gap left by the dual ascent procedures by adding valid inequalities to the SP formulation. The final dual solution is used to generate a reduced problem containing all optimal integer solutions that is solved by an integer programming solver. In this paper, we describe how this solution framework can be extended to solve different variants of the VRP by tailoring the different bounding procedures to deal with the constraints of the specific variant. We describe how this solution framework has been recently used to derive exact algorithms for a broad class of VRPs such as the capacitated VRP, the VRP with time windows, the pickup and delivery problem with time windows, all types of heterogeneous VRP including the multi depot VRP, and the period VRP. The computational results show that the exact algorithm derived for each of these VRP variants outperforms all other exact methods published so far and can solve several test instances that were previously unsolved.     

Capacitated facility location/network design problems

We introduce a combined facility location/network design problem in which facilities have constraining capacities on the amount of demand they can serve. This model has a number of applications in regional planning, distribution, telecommunications, energy management, and other areas. Our model includes the classical capacitated facility location problem (CFLP) on a network as a special case. We present a mixed integer programming formulation of the problem, and several classes of valid inequalities are derived to strengthen its LP relaxation. Computational experience with problems with up to 40 nodes and 160 candidate links is reported, and a sensitivity analysis provides insight into the behavior of the model in response to changes in key problem parameters.     

Modeling and solving the mixed capacitated general routing problem

We tackle the mixed capacitated general routing problem (MCGRP) which generalizes many other routing problems. We propose an integer programming model for the MCGRP and extend some inequalities originally introduced for the capacitated arc routing problem (CARP). Identification procedures for these inequalities and for some relaxed constraints are also discussed. Finally, we describe a branch and cut algorithm including the identification procedures and present computational experiments over instances derived from the CARP.     

An intermodal multicommodity routing problem with scheduled services

We study a multicommodity routing problem faced by an intermodal service operator that uses ground and maritime transportation. Given a planning horizon, a?set of commodities to be picked up at their release times and to be delivered not later than their duedates, the problem is to decide on routes for these commodities using trucks and scheduled and capacitated maritime services at minimum cost of transportation and stocking at the seaports. Two mixed integer programming formulations and valid inequalities are proposed for this problem. The results of a computational study to evaluate the strength of the linear programming relaxations and the solution times are reported.     

Comparison of bundle and classical column generation

When a column generation approach is applied to decomposable mixed integer programming problems, it is standard to formulate and solve the master problem as a linear program. Seen in the dual space, this results in the algorithm known in the nonlinear programming community as the cutting-plane algorithm of Kelley and Cheney-Goldstein. However, more stable methods with better theoretical convergence rates are known and have been used as alternatives to this standard. One of them is the bundle method; our aim is to illustrate its differences with Kelley’s method. In the process we review alternative stabilization techniques used in column generation, comparing them from both primal and dual points of view. Numerical comparisons are presented for five applications: cutting stock (which includes bin packing), vertex coloring, capacitated vehicle routing, multi-item lot sizing, and traveling salesman. We also give a sketchy comparison with the volume algorithm. This research has been supported by Inria New Investigation Grant “Convex Optimization and Dantzig-Wolfe Decomposition”.     

A polyhedral study for the cubic formulation of the unconstrained traveling tournament problem

We consider the unconstrained traveling tournament problem, a sports timetabling problem that minimizes traveling of teams. Since its introduction about 20 years ago, most research was devoted to modeling and reformulation approaches. In this paper we carry out a polyhedral study for the cubic integer programming formulation by establishing the dimension of the integer hull as well as of faces induced by model inequalities. Moreover, we introduce a new class of inequalities and show that they are facet-defining. Finally, we evaluate the impact of these inequalities on the linear programming bounds.     

The convex hull of two core capacitated network design problems

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.Research of this author was supported in part by a Faculty Grant from the Katz Graduate School of Business, University of Pittsburgh.     

Unrelated machine scheduling with time-window and machine downtime constraints: An application to a naval battle-group problem

This paper deals with an unrelated machine scheduling problem of minimizing the total weighted flow time, subject to time-window job availability and machine downtime side constraints. We present a zero-one integer programming formulation of this problem. The linear programming relaxation of this formulation affords a tight lower bound and often generates an integer optimal solution for the problem. By exploiting the special structures inherent in the formulation, we develop some classes of strong valid inequalities that can be used to tighten the initial formulation, as well as to provide cutting planes in the context of a branch-and-cut procedure. A major computational bottleneck is the solution of the underlying linear programming relaxation because of the extremely high degree of degeneracy inherent in the formulation. In order to overcome this difficulty, we employ a Lagrangian dual formulation to generate lower and upper bounds and to drive the branch-and-bound algorithm. As a practical instance of the unrelated machine scheduling problem, we describe a combinatorial naval defense problem. This problem seeks to schedule a set of illuminators (passive homing devices) in order to strike a given set of targets using surface-to-air missiles in a naval battle-group engagement scenario. We present computational results for this problem using suitable realistic data.     

Ramsey theory and integrality gap for the independent set problem

We discuss the effectiveness of integer programming for solving large instances of the independent set problem. Typical LP formulations, even strengthened by clique inequalities, yield poor bounds for this problem. We show that a strong bound can be obtained by the use of the so-called rank inequalities, which generalize the clique inequalities. For some problems the clique inequalities imply the rank inequalities, and then a strong bound is guaranteed already by the simpler formulation.     

On alternative mixed integer programming formulations and LP-based heuristics for lot-sizing with setup times

We address the multi-item, capacitated lot-sizing problem (CLSP) encountered in environments where demand is dynamic and to be met on time. Items compete for a limited capacity resource, which requires a setup for each lot of items to be produced causing unproductive time but no direct costs. The problem belongs to a class of problems that are difficult to solve. Even the feasibility problem becomes combinatorial when setup times are considered. This difficulty in reaching optimality and the practical relevance of CLSP make it important to design and analyse heuristics to find good solutions that can be implemented in practice. We consider certain mixed integer programming formulations of the problem and develop heuristics including a curtailed branch and bound, for rounding the setup variables in the LP solution of the tighter formulations. We report our computational results for a class of instances taken from literature.     

Strong valid inequalities for fluence map optimization problem under dose-volume restrictions

Fluence map optimization problems are commonly solved in intensity modulated radiation therapy (IMRT) planning. We show that, when subject to dose-volume restrictions, these problems are NP-hard and that the linear programming relaxation of their natural mixed integer programming formulation can be arbitrarily weak. We then derive strong valid inequalities for fluence map optimization problems under dose-volume restrictions using disjunctive programming theory and show that strengthening mixed integer programming formulations with these valid inequalities has significant computational benefits.