We propose a simple and sufficiently fast separation procedure to identify cover inequalities for the multidimensional knapsack problem. It is based on the solution of a conventional integer programming model. Solving this kind of integer programs are usually considered expensive and the proposed method may have been overlooked because of this assumption. The results of … Read more
This paper first presents an improve cutting plane method for solving the linear programming problems, based on the primal simplex method with the current equivalent facet technique, in which the increment of objection function is allowed as a pivot variable to decide the search step size. We obtain a strong valid inequality from the objective … Read more
For a real world problem — transporting pallets between warehouses in order to guarantee sufficient supply for known and additional stochastic demand — we propose a solution approach via convex relaxation of an integer programming formulation, suitable for online optimization. The essential new element linking routing and inventory management is a convex piecewise linear cost … Read more
In this paper, we study the conflict-free assignment of wavelengths to lightpaths in an optical network with the opportunity to place wavelength converters. To benchmark heuristics for the problem, we develop integer programming formulations and study their properties. Moreover, we study the computational performance of the column generation algorithm for solving the linear relaxation of … Read more
We introduce a new extension of Punnen’s exponential neighborhood for the traveling salesman problem (TSP). In contrast to an interesting generalization of Punnen’s neighborhood by De Franceschi, Fischetti and Toth (2005), our neighborhood is searchable in polynomial time, a feature that invites exploitation by heuristic and metaheuristic procedures for the TSP and related problems, including … Read more
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
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
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
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
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