Integer Programming

Socially optimal location of facilities with fixed servers, stochastic demand and congestion

  • Ignacio Castillo
  • Armann Ingolfsson
  • Thaddeus Sim
    • Categories (Mixed) Integer Nonlinear Programming, Multidisciplinary Design Optimization

    We present two capacity choice scenarios for the socially optimal location of facilities with fixed servers, stochastic demand and congestion. Walk-in health clinics, motor vehicle inspection stations, automobile emissions testing stations, and internal service systems are motivating examples of such facilities. The choice of locations for such facilities influences not only distances for users traveling … Read more

    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

    Hard equality constrained integer knapsacks

  • Karen I. Aardal
  • Arjen K. Lenstra
    • Categories Integer Programming Tags , ,

    We consider the following integer feasibility problem: “Given positive integer numbers $a_0,a_1,\dots,a_n,$ with $\gcd(a_1,\dots,a_n)=1$ and $\va=(a_1,\dots,a_n)$, does there exist a vector $\vx\in\bbbz^n_{\ge \zero}$ satisfying $\va\vx = a_0$?” Some instances of this type have been found to be extremely hard to solve by standard methods such as branch-and-bound, even if the number of variables is as … Read more

    Using selective orthonormalization to update the analytic center after the addition of multiple cuts

  • John E. Mitchell
  • Srinivasan Ramaswamy
    • Categories Convex Optimization, Cutting Plane Approaches, Nonsmooth Optimization Tags , , , ,

    We study the issue of updating the analytic center after multiple cutting planes have been added through the analytic center of the current polytope in Euclidean n-space. This is an important issue that arises at every `stage’ in a cutting plane algorithm. If q cuts are to be added, with q no larger than n, … 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

    Sufficient Global Optimality Conditions for Bivalent Quadratic Optimization

  • Mustafa C. Pinar
    • Categories 0-1 Programming, Quadratic Programming Tags , ,

    We prove a sufficient global optimality condition for quadratic optimization with quadratic constraints where the variables are allowed to take -1 and 1 values. We extend the condition to quadratic programs with matrix variables and orthogonality conditions, and in particular, to the quadratic assignment problem. Citation Bilkent University Technical Report, September 2002. Article Download View … Read more

    A Branch-and-Price Algorithm and New Test Problems for Spectrum Auctions

  • Sven de Vries
  • Oktay Gunluk
  • Lazslo Ladanyi
    • Categories Applications - OR and Management Sciences, Integer Programming Tags , , ,

    When combinatorial bidding is permitted in Spectrum Auctions, such as the upcoming FCC auction #31, the resulting winner-determination problem can be computationally challenging. We present a branch-and-price algorithm based on a set-packing formulation originally proposed by Dietrich and Forrest (2002). This formulation has a variable for every possible combination of winning bids for each bidder. … Read more

    Solving the knapsack problem via Z-transform

  • Jean-Bernard Lasserre
  • Eduardo Santillan Zeron
    • Categories Integer Programming, Polyhedra

    Given vectors $a,c\in Z^n$ and $b\in Z$, we consider the (unbounded) knapsack optimization problem $P:\,\min\{c’x\,\vert\, a’x=b;\,x\in N^n\}$. We compute the minimum value $p^*$ using techniques from complex analysis, namely Cauchy residue technique to integrate a function in $C^2$, the $Z$-transform of an appropriate function related to $P$. The computational complexity depends on $s:=\sum_{a_j} a_j$, not … Read more

    Lower bound for the number of iterations in semidefinite hierarchies for the cut polytope

  • Monique Laurent
    • Categories 0-1 Programming, Polyhedra, Semi-definite Programming Tags , , ,

    Hierarchies of semidefinite relaxations for $0/1$ polytopes have been constructed by Lasserre (2001a) and by Lov\’asz and Schrijver (1991), permitting to find the cut polytope of a graph on $n$ nodes in $n$ steps. We show that $\left\lceil {n\over 2} \right\rceil$ iterations are needed for finding the cut polytope of the complete graph $K_n$. Citation … Read more