On generalized branching methods for mixed integer programming

In this paper we present a restructuring of the computations in Lenstra’s methods for solving mixed integer linear programs. We show that the problem of finding a good branching hyperplane can be formulated on an adjoint lattice of the Kernel lattice of the equality constraints without requiring any dimension reduction. As a consequence the short … Read more

Decomposition in Integer Programming

Both cutting plane methods and traditional decomposition methods are procedures that compute a bound on the optimal value of an integer linear program (ILP) by constructing an approximation to the convex hull of feasible solutions. This approximation is obtained by intersecting the polyhedron associated with the continuous relaxation, which has an explicit representation, with an … Read more

Noncommercial Software for Mixed-Integer Linear Programming

We present an overview of noncommercial software tools for the solution of mixed-integer linear programs (MILPs). We first review solution methodologies for MILPs and then present an overview of the available software, including detailed descriptions of eight software packages available under open source or other noncommercial licenses. Each package is categorized as a black box … Read more

Sequential pairing of mixed integer inequalities

We present a scheme for generating new valid inequalities for mixed integer programs by taking pair-wise combinations of existing valid inequalities. Our scheme is related to mixed integer rounding and mixing. The scheme is in general sequence-dependent and therefore leads to an exponential number of inequalities. For some important cases, we identify combination sequences that … Read more

Provably Good Solutions for Wavelength Assignment in Optical Networks

In this paper, we study the minimum converter wavelength assignment problem in optical networks. To benchmark the quality of solutions obtained by heuristics, we derive an integer programming formulation by generalizing the formulation of Mehrotra and Trick (1996) for the vertex coloring problem. To handle the exponential number of variables, we propose a column generation … Read more

Formulations and Valid Inequalities for the Heterogeneous Vehicle Routing Problem

We consider the vehicle routing problem where one can choose among vehicles with different costs and capacities to serve the trips. We develop six different formulations: the first four based on Miller-Tucker-Zemlin constraints and the last two based on flows. We compare the linear programming bounds of these formulations. We derive valid inequalities and lift … Read more

SYNERGY ANALYSIS OF COLLABORATIVE SUPPLY CHAIN MANAGEMENT IN ENERGY SYSTEMS USING MULTI-PERIOD MILP

Energy, a fundamental entity of modern life, is usually produced using fossil fuels as the primary raw material. A consequence of burning fossil fuels is the emission of environmentally harmful substances. Energy production systems generate steam and electricity that are served to different process customers to satisfy their energy requirement. The improvement of economical and … Read more

A Mixed-Integer Programming Approach to Multi-Class Data Classification Problem

This paper presents a new data classification method based on mixed-integer programming. Traditional approaches that are based on partitioning the data sets into two groups perform poorly for multi-class data classification problems. The proposed approach is based on the use of hyper-boxes for defining boundaries of the classes that include all or some of the … Read more

A Piecewise Linearization Framework for Retail Shelf Space Management Models

Managing shelf space is critical for retailers to attract customers and to optimize profit. This paper develops a shelf space allocation optimization model that explicitly incorporates essential in-store costs and considers space- and cross-elasticities. The resultant model maximizes a signomial objective function over linear and bilinear constraints in mixed-integer variables. We propose a piecewise linearization … Read more

Reduction Tests for the Prize-Collecting Steiner Problem

The Prize-Collecting Steiner Problem (PCSP) is a generalization of the classical Steiner Problem in Graphs (SPG) where instead of terminal vertices that must be necessarily connected, one have profits associated to the vertices that must be balanced against the connection costs. This problem is gaining much attention in the last years due to its practical … Read more