mixed-integer programming

Pseudo-Compact Formulations and Branch-and-Cut Approaches for the Capacitated Vehicle Routing Problem with Stochastic Demands

  • Caio Tomazella
  • Pedro Munari
  • Reinaldo Morabito
    • Categories (Mixed) Integer Linear Programming, Branch and Cut Algorithms, Stochastic Programming Tags , , ,

    In this paper, we address the Capacitated Vehicle Routing Problem with Stochastic Demands (CVRPSD), in which routes are planned a priori and recourse actions are performed to ensure demand fulfillment. These recourse actions are defined through policies and may include replenishment trips or demand backlogging subject to penalties. We develop the first family of pseudo-compact … Read more

    A cut-based mixed integer programming formulation for the hop-constrained cheapest path problem

  • Hamidreza Validi
    • Categories Combinatorial Optimization, Integer Programming, Network Optimization Tags , ,

    Given a simple graph G = (V, E) with edge cost c ∈ ℝ^|E|, a positive integer h, source s ∈ V and terminal t ∈ V, the hop-constrained cheapest path problem (HCCP) seeks to find an s–t path of length at most h hops with the cheapest cost. This paper proposes a cut-based mixed … Read more

    Speeding Up Mixed-Integer Programming Solvers with Sparse Learning for Branching

  • Selin Bayramoglu
  • George L. Nemhauser
  • Nikolaos Sahinidis
    • Categories (Mixed) Integer Linear Programming, Branch and Cut Algorithms Tags , ,

    Machine learning is increasingly used to improve decisions within branch-and-bound algorithms for mixed-integer programming. Many existing approaches rely on deep learning, which often requires very large training datasets and substantial computational resources for both training and deployment, typically with GPU parallelization. In this work, we take a different path by developing interpretable models that are … Read more

    Solving Convex Quadratic Optimization with Indicators Over Structured Graphs

  • Aaresh Bhathena
  • Salar Fattahi
  • Andrés Gómez
  • Simge Küçükyavuz
    • Categories (Mixed) Integer Nonlinear Programming, Dynamic Programming Tags ,

    This paper studies convex quadratic minimization problems in which each continuous variable is coupled with a binary indicator variable. We focus on the structured setting where the Hessian matrix of the quadratic term is positive definite and exhibits sparsity. We develop an exact parametric dynamic programming algorithm whose computational complexity depends explicitly on the treewidth … Read more

    Exact and Heuristic Methods for Gamma-Robust Min-Max Problems

  • Yasmine Beck
    • Categories Bilevel Optimization, Combinatorial Optimization, Robust Optimization Tags , , , ,

    Bilevel optimization is a powerful tool for modeling hierarchical decision-making processes, which arise in various real-world applications. Due to their nested structure, however, bilevel problems are intrinsically hard to solve—even if all variables are continuous and all parameters of the problem are exactly known. Further challenges arise if mixed-integer aspects and problems under uncertainty are … Read more

    Asymptotically tight Lagrangian dual of smooth nonconvex problems via improved error bound of Shapley-Folkman Lemma

  • Jingye Xu
    • Categories Convex Optimization, Nonlinear Optimization Tags , ,

    In convex geometry, the Shapley–Folkman Lemma asserts that the nonconvexity of a Minkowski sum of $n$-dimensional bounded nonconvex sets does not accumulate once the number of summands exceeds the dimension $n$, and thus the sum becomes approximately convex. Originally published by Starr in the context of quasi-equilibrium in nonconvex market models in economics, the lemma … Read more

    Clique Probing For Mixed-Integer-Programs

  • Jacob von Holly-Ponientzietz
  • Alexander Hoen
  • Mark Turner
  • Ambros Gleixner
    • Categories (Mixed) Integer Linear Programming, 0-1 Programming, Integer Programming Tags , ,

    Probing is an important presolving technique in mixed-integer programming solvers. It selects binary variables, tentatively fixes them to 0 and 1, and performs propagation to deduce additional variable fixings, bound tightenings, substitutions, and implications. In this work, we propose clique probing instead of probing on individual variables, we select cliques, a set of binary variables … Read more

    Optimizing Two-Tier Robotized Sorting Systems for Urban Parcel Delivery

  • Junsu Kim
  • Reem Khir
    • Categories (Mixed) Integer Linear Programming, Applications - OR and Management Sciences, Production and Logistics Tags , ,

    This paper addresses an operational planning challenge in two-tier robotized sorting systems (T-RSS), an emerging alternative to traditional conveyor-based sorting in e-commerce delivery stations. Designed to be compact and space-efficient, T-RSS use an upper tier to sort parcels from loading stations to drop-off points, which connect to roll containers on a lower tier where parcels … Read more

    Branch and price for nonlinear production-maintenance scheduling in complex machinery

  • João Dionísio
  • Ambros Gleixner
  • João Pedro Pedroso
  • Ksenia Bestuzheva
    • Categories (Mixed) Integer Nonlinear Programming, Production and Logistics, Scheduling Tags , , , ,

    This paper proposes a mixed-integer nonlinear programming approach for joint scheduling of long-term maintenance decisions and short-term production for groups of complex machines with multiple interacting components. We introduce an abstract model where the production and the condition of machines are described by convex functions, allowing the model to be employed for various application areas … Read more

    Smoothie: Mixing the strongest MIP solvers to solve hard MIP instances on supercomputers – Phase I development

  • Yuji Shinano
  • Stefan Vigerske
    • Categories (Mixed) Integer Linear Programming, Parallel Algorithms Tags , , ,

    Mixed-Integer Linear Programming (MIP) is applicable to such a wide range of real-world decision problems that the competition for the best code to solve such problems has lead to tremendous progress over the last decades. While current solvers can solve some of the problems that seemed completely out-of-reach just 10 years ago, there are always … Read more