(Mixed) Integer Linear Programming

Integrating design and production planning considerations in multi-bay manufacturing facility layout

  • Ignacio Castillo
  • Brett A. Peters
    • Categories (Mixed) Integer Linear Programming, Facility Planning and Design

    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

    Transparent optical network design with sparse wavelength conversion

  • Arie M.C.A. Koster
  • Adrian Zymolka
  • Roland Wessäly
    • Categories (Mixed) Integer Linear Programming, Network Optimization, Telecommunications Tags , ,

    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

    Facets of a polyhedron closely related to the integer knapsack-cover problem

  • Leslie A. Hall
  • David R. Mazur
    • Categories (Mixed) Integer Linear Programming, Polyhedra Tags , ,

    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

    Safe bounds in linear and mixed-integer programming

  • Arnold Neumaier
  • Oleg Shcherbina
    • Categories (Mixed) Integer Linear Programming, Linear Programming Tags , , , , , , , , , , ,

    Current mixed-integer linear programming solvers are based on linear programming routines that use floating point arithmetic. Occasionally, this leads to wrong solutions, even for problems where all coefficients and all solution components are small integers. It is shown how, using directed rounding and interval arithmetic, cheap pre- and postprocessing of the linear programs arising in … Read more

    Pivot, Cut, and Dive: A Heuristic for 0-1 Mixed Integer Programming

  • Jonathan Eckstein
  • Mikhail S. Nediak
    • Categories (Mixed) Integer Linear Programming, Meta Heuristics, Parallel Algorithms Tags , ,

    We present a heuristic method for general 0-1 mixed integer programming, intended for eventual incorporation into parallel branch-and-bound methods for solving such problems exactly. The core of the heuristic is a rounding method based on simplex pivots, employing only gradient information, for a strictly concave, differentiable merit function measuring integer feasibility. When local minima of … Read more

    A Mixed Integer Disjunctive Model for Transmission Network Expansion

  • Laura Bahiense
  • Sérgio Granville
  • Gerson C. Oliveira
  • Mario Pereira
    • Categories (Mixed) Integer Linear Programming, Applications - OR and Management Sciences, Network Optimization Tags , ,

    The classical non-linear mixed integer formulation of the transmission network expansion problem cannot guarantee finding the optimal solution due to its non-convex nature. We propose an alternative mixed integer linear disjunctive formulation, which has better conditioning properties than the standard disjunctive model. The mixed integer program is solved by a commercial Branch and Bound code, … Read more

    A Family of Facets for the p-Median Polytope

  • Ismael de Farias
    • Categories (Mixed) Integer Linear Programming, Branch and Cut Algorithms, Transportation Tags , , , ,

    We present a nontrivial family of facet-defining inequalities for the p-median polytope. We incorporate the inequalities in a branch-and-cut scheme, and we report computational results that demonstrate their effectiveness. Citation Department of Industrial Engineering, State University of New York at Buffalo, submitted Article Download View A Family of Facets for the p-Median Polytope

    Facets of the Complementarity Knapsack Polytope

  • Ellis L. Johnson
  • George L. Nemhauser
  • Ismael de Farias
    • Categories (Mixed) Integer Linear Programming, Branch and Cut Algorithms Tags , ,

    We present a polyhedral study of the complementarity knapsack problem, in which no auxiliary binary variables are introduced, but rather the inequalities are derived in the space of the continuous variables. Citation School of Industrial and Systems Engineering, GA Tech, under review Article Download View Facets of the Complementarity Knapsack Polytope

    Solving Large Quadratic Assignment Problems on Computational Grids

  • Jean-Pierre Goux
  • Kurt M. Anstreicher
  • Jeff Linderoth
  • Nathan Brixius
    • Categories (Mixed) Integer Linear Programming, Combinatorial Optimization, Parallel Algorithms

    The quadratic assignment problem (QAP) is among the hardest combinatorial optimization problems. Some instances of size n >= 30 have remained unsolved for decades. The solution of these problems requires both improvements in mathematical programming algorithms and the utilization of powerful computational platforms. In this article we describe a novel approach to solve QAPs using … Read more