An Improved Lower Bound for the Multimedian Location Problem

We consider the problem of locating, on a network, n new facilities that interact with m existing facilities. In addition, pairs of new facilities interact. This problem, the multimedian location problem on a network, is known to be NP-hard. We give a new integer programming formulation of this problem, and show that its linear programming relaxation provides a lower bound that is superior to the bound provided by a previously published formulation. We also report results of computational testing with both formulations.     

Strong formulations for the pooling problem

The pooling problem is a well-studied global optimization problem with applications in oil refining and petrochemical industry. Despite the strong NP-hardness of the problem, which is proved formally in this paper, most instances from the literature have recently been solved efficiently by use of strong formulations. The main contribution from this paper is a new formulation that proves to be stronger than other formulations based on proportion variables. Moreover, we propose a promising branching strategy for the new formulation and provide computational experiments confirming the strength of the new formulation and the effectiveness of the branching strategy.     

Heuristic algorithms for delivered price spatially competitive network facility location problems

We review previous formulations of models for locating a firm's production facilities while simultaneously determining production levels at those facilities so as to maximize the firm's profit. We enhance these formulations by adding explicit variables to represent the firm's shipping activities and discuss the implications of this revised approach. In these formulations, existing firms, as well as new entrants, are assumed to act in accordance with an appropriate model of spatial equilibrium. The firm locating new production facilities is assumed to be a large manufacturer entering an industry composed of a large number of small firms. Our previously reported proof of existence of a solution to the combined location-equilibrium problem is briefly reviewed. A heuristic algorithm based on sensitivity analysis methods which presume the existence of a solution and which locally approximate price changes as linear functions of production perturbations resulting from newly established facilities is presented. We provide several numerical tests to illustrate the contrasting locational solutions which this paper's revised delivered price formulation generates relative to those of previous formulations. An exact, although computationally burdensome, method is also presented and employed to check the reliability of the heuristic algorithm.     

A computational comparison of flow formulations for the capacitated location-routing problem

In this paper we present a computational comparison of four different flow formulations for the capacitated location-routing problem. We introduce three new flow formulations for the problem, namely a two-index two-commodity flow formulation, a three-index vehicle-flow formulation and a three-index two-commodity flow formulation. We also consider an existing two-index vehicle-flow formulation and extend it by considering new families of valid inequalities and separation algorithms. We introduce new branch-and-cut algorithms for each of the formulations and compare them on a wide number of instances. Our results show that compact formulations can produce tight gaps and solve many instances quickly, whereas three-index formulations scale better in terms of computing time.     

On the equivalence of strong formulations for capacitated multi-level lot sizing problems with setup times

Several mixed integer programming formulations have been proposed for modeling capacitated multi-level lot sizing problems with setup times. These formulations include the so-called facility location formulation, the shortest route formulation, and the inventory and lot sizing formulation with (?, S) inequalities. In this paper, we demonstrate the equivalence of these formulations when the integrality requirement is relaxed for any subset of binary setup decision variables. This equivalence has significant implications for decomposition-based methods since same optimal solution values are obtained no matter which formulation is used. In particular, we discuss the relax-and-fix method, a decomposition-based heuristic used for the efficient solution of hard lot sizing problems. Computational tests allow us to compare the effectiveness of different formulations using benchmark problems. The choice of formulation directly affects the required computational effort, and our results therefore provide guidelines on choosing an effective formulation during the development of heuristic-based solution procedures.     

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.     

The pickup and delivery problem with transfers: Formulation and a branch-and-cut solution method

In this paper, a strict formulation of a generalization of the classical pickup and delivery problem is presented. Here, we add the flexibility of providing the option for passengers to transfer from one vehicle to another at specific locations. As part of the mathematical formulation, we include transfer nodes where vehicles may interact interchanging passengers. Additional variables to keep track of customers along their route are considered. The formulation has been proven to work correctly, and by means of a simple example instance, we conclude that there exist some configurations in which a scheme allowing transfers results in better quality optimal solutions. Finally, a solution method based on Benders decomposition is addressed. We compare the computational effort of this application with a straight branch and bound strategy; we also provide insights to develop more efficient set partitioning formulations and associated algorithms for solving real-size problems.     

