cutting planes

Modeling Binary Relations in Piecewise-Linear Approximations

  • Kristin Braun
  • Robert Burlacu
  • Tobias Kuen
  • kristinarolsing
    • Categories Combinatorial Optimization, Global Optimization Theory, Nonlinear Optimization Tags , , , , ,

    Over the last decades, using piecewise-linear mixed-integer relaxations of nonlinear expressions has become a strong alternative to spatial branching for solving mixed-integer nonlinear programs. Since these relaxations give rise to large numbers of binary variables that encode interval selections, strengthening them is crucial. We investigate how to exploit the resulting combinatorial structure by integrating cutting-plane … Read more

    Semidefinite programming via Projective Cutting Planes for dense (easily-feasible) instances

  • Daniel Porumbel
    • Categories Linear, Cone and Semidefinite Programming, Semi-definite Programming Tags , ,

    The cone of positive semi-definite (SDP) matrices can be described by an infinite number of linear constraints. It is well-known that one can optimize over such a feasible area by standard Cutting Planes, but work on this idea remains a rare sight, likely due to its limited practical appeal compared to Interior Point Methods (IPMs). … Read more

    The Branch-and-Bound Tree Closure

  • Marius Roland
  • Nagisa Sugishita
  • Alexandre Forel
  • Youssouf Emine
  • Ricardo Fukasawa
  • Thibaut Vidal
    • Categories (Mixed) Integer Linear Programming, 0-1 Programming, Cutting Plane Approaches Tags , ,

    This paper investigates the a-posteriori analysis of Branch-and-Bound (BB) trees to extract structural information about the feasible region of mixed-binary linear programs. We introduce three novel outer approximations of the feasible region, systematically constructed from a BB tree. These are: a tight formulation based on disjunctive programming, a branching-based formulation derived from the tree’s branching … Read more

    Solving the Partial Inverse Knapsack Problem

  • Eva Ley
  • Nikolas Lykourinos
  • Maximilian Merkert
  • Andreas M. Tillmann
    • Categories (Mixed) Integer Linear Programming, Bilevel Optimization, Branch and Cut Algorithms Tags , , , ,

    In this paper, we investigate the partial inverse knapsack problem, a bilevel optimization problem in which the follower solves a classical 0/1-knapsack problem with item profit values comprised of a fixed part and a modification determined by the leader. Specifically, the leader problem seeks a minimal change to given item profits such that there is … Read more

    Branch-and-Cut for Mixed-Integer Nash Equilibrium Problems

  • Alois Duguet
  • Tobias Harks
  • Martin Schmidt
  • Julian Schwarz
    • Categories (Mixed) Integer Linear Programming, Bilevel Optimization, Game Theory Tags , , , ,

    We consider Nash equilibrium problems with mixed-integer variables in which each player solves a mixed-integer optimization problem parameterized in the rivals’ strategies. We distinguish between standard Nash equilibrium problems (NEP), where the parameterization acts only on the players’ cost functions and generalized Nash equilibrium problems (GNEPs), where, additionally, the strategy spaces of the players may … Read more

    Solving Multi-Follower Mixed-Integer Bilevel Problems with Binary Linking Variables

  • Vladimir Stadnichuk
  • Arie M.C.A. Koster
    • Categories (Mixed) Integer Linear Programming, Cutting Plane Approaches, Network Optimization Tags , , , ,

    We study multi-follower bilevel optimization problems with binary linking variables where the second level consists of many independent integer-constrained subproblems. This problem class not only generalizes many classical interdiction problems but also arises naturally in many network design problems where the second-level subproblems involve complex routing decisions of the actors involved. We propose a novel … Read more

    Cut-based Conflict Analysis in Mixed Integer Programming

  • Gioni Mexi
  • Felipe Serrano
  • Timo Berthold
  • Ambros Gleixner
  • jakobnordstrom
    • Categories (Mixed) Integer Linear Programming, 0-1 Programming, Integer Programming Tags , , , , ,

    For almost two decades, mixed integer programming (MIP) solvers have used graph- based conflict analysis to learn from local infeasibilities during branch-and-bound search. In this paper, we improve MIP conflict analysis by instead using reasoning based on cuts, inspired by the development of conflict-driven solvers for pseudo- Boolean optimization. Phrased in MIP terminology, this type … Read more

    A graphical framework for global optimization of mixed-integer nonlinear programs

  • Danial Davarnia
    • Categories (Mixed) Integer Nonlinear Programming, Global Optimization Applications, Global Optimization Theory Tags , , , , ,

    While mixed-integer linear programming and convex programming solvers have advanced significantly over the past several decades, solution technologies for general mixed-integer nonlinear programs (MINLPs) have yet to reach the same level of maturity. Various problem structures across different application domains remain challenging to model and solve using modern global solvers, primarily due to the lack … Read more

    A Decomposition Algorithm for Distributionally Robust Chance-Constrained Programs with Polyhedral Ambiguity Set

  • Hamed Rahimian
    • Categories Stochastic Programming Tags , , ,

    In this paper, we study a distributionally robust optimization approach to chance-constrained stochastic programs to hedge against uncertainty in the distributions of the random parameters. We consider a general polyhedral ambiguity set under finite support and study Wasserstein ambiguity set, total variation distance ambiguity set, and moment-based ambiguity set as examples for our computations. We … Read more

    A computational study of cutting-plane methods for multi-stage stochastic integer programs

  • Akul Bansal
  • Simge Küçükyavuz
    • Categories Stochastic Programming Tags , ,

    We report a computational study of cutting plane algorithms for multi-stage stochastic mixed-integer programming models with the following cuts: (i) Benders’, (ii) Integer L-shaped, and (iii) Lagrangian cuts. We first show that Integer L-shaped cuts correspond to one of the optimal solutions of the Lagrangian dual problem, and, therefore, belong to the class of Lagrangian … Read more