(Mixed) Integer Linear Programming

On n-step MIR and Partition Inequalities for Integer Knapsack and Single-node Capacitated Flow Sets

  • Kiavash Kianfar
    • Categories (Mixed) Integer Linear Programming

    Pochet and Wolsey [Y. Pochet, L.A. Wolsey, Integer knapsack and flow covers with divisible coefficients: polyhedra, optimization and separation. Discrete Applied Mathematics 59(1995) 57-74] introduced partition inequalities for three substructures arising in various mixed integer programs, namely the integer knapsack set with nonnegative divisible/arbitrary coefficients and two forms of single-node capacitated flow set with divisible … Read more

    Recoverable Robust Knapsacks: $\GammahBcScenarios

  • Christina Büsing
  • Arie M.C.A. Koster
  • Manuel Kutschka
    • Categories (Mixed) Integer Linear Programming, Robust Optimization Tags , , , ,

    In this paper, we investigate the recoverable robust knapsack problem, where the uncertainty of the item weights follows the approach of Bertsimas and Sim (2003,2004). In contrast to the robust approach, a limited recovery action is allowed, i.e., upto k items may be removed when the actual weights are known. This problem is motivated by … Read more

    Bound reduction using pairs of linear inequalities

  • Pietro Belotti
    • Categories (Mixed) Integer Linear Programming, (Mixed) Integer Nonlinear Programming, Constrained Nonlinear Optimization Tags , , ,

    We describe a procedure to reduce variable bounds in Mixed Integer Nonlinear Programming (MINLP) as well as Mixed Integer Linear Programming (MILP) problems. The procedure works by combining pairs of inequalities of a linear programming (LP) relaxation of the problem. This bound reduction technique extends the implied bounds procedure used in MINLP and MILP and … Read more

    Dippy — a simplified interface for advanced mixed-integer programming

  • Iain Dunning
  • Stuart Mitchell
  • Cameron Walker
  • Qi-Shan Lim
  • Michael O'Sullivan
    • Categories (Mixed) Integer Linear Programming, Branch and Cut Algorithms, Modeling Languages and Systems

    Mathematical modelling languages such as AMPL, GAMS, and Xpress-MP enable mathematical models such as mixed-integer linear programmes (MILPs) to be expressed clearly for solution in solvers such as CPLEX, MINOS and Gurobi. However some models are sufficiently difficult that they cannot be solved using “out-of-the-box” solvers, and customisation of the solver framework to exploit model-specific … Read more

    On the hyperplanes arrangements in mixed-integer techniques

  • Sorin Olaru
  • Florin Stoican
  • Ionela Prodan
    • Categories (Mixed) Integer Linear Programming

    This paper is concerned with the improved constraints handling in mixed-integer optimization problems. The novel element is the reduction of the number of binary variables used for expressing the complement of a convex (polytopic) region. As a generalization, the problem of representing the complement of a possibly non-connected union of such convex sets is detailed. … Read more

    A note on the MIR closure and basic relaxations of polyhedra

  • Sanjeeb Dash
  • Oktay Gunluk
  • Christian Raack
    • Categories (Mixed) Integer Linear Programming, Cutting Plane Approaches Tags , ,

    Anderson, Cornuejols and Li (2005) show that for a polyhedral mixed integer set defined by a constraint system Ax >= b, where x is n-dimensional, along with integrality restrictions on some of the variables, any split cut is in fact a split cut for a “basic relaxation”, i.e., one defined by a subset of linearly … Read more

    Formulations for Dynamic Lot Sizing with Service Levels

  • Dinakar Gade
  • Simge Küçükyavuz
    • Categories (Mixed) Integer Linear Programming, Applications - OR and Management Sciences, Combinatorial Optimization Tags , , , ,

    In this paper, we study deterministic dynamic lot-sizing problems with service level constraints on the total number of periods in which backorders can occur over the finite planning horizon. We give a natural mixed integer programming formulation for the single item problem (LS-SL-I) and study the structure of its solution. We show that an optimal … Read more

    Partial Convexification of General MIPs by Dantzig-Wolfe Reformulation

  • Martin Bergner
  • Alberto Caprara
  • Fabio Furini
  • Marco E. Lübbecke
  • Enrico Malaguti
  • Emiliano Traversi
    • Categories (Mixed) Integer Linear Programming

    Dantzig-Wolfe decomposition is well-known to provide strong dual bounds for specially structured mixed integer programs (MIPs) in practice. However, the method is not part of any state-of-the-art MIP solver: it needs tailoring to the particular problem; the typical bordered block-diagonal matrix structure determines the decomposition; the resulting column generation subproblems need to be solved efficiently; … Read more

    Optimizing the Layout of Proportional Symbol Maps: Polyhedra and Computation

  • Pedro J. de Rezende
  • Cid C. de Souza
  • Guilherme Kunigami
  • Tallys H. Yunes
    • Categories (Mixed) Integer Linear Programming, Basic Sciences Applications, Branch and Cut Algorithms Tags , , ,

    Proportional symbol maps are a cartographic tool to assist in the visualization and analysis of quantitative data associated with specific locations, such as earthquake magnitudes, oil well production, and temperature at weather stations. As the name suggests, symbol sizes are proportional to the magnitude of the physical quantities that they represent. We present two novel … Read more

    Using the analytic center in the feasibility pump

  • Daniel Baena
  • Jordi Castro
    • Categories (Mixed) Integer Linear Programming Tags , , , ,

    The feasibility pump (FP) [5,7] has proved to be a successful heuristic for finding feasible solutions of mixed integer linear problems (MILPs). FP was improved in [1] for finding better quality solutions. Briefly, FP alternates between two sequences of points: one of feasible so- lutions for the relaxed problem (but not integer), and another of … Read more