Set covering and packing formulations of graph coloring: Algorithms and first polyhedral results

We consider two (0, 1)-linear programming formulations of the graph (vertex-) coloring problem, in which variables are associated with stable sets of the input graph. The first one is a set covering formulation, where the set of vertices has to be covered by a minimum number of stable sets. The second is a set packing formulation, in which constraints express that two stable sets cannot have a common vertex, and large stable sets are preferred in the objective function. We identify facets with small coefficients for the polytopes associated with both formulations. We show by computational experiments that both formulations are about equally efficient when used in a branch-and-price algorithm. Next we propose some preprocessing, and show that it can substantially speed up the algorithm, if it is applied at each node of the enumeration tree. Finally we describe a cutting plane procedure for the set covering formulation, which often reduces the size of the enumeration tree.     

Branch-and-price-and-cut algorithms for solving the reliable <Emphasis Type="Italic">h</Emphasis>-paths problem

We examine a routing problem in which network arcs fail according to independent failure probabilities. The reliable h-path routing problem seeks to find a minimum-cost set of h ≥ 2 arc-independent paths from a common origin to a common destination, such that the probability that at least one path remains operational is sufficiently large. For the formulation in which variables are used to represent the amount of flow on each arc, the reliability constraint induces a nonconvex feasible region, even when the integer variable restrictions are relaxed. Prior arc-based models and algorithms tailored for the case in which h = 2 do not extend well to the general h-path problem. Thus, we propose two alternative integer programming formulations for the h-path problem in which the variables correspond to origin-destination paths. Accordingly, we develop two branch-and-price-and-cut algorithms for solving these new formulations, and provide computational results to demonstrate the efficiency of these algorithms.     

Integer-friendly formulations for the r-separation problem

In this paper, we consider different formulations for the r-separation problem, where the objective is to choose as as many points as possible from a given set of points subject to the constraint that no two selected points can be closer than r units to one another. Our goal is to devise a mathematical programming formulation with an LP-relaxation which yields integer solutions with great frequency. We consider six different formulations of the r-separation problem. We show that the LP-relaxations of the most obvious formulations will yield fractional results in all instances of the problem if an optimal solution contains fewer than half of the given points. To build computationally effective formulations for the r-separation problem, we write dense constraints with unit right-hand-sides. The LP formulation that performs the best in our computational tests almost always finds 0–1 solutions to the problem.     

Extended formulations for the A-cut problem

LetG=(V, E) be an undirected graph andA⊆V. We consider the problem of finding a minimum cost set of edges whose deletion separates every pair of nodes inA. 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.     

A branch-and-cut procedure for the Udine Course Timetabling problem

A branch-and-cut procedure for the Udine Course Timetabling problem is described. Simple compact integer linear programming formulations of the problem employ only binary variables. In contrast, we give a formulation with fewer variables by using a mix of binary and general integer variables. This formulation has an exponential number of constraints, which are added only upon violation. The number of constraints is exponential. However, this is only with respect to the upper bound on the general integer variables, which is the number of periods per day in the Udine Course Timetabling problem.     

A combined nodal continuous-discontinuous finite element formulation for the Maxwell problem

Continuous Galerkin formulations are appealing due to their low computational cost, whereas discontinuous Galerkin formulation facilitate adaptative mesh refinement and are more accurate in regions with jumps of physical parameters. Since many electromagnetic problems involve materials with different physical properties, this last point is very important. For this reason, in this article we have developed a combined cG-dG formulation for Maxwell’s problem that allows arbitrary finite element spaces with functions continuous in patches of finite elements and discontinuous on the interfaces of these patches. In particular, the second formulation we propose comes from a novel continuous Galerkin formulation that reduces the amount of stabilization introduced in the numerical system. In all cases, we have performed stability and convergence analyses of the methods. The outcome of this work is a new approach that keeps the low CPU cost of recent nodal continuous formulations with the ability to deal with coefficient jumps and adaptivity of discontinuous ones. All these methods have been tested using a problem with singular solution and another one with different materials, in order to prove that in fact the resulting formulations can properly deal with these problems.     

