Integer Programming

Computing an approximation of the nondominated set of multi-objective mixed-integer nonlinear optimization problems

  • Leo Warnow
  • Gabriele Eichfelder
    • Categories (Mixed) Integer Nonlinear Programming, Global Optimization, Multi-Criteria Optimization Tags , , , ,

    In practical applications, one often has not only one, but several objectives that need to be optimized simultaneously. What is more, modeling such real world problems usually involves using both, continuous and integer variables. This then results in multi-objective mixed-integer optimization problems, which are in focus of this paper. We present an approximation concept, called … Read more

    A two-stage stochastic programming approach incorporating spatially-explicit fire scenarios for optimal firebreak placement

  • Sebastián Dávila
  • Andres Weintraub
  • Franco Quezada
  • Jaime
    • Categories (Mixed) Integer Linear Programming, Stochastic Programming Tags , , , ,

    Ensuring the effective placement of firebreaks across the landscape is a critical issue in wildfire prevention, as their success relies on their ability to block the spread of future fires. To address this challenge, it is essential to recognize the stochastic nature of fires, which are highly unpredictable from start to finish. The issue is … Read more

    Facets of the knapsack polytope from non-minimal covers

  • Guneshwar Anand
  • Sachin Jayaswal
  • B. Srirangacharyulu
    • Categories (Mixed) Integer Linear Programming, Polyhedra, Transportation Tags , , , , ,

    We propose two new classes of valid inequalities (VIs) for the binary knapsack polytope, based on non-minimal covers. We also show that these VIs can be obtained through neither sequential nor simultaneous lifting of well-known cover inequalities. We further provide conditions under which they are facet-defining. The usefulness of these VIs is demonstrated using computational … Read more

    Solving Nonconvex Optimization Problems using Outer Approximations of the Set-Copositive Cone

  • Kurt M. Anstreicher
  • MarkusGabl
    • Categories (Mixed) Integer Nonlinear Programming, Cone Programming, Global Optimization Theory Tags , ,

    We consider the solution of nonconvex quadratic optimization problems using an outer approximation of the set-copositive cone that is iteratively strengthened with conic constraints and cutting planes. Our methodology utilizes an MILP-based oracle for a generalization of the copositive cone that considers additional linear equality constraints. In numerical testing we evaluate our algorithm on a … Read more

    Relaxation strength for multilinear optimization: McCormick strikes back

  • Matthias Walter
    • Categories (Mixed) Integer Linear Programming, Nonlinear Optimization, Polyhedra Tags , , , , ,

    We consider linear relaxations for multilinear optimization problems. In a recent paper, Khajavirad proved that the extended flower relaxation is at least as strong as the relaxation of any recursive McCormick linearization (Operations Research Letters 51 (2023) 146-152). In this paper we extend the result to more general linearizations, and present a simpler proof. Moreover, … Read more

    Combining Precision Boosting with LP Iterative Refinement for Exact Linear Optimization

  • Leon Eifler
  • Ambros Gleixner
    • Categories (Mixed) Integer Linear Programming, Linear Programming, Other Topics Tags , , ,

    This article studies a combination of the two state-of-the-art algorithms for the exact solution of linear programs (LPs) over the rational numbers, i.e., without any roundoff errors or numerical tolerances. By integrating the method of precision boosting inside an LP iterative refinement loop, the combined algorithm is able to leverage the strengths of both methods: … Read more

    The Impact of Symmetry Handling for the Stable Set Problem via Schreier-Sims Cuts

  • Christopher Hojny
  • Marc E. Pfetsch
  • José Verschae
    • Categories Integer Programming Tags , , ,

    Symmetry handling inequalities (SHIs) are an appealing and popular tool for handling symmetries in integer programming. Despite their practical application, little is known about their interaction with optimization problems. This article focuses on Schreier-Sims (SST) cuts, a recently introduced family of SHIs, and investigate their impact on the computational and polyhedral complexity of optimization problems. … Read more

    Cross-Dock Trailer Scheduling with Workforce Constraints: A Dynamic Discretization Discovery Approach

  • Ritesh Ojha
  • Alan L. Erera
    • Categories (Mixed) Integer Linear Programming, Scheduling Tags , ,

    LTL freight carriers operate consolidation networks that utilize cross-docking terminals to facilitate thetransfer of freight between trailers and enhance trailer utilization. This research addresses the problem ofdetermining an optimal schedule for unloading inbound trailers at specific unloading doors using teams ofdock workers. The optimization objective is chosen to ensure that outbound trailers are loaded with … Read more

    A proof system for certifying symmetry and optimality reasoning in integer programming

  • Jasper van Doornmalen
  • Leon Eifler
  • Ambros Gleixner
  • Christopher Hojny
    • Categories (Mixed) Integer Linear Programming Tags , , , ,

    We present a proof system for establishing the correctness of results produced by optimization algorithms, with a focus on mixed-integer programming (MIP). Our system generalizes the seminal work of Bogaerts, Gocht, McCreesh, and Nordström (2022) for binary programs to handle any additional difficulties arising from unbounded and continuous variables, and covers a broad range of … Read more

    Branch-and-Bound versus Lift-and-Project Relaxations in Combinatorial Optimization

  • Yatharth Dubey
  • Gérard Cornuéjols
    • Categories 0-1 Programming, Branch and Cut Algorithms Tags , ,

    In this paper, we consider a theoretical framework for comparing branch-and-bound with classical lift-and-project hierarchies. We simplify our analysis of streamlining the definition of branch-and-bound. We introduce “skewed $k$-trees” which give a hierarchy of relaxations that is incomparable to that of Sherali-Adams, and we show that it is much better for some instances. We also … Read more