Integer Programming

Two-row and two-column mixed-integer presolve using hash-based pairing methods

  • Weikun Chen
  • Ambros Gleixner
  • Dieter Weninger
  • Patrick Gemander
  • Leona Gottwald
  • Alexander Martin
    • Categories (Mixed) Integer Linear Programming, Optimization Software Benchmark, Polyhedra Tags , , ,

    In state-of-the-art mixed-integer programming solvers, a large array of reduction techniques are applied to simplify the problem and strengthen the model formulation before starting the actual branch-and-cut phase. Despite their mathematical simplicity, these methods can have significant impact on the solvability of a given problem. However, a crucial property for employing presolving techniques successfully is … Read more

    The risk-averse ultimate pit problem

  • Gianpiero Canessa
  • Bernardo K. Pagnoncelli
  • Eduardo Moreno
    • Categories 0-1 Programming, Stochastic Programming

    In this work, we consider a risk-averse ultimate pit problem where the grade of the mineral is uncertain. We propose a two-stage formulation of the problem and discuss which properties are desirable for a risk measure in this context. We show that the only risk measure that satisfies these properties is the entropic. We propose … Read more

    Branch-and-Cut-and-Price for Multi-Agent Pathfinding

  • Daniel Harabor
  • Edward Lam
  • Pierre Le Bodic
  • Peter J. Stuckey
    • Categories 0-1 Programming, Branch and Cut Algorithms, Transportation Tags , , , ,

    There are currently two broad strategies for optimal Multi-agent Pathfinding (MAPF): (1) search-based methods, which model and solve MAPF directly, and (2) compilation-based solvers, which reduce MAPF to instances of well-known combinatorial problems, and thus, can benefit from advances in solver techniques. In this work, we present an optimal algorithm, BCP, that hybridizes both approaches … Read more

    Logic-based Benders Decomposition and Binary Decision Diagram Based Approaches for Stochastic Distributed Operating Room Scheduling

  • Dionne M. Aleman
  • Merve Bodur
  • Cheng Guo
  • David R. Urbach
    • Categories Cutting Plane Approaches, Scheduling, Stochastic Programming

    The distributed operating room (OR) scheduling problem aims to find an assignment of surgeries to ORs across collaborating hospitals that share their waiting lists and ORs. We propose a stochastic extension of this problem where surgery durations are considered to be uncertain. In order to obtain solutions for the challenging stochastic model, we use sample … Read more

    Integer Programming, Constraint Programming, and Hybrid Decomposition Approaches to Discretizable Distance Geometry Problems

  • Merve Bodur
  • Moira MacNeil
    • Categories Branch and Cut Algorithms, Integer Programming, Other Topics Tags , , , ,

    Given an integer dimension K and a simple, undirected graph G with positive edge weights, the Distance Geometry Problem (DGP) aims to find a realization function mapping each vertex to a coordinate in K-dimensional space such that the distance between pairs of vertex coordinates is equal to the corresponding edge weights in G. The so-called … Read more

    Near-optimal Robust Bilevel Optimization

  • Miguel F. Anjos
  • Mathieu Besançon
  • Luce Brotcorne
    • Categories (Mixed) Integer Nonlinear Programming, Complementarity and Variational Inequalities, Robust Optimization Tags , , , , , ,

    Bilevel optimization studies problems where the optimal response to a second mathematical optimization problem is integrated in the constraints. Such structure arises in a variety of decision-making problems in areas such as market equilibria, policy design or product pricing. We introduce near-optimal robustness for bilevel problems, protecting the upper-level decision-maker from bounded rationality at the … Read more

    Solving Heated Oil Pipeline Problems Via Mixed Integer Nonlinear Programming Approach

  • Yu-Hong Dai
  • Yakui Huang
  • Bo Li
  • Muming Yang
    • Categories (Mixed) Integer Nonlinear Programming, Applications - OR and Management Sciences Tags , , , , , ,

    It is a crucial problem how to heat oil and save running cost for crude oil transport. This paper strictly formulates such a heated oil pipeline problem as a mixed integer nonlinear programming model. Nonconvex and convex continuous relaxations of the model are proposed, which are proved to be equivalent under some suitable conditions. Meanwhile, … Read more

    A Bilevel Approach for Identifying the Worst Contingencies for Nonconvex Alternating Current Power Systems

  • Brian Dandurand
  • Kibaek Kim
  • Sven Leyffer
    • Categories (Mixed) Integer Nonlinear Programming, Branch and Cut Algorithms, Robust Optimization Tags , , ,

    We address the bilevel optimization problem of identifying the most critical attacks to an alternating current (AC) power flow network. The upper-level binary maximization problem consists in choosing an attack that is treated as a parameter in the lower-level defender minimization problem. Instances of the lower-level global minimization problem by themselves are NP-hard due to … Read more

    Decomposition-based approaches for a class of two-stage robust binary optimization problems

  • Ayse Nur Arslan
  • Boris Detienne
    • Categories 0-1 Programming, Robust Optimization Tags , , ,

    In this paper, we study a class of two-stage robust binary optimization problems with objective uncertainty where recourse decisions are restricted to be mixed-binary. For these problems, we present a deterministic equivalent formulation through the convexification of the recourse feasible region. We then explore this formulation under the lens of a relaxation, showing that the … Read more

    Visible points, the separation problem, and applications to MINLP

  • Felipe Serrano
    • Categories (Mixed) Integer Nonlinear Programming, Cutting Plane Approaches, Global Optimization Tags , , , ,

    In this paper we introduce a technique to produce tighter cutting planes for mixed-integer non-linear programs. Usually, a cutting plane is generated to cut off a specific infeasible point. The underlying idea is to use the infeasible point to restrict the feasible region in order to obtain a tighter domain. To ensure validity, we require … Read more