The maximization of a function over the efficient set via a penalty function approach

In this paper we present several equivalent mathematical programming formulations of the problem of maximizing a function over the efficient set, in the case of a polytopal feasible region and linear functions. Penalty function formulations and their properties are given. An examination is made of computational aspects, epsilon efficiency, the appropriateness of the original problem formulation, and of nonlinear extensions.     

Probabilistic Formulation of the Emergency Service Location Problem

The problem of locating emergency service facilities is studied under the assumption that the locations of incidents (accidents, fires, or customers) are random variables. The probability distribution for rectilinear travel time between a new facility location and the random location of the incident P _i is developed for the case of P _i being uniformly distributed over a rectangular region. The location problem is considered in a discrete space. A deterministic formulation is obtained and recognized to be a set cover problem. Probabilistic variation of the central facility location problem is also presented.An example and some computational experience are provided to emphasize the impact of the probabilistic formulation on the location decision.     

On relaxing the integrality of the allocation variables of the reliability fixed-charge location problem

The aim of the reliability fixed-charge location problem is to find robust solutions to the fixed-charge location problem when some facilities might fail with probability q. In this paper we analyze for which allocation variables in the reliability fixed-charge location problem formulation the integrality constraint can be relaxed so that the optimal value matches the optimal value of the binary problem. We prove that we can relax the integrality of all the allocation variables associated to non-failable facilities or of all the allocation variables associated to failable facilities but not of both simultaneously. We also demonstrate that we can relax the integrality of all the allocation variables whenever a family of valid inequalities is added to the set of constraints or whenever the parameters of the problem satisfy certain conditions. Finally, when solving the instances in a data set we discuss which relaxation or which modification of the problem works better in terms of resolution time and we illustrate that relaxing the integrality of the allocation variables inappropriately can alter the objective value considerably.     

Threshold Boolean form for joint probabilistic constraints with random technology matrix

We develop a new modeling and solution method for stochastic programming problems that include a joint probabilistic constraint in which the multirow random technology matrix is discretely distributed. We binarize the probability distribution of the random variables in such a way that we can extract a threshold partially defined Boolean function (pdBf) representing the probabilistic constraint. We then construct a tight threshold Boolean minorant for the pdBf. Any separating structure of the tight threshold Boolean minorant defines sufficient conditions for the satisfaction of the probabilistic constraint and takes the form of a system of linear constraints. We use the separating structure to derive three new deterministic formulations for the studied stochastic problem, and we derive a set of strengthening valid inequalities. A crucial feature of the new integer formulations is that the number of integer variables does not depend on the number of scenarios used to represent uncertainty. The computational study, based on instances of the stochastic capital rationing problem, shows that the mixed-integer linear programming formulations are orders of magnitude faster to solve than the mixed-integer nonlinear programming formulation. The method integrating the valid inequalities in a branch-and-bound algorithm has the best performance.     

Extended formulations in combinatorial optimization

This survey is concerned with the size of perfect formulations for combinatorial optimization problems. By “perfect formulation”, we mean a system of linear inequalities that describes the convex hull of feasible solutions, viewed as vectors. Natural perfect formulations often have a number of inequalities that is exponential in the size of the data needed to describe the problem. Here we are particularly interested in situations where the addition of a polynomial number of extra variables allows a formulation with a polynomial number of inequalities. Such formulations are called “compact extended formulations”. We survey various tools for deriving and studying extended formulations, such as Fourier’s procedure for projection, Minkowski–Weyl’s theorem, Balas’ theorem for the union of polyhedra, Yannakakis’ theorem on the size of an extended formulation, dynamic programming, and variable discretization. For each tool that we introduce, we present one or several examples of how this tool is applied. In particular, we present compact extended formulations for several graph problems involving cuts, trees, cycles and matchings, and for the mixing set. We also present Bienstock’s approximate compact extended formulation for the knapsack problem, Goemans’ result on the size of an extended formulation for the permutahedron, and the Faenza-Kaibel extended formulation for orbitopes.