In this paper we use facets 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. Facets of this polyhedron give strong valid inequalities for general mixed-integer sets, such as the well-known … Read more
Decomposition algorithms such as Lagrangian relaxation and Dantzig-Wolfe decomposition are well-known methods that can be used to generate bounds for mixed-integer linear programming problems. Traditionally, these methods have been viewed as distinct from polyhedral methods, in which bounds are obtained by dynamically generating valid inequalities to strengthen the linear programming relaxation. Recently, a number of … Read more
We review strong inequalities for fundamental knapsack relaxations of (mixed) integer programs. These relaxations are the 0-1 knapsack set, the mixed 0-1 knapsack set, the integer knapsack set, and the mixed integer knapsack set. Our aim is to give a unified presentation of the inequalities based on covers and packs and highlight the connections among … Read more
We consider the rail car management at industrial in-plant railroads. Demands for materials or empty cars are characterized by a track, a car type, and the desired quantity. If available, we assign cars from the stock, possibly substituting types, otherwise we rent additional cars. Transportation requests are fulfilled as a short sequence of pieces of … Read more
We study the mixed-integer knapsack polyhedron, that is, the convex hull of the mixed-integer set defined by an arbitrary linear inequality and the bounds on the variables. We describe facet-defining inequalities of this polyhedron that can be obtained through sequential lifting of inequalities containing a single integer variable. These inequalities strengthen and/or generalize known inequalities … Read more
Column generation has become a powerful tool in solving large scale integer programs. We argue that most of the often reported compatibility issues between pricing oracle and branching rules disappear when branching decisions are based on the reduction of the variables of the oracle’s domain. This can be generalized to branching on variables of a … Read more
Dantzig-Wolfe decomposition and column generation, devised for linear programs, is a success story in large scale integer programming. We outline and relate the approaches, and survey mainly recent contributions, not found in textbooks, yet. We emphasize on the growing understanding of the dual point of view, which brought considerable progress to the column generation theory … Read more
This paper develops a new mathematical model that integrates layout design and production planning to prescribe efficient multi-bay manufacturing facilities. The model addresses the need to distribute department replicas throughout the facility and extends the use of product and process requirements as problem parameters in order to increase process routing flexibility. In addition, the model … Read more
We consider the design of transparent optical networks from a practical perspective. Network operators aim at satisfying the communication demands at minimum cost. Such an optimization involves three interdependent planning issues: the dimensioning of the physical topology, the routing of lightpaths, and the wavelength assignment. Further topics include the reliability of the configuration and sparse … Read more
We investigate the polyhedral structure of an integer program with a single functional constraint: the integer capacity-cover polyhedron. Such constraints arise in telecommunications planning and facility location applications, and feature the use of general integer (rather than just binary) variables. We derive a large class of facet-defining inequalities by using an augmenting technique that builds … Read more