Integer Programming

Decomposition and Dynamic Cut Generation in Integer Linear Programming

  • M.V. Galati
  • Ted K. Ralphs
    • Categories (Mixed) Integer Linear Programming, Branch and Cut Algorithms, Cutting Plane Approaches Tags , , , ,

    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

    An Exact Algorithm for the Capacitated Vertex p-Center Problem

  • F.A. Ozsoy
  • Mustafa C. Pinar
    • Categories 0-1 Programming, Production and Logistics Tags ,

    We develop a simple and practical exact algorithm for the problem of locating $p$ facilities and assigning clients to them within capacity restrictions in order to minimize the maximum distance between a client and the facility to which it is assigned (capacitated $p$-center). The algorithm iteratively sets a maximum distance value within which it tries … Read more

    The Quadratic Selective Travelling Saleman Problem

  • Thomas R. Stidsen
  • Tommy Thomadsen
    • Categories 0-1 Programming, Branch and Cut Algorithms, Network Optimization Tags , , ,

    A well-known extension of the Travelling Salesman Problem (TSP) is the Selective TSP (STSP): Each node has an associated profit and instead of visiting all nodes, the most profitable set of nodes, taking into account the tour cost, is visited. The Quadratic STSP (QSTSP) adds the additional complication that each pair of nodes have an … Read more

    Lifting 2-integer knapsack inequalities

  • Agostinho Agra
  • Miguel Constantino
    • Categories Integer Programming Tags , ,

    In this paper we discuss the generation of strong valid inequalities for (mixed) integer knapsack sets based on lifting of valid inequalities for basic knapsack sets with two integer variables (and one continuous variable). The description of the basic polyhedra can be made in polynomial time. We use superadditive valid functions in order to obtain … Read more

    Capacitated Facility Location Model with Risk Pooling

  • Collette R. Coullard
  • Mark S. Daskin
  • Leyla Ozsen
    • Categories (Mixed) Integer Nonlinear Programming, Transportation Tags ,

    The Facility Location Model with Risk Pooling (LMRP) extends the uncapacitated fixed charge model to incorporate inventory decisions at the distribution centers (DCs). In this paper, we introduce a capacitated version of the LMRP that handles inventory management at the DCs such that the capacity limitations at the DCs are not exceeded. We consider a … Read more

    Lot Sizing with Inventory Bounds and Fixed Costs: Polyhedral Study and Computation

  • Alper Atamturk
  • Simge Küçükyavuz
    • Categories Cutting Plane Approaches, Production and Logistics Tags , , ,

    We investigate the polyhedral structure of the lot-sizing problem with inventory bounds. We consider two models, one with linear costs on inventory, the other with linear and fixed costs on inventory. For both models, we identify facet-defining inequalities that make use of the inventory capacities explicitly and give exact separation algorithms. We also give a … Read more

    Cover and pack inequalities for (mixed) integer programming

  • Alper Atamturk
    • Categories (Mixed) Integer Linear Programming, Cutting Plane Approaches Tags , , ,

    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

    Shunting Minimal Rail Car Allocation

  • Marco E. Luebbecke
  • Uwe T. Zimmermann
    • Categories (Mixed) Integer Linear Programming, Transportation

    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

    An algorithm model for mixed variable programming

  • Stefano Lucidi
  • Veronica Piccialli
  • Marco Sciandrone
    • Categories (Mixed) Integer Nonlinear Programming Tags , ,

    In this paper we consider a particular class of nonlinear optimization problems involving both continuous and discrete variables. The distinguishing feature of this class of nonlinear mixed optimization problems is that the structure and the number of variables of the problem depend on the values of some discrete variables. In particular we define a general … Read more