mixed-integer programming

A MIP Approach for some Practical Packing Problems: Balancing Constraints and Tetris-like Items

  • Giorgio Fasano
    • Categories (Mixed) Integer Linear Programming, Applications - OR and Management Sciences Tags , , , ,

    This paper considers packing problems with balancing conditions and items consisting of clusters of parallelepipeds (mutually orthogonal, i.e. tetris-like items). This issue is quite frequent in space engineering and a real-world application deals with the Automated Transfer Vehicle project (funded by the European Space Agency), at present under development. A Mixed Integer Programming (MIP) approach … Read more

    Some Relations Between Facets of Low- and High-Dimensional Group Problems

  • Santanu S. Dey
  • Jean-Philippe P. Richard
    • Categories (Mixed) Integer Linear Programming, Cutting Plane Approaches Tags ,

    In this paper, we introduce an operation that creates families of facet-defining inequalities for high-dimensional infinite group problems using facet-defining inequalities of lower-dimensional group problems. We call this family sequential-merge inequalities because they are produced by applying two group cuts one after the other and because the resultant inequality depends on the order of the … Read more

    Maximum Utility Product Pricing Models and Algorithms Based on Reservation Prices

  • Tor G.J. Myklebust
  • Romy Shioda
  • Levent Tunçel
    • Categories Applications - OR and Management Sciences Tags , ,

    We consider a revenue management model for pricing a product line with several customer segments under the assumption that customers’ product choices are determined entirely by their reservation prices. We highlight key mathematical properties of the maximum utility model and formulate it as a mixed-integer programming problem, design heuristics and valid cuts. We further present … Read more

    A Short Note on the Probabilistic Set Covering Problem

  • Anureet Saxena
    • Categories 0-1 Programming, Cutting Plane Approaches, Stochastic Programming Tags , , ,

    In this paper we address the following probabilistic version (PSC) of the set covering problem: min { cx | P (Ax>= xi) >= p, x_{j} in {0,1} j in N} where A is a 0-1 matrix, xi is a random 0-1 vector and p in (0,1] is the threshold probability level. In a recent development … Read more

    Efficient Formulations for the Multi-Floor Facility Layout Problem with Elevators

  • Marc Goetschalckx
  • Takashi Irohara
    • Categories (Mixed) Integer Linear Programming, Facility Planning and Design, Production and Logistics Tags , , , ,

    The block layout problem for a multi-floor facility is an important sub class of the facility layout problem with practical applications when the price of land is high or when a compact building allows for more efficient environmental control. Several alternative formulations for the block layout problem of a multi-floor facility are presented, where the … Read more

    MIP Reformulations of the Probabilistic Set Covering Problem

  • Vineet Goyal
  • Miguel A. Lejeune
  • Anureet Saxena
    • Categories 0-1 Programming, Cutting Plane Approaches, Stochastic Programming Tags , , ,

    In this paper we address the following probabilistic version (PSC) of the set covering problem: $min \{ cx \ |\ {\mathbb P} (Ax\ge \xi) \ge p,\ x_{j}\in \{0,1\}^N\}$ where $A$ is a 0-1 matrix, $\xi$ is a random 0-1 vector and $p\in (0,1]$ is the threshold probability level. We formulate (PSC) as a mixed integer … Read more

    The Mixing-MIR Set with Divisible Capacities

  • Ismael de Farias
  • Ming Zhao
    • Categories (Mixed) Integer Linear Programming, Cutting Plane Approaches, Integer Programming Tags , , , , ,

    We study the set $S = \{(x, y) \in \Re_{+} \times Z^{n}: x + B_{j} y_{j} \geq b_{j}, j = 1, \ldots, n\}$, where $B_{j}, b_{j} \in \Re_{+} – \{0\}$, $j = 1, \ldots, n$, and $B_{1} | \cdots | B_{n}$. The set $S$ generalizes the mixed-integer rounding (MIR) set of Nemhauser and Wolsey and … Read more

    Extreme inequalities for infinite group problems

  • Santanu S. Dey
  • Yanjun Li
  • Jean-Philippe P. Richard
  • Lisa A. Miller
    • Categories (Mixed) Integer Linear Programming, Cutting Plane Approaches Tags , , ,

    In this paper we derive new properties of extreme inequalities for infinite group problems. We develop tools to prove that given valid inequalities for the infinite group problem are extreme. These results show that integer infinite group problems have discontinuous extreme inequalities. These inequalities are strong when compared to related classes of continuous extreme inequalities. … Read more

    Using mixed-integer programming to solve power grid blackout problems

  • Daniel Bienstock
  • Sara Mattia
    • Categories Applications - OR and Management Sciences Tags , ,

    We consider optimization problems related to the prevention of large-scale cascading blackouts in power transmission networks subject to multiple scenarios of externally caused damage. We present computation with networks with up to 600 nodes and 827 edges, and many thousands of damage scenarios. Citation CORC Report TR-2005-07, Columbia University Article Download View Using mixed-integer programming … Read more

    MIP-based heuristics for multi-item capacitated lot-sizing problem with setup times and shortage costs

  • Nabil Absi
  • Safia Kedad-Sidhoum
    • Categories Applications - OR and Management Sciences Tags , , , , , ,

    We address a multi-item capacitated lot-sizing problem with setup times that arises in real-world production planning contexts. Demand cannot be backlogged, but can be totally or partially lost. Safety stock is an objective to reach rather than an industrial constraint to respect. The problem is NP-hard. A mixed integer mathematical formulation is presented. We propose … Read more