mixed-integer programming

On mixed integer reformulations of monotonic probabilistic programming problems with discrete distributions

  • Vladimir I. Norkin
    • Categories (Mixed) Integer Nonlinear Programming, Finance and Economics, Stochastic Programming Tags , , , , ,

    The paper studies large scale mixed integer reformulation approach to stochastic programming problems containing probability and quantile functions, under assumption of discreteness of the probability distribution involved. Jointly with general sample approximation technique and contemporary mixed integer programming solvers the approach gives a regular framework to solution of practical probabilistic programming problems. In the literature … Read more

    Aircraft landing problems with aircraft classes

  • Dirk Briskorn
  • Raik Stolletz
    • Categories Applications - OR and Management Sciences, Dynamic Programming, Transportation Tags , , , ,

    This paper focuses on the aircraft landing problem that is to assign landing times to aircraft approaching the airport under consideration. Each aircraft’s landing time must be in a time interval encompassing a target landing time. If the actual landing time deviates from the target landing time additional costs occur which depend on the amount … Read more

    Experiments with a Generic Dantzig-Wolfe Decomposition for Integer Programs

  • Gerald Gamrath
  • Marco E. Lübbecke
    • Categories (Mixed) Integer Linear Programming Tags , , ,

    We report on experiments with turning the branch-cut-and-price framework SCIP into a generic branch-cut-and-price solver. That is, given a mixed integer program (MIP), our code performs a Dantzig-Wolfe decomposition according to the user’s specification, and solves the resulting re-formulation via branch-and-price. We take care of the column generation subproblems which are solved as MIPs themselves, … Read more

    The Mcf-Separator – Detecting and Exploiting Multi-Commodity Flow Structures in MIPs

  • Tobias Achterberg
  • Christian Raack
    • Categories Branch and Cut Algorithms, Cutting Plane Approaches, Network Optimization Tags , , , , ,

    Given a general mixed integer program (MIP), we automatically detect block structures in the constraint matrix together with the coupling by capacity constraints arising from multi-commodity flow formulations. We identify the underlying graph and generate cutting planes based on cuts in the detected network. Our implementation adds a separator to the branch-and-cut libraries of Scip … Read more

    Concrete Structure Design Using Mixed-Integer Nonlinear Programming with Complementarity Constraints

  • Andres Guerra
  • Sven Leyffer
  • Alexandra Newman
    • Categories (Mixed) Integer Nonlinear Programming, Civil and Environmental Engineering, Complementarity and Variational Inequalities Tags , ,

    We present a mixed-integer nonlinear programming (MINLP) formulation to achieve minimum-cost designs for reinforced concrete (RC) structures that satisfy building code requirements. The objective function includes material and labor costs for concrete, steel reinforcing bars, and formwork according to typical contractor methods. Restrictions enforce correct geometry of the cross-section dimensions for each element and relative … Read more

    Two-Stage Robust Unit Commitment Problem

  • Yongpei Guan
  • Muhong Zhang
    • Categories Robust Optimization Tags , , ,

    As an energy market transforms from a regulated market to a deregulated one, the demands for a power plant are highly uncertain. In this paper, we study a two-stage robust optimization formulation and provide a tractable solution approach for the problem. The computational experiments show the effectiveness of our approach. Article Download View Two-Stage Robust … Read more

    Finite Disjunctive Programming Characterizations for General Mixed-Integer Linear Programs

  • Binyuan Chen
  • Simge Küçükyavuz
  • Suvrajeet Sen
    • Categories (Mixed) Integer Linear Programming, Cutting Plane Approaches Tags , , ,

    In this paper, we give a finite disjunctive programming procedure to obtain the convex hull of general mixed-integer linear programs (MILP) with bounded integer variables. We propose a finitely convergent convex hull tree algorithm which constructs a linear program that has the same optimal solution as the associated MILP. In addition, we combine the standard … Read more

    Lifting Group Inequalities and an Application to Mixing Inequalities

  • Santanu S. Dey
  • Laurence A. Wolsey
    • Categories (Mixed) Integer Linear Programming, Cutting Plane Approaches Tags , ,

    Given a valid inequality for the mixed integer infinite group relaxation, a lifting based approach is presented that can be used to strengthen this inequality. Bounds on the solution of the corresponding lifting problem and some necessary conditions for the lifted inequality to be minimal for the mixed integer infinite group relaxation are presented. Finally, … Read more

    Split Rank of Triangle and Quadrilateral Inequalities

  • Santanu S. Dey
  • Quentin Louveaux
    • Categories (Mixed) Integer Linear Programming, Cutting Plane Approaches Tags , ,

    A simple relaxation of two rows of a simplex tableau is a mixed integer set consisting of two equations with two free integer variables and non-negative continuous variables. Recently Andersen et al. (2007) and Cornuejols and Margot (2007) showed that the facet-defining inequalities of this set are either split cuts or intersection cuts obtained from … Read more

    Valid inequalities and Branch-and-Cut for the Clique Pricing Problem

  • Géraldine Heilporn
  • Martine Labbé
  • Patrice Marcotte
  • Gilles Savard
    • Categories (Mixed) Integer Linear Programming, Branch and Cut Algorithms Tags ,

    Motivated by an application in highway pricing, we consider the problem that consists in setting profit-maximizing tolls on a clique subset of a multicommodity transportation network. Following a proof that clique pricing is NP-hard, we propose strong valid inequalities, some of which define facets of the 2-commodity polyhedron. The numerical efficiency of these inequalities is … Read more