(Mixed) Integer Linear Programming

Pricing Discrete and Nonlinear Markets With Semidefinite Relaxations

  • Cheng Guo
  • Lauren Henderson
  • Ryan Cory-Wright
  • Boshi Yang
    • Categories (Mixed) Integer Linear Programming, Applications - OR and Management Sciences, Semi-definite Programming Tags , , , ,

    Nonconvexities in markets with discrete decisions and nonlinear constraints make efficient pricing challenging, often necessitating subsidies. A prime example is the unit commitment (UC) problem in electricity markets, where costly subsidies are commonly required. We propose a new pricing scheme for nonconvex markets with both discreteness and nonlinearity, by convexifying nonconvex structures through a semidefinite … Read more

    Adaptive Subproblem Selection in Benders Decomposition for Survivable Network Design Problems

  • Tim Donkiewicz
    • Categories (Mixed) Integer Linear Programming, Branch and Cut Algorithms, Network Optimization

    Scenario-based optimization problems can be solved via Benders decomposition, which separates first-stage (master problem) decisions from second-stage (subproblem) recourse actions and iteratively refines the master problem with Benders cuts. In conventional Benders decomposition, all subproblems are solved at each iteration. For problems with many scenarios, solving only a selected subset can reduce computation. We quantify … 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

    Folding Mixed-Integer Linear Programs and Reflection Symmetries

  • Rolf van der Hulst
    • Categories (Mixed) Integer Linear Programming, Linear Programming Tags , , , ,

    For mixed-integer linear programming and linear programming it is well known that symmetries can have a negative impact on the performance of branch-and-bound and linear optimization algorithms. A common strategy to handle symmetries in linear programs is to reduce the dimension of the linear program by aggregating symmetric variables and solving a linear program of … Read more

    Integral Inverse Optimization Problems

  • Eva Ley
  • Maximilian Merkert
    • Categories (Mixed) Integer Linear Programming, Bilevel Optimization Tags , ,

    Inverse optimization problems are bilevel optimization problems in which the leader modifies the follower’s objective such that a prescribed feasible solution becomes an optimal solution of the follower. They capture hierarchical decision-making problems like parameter estimation tasks or situations where a planner wants to steer an agent’s choice. In this work, we study integral inverse … Read more

    Zimpler – Integer Programming, easier

  • Javier Martínez-Viademonte
    • Categories (Mixed) Integer Linear Programming, Modeling Languages and Systems Tags , , , ,

    This paper introduces Zimpler, a free tool built on the ZIMPL modeling language to streamline the solution of mixed-integer linear programs (MILP). Zimpler extends existing ZIMPL workflows by integrating native data sources—such as Excel spreadsheets—without requiring manual conversion to text-based tables. In addition, it supports solution refinement by adapting solver outputs into alternative formats, including … Read more

    A Surface-Based Formulation of the Traveling Salesman Problem

  • Yılmaz Arslanoğlu
    • Categories (Mixed) Integer Linear Programming, Other Topics Tags , , , ,

    We present an exact formulation of the symmetric Traveling Salesman Problem (TSP) that replaces the classical edge-selection view with a surface-building approach. Instead of selecting edges to form a cycle, the model selects a set of connected triangles where the boundary of the resulting surface forms the tour. This method yields a mixed-integer linear programming … Read more

    The colored knapsack problem: structural properties and exact algorithms

  • Fabio Ciccarelli
  • Alexander Helber
  • Erik Mühmer
    • Categories (Mixed) Integer Linear Programming, Combinatorial Optimization, Dynamic Programming Tags , , , ,

    We introduce and study a novel generalization of the classical Knapsack Problem (KP), called the Colored Knapsack Problem (CKP). In this problem, the items are partitioned into classes of colors and the packed items need to be ordered such that no consecutive items are of the same color. We establish that the problem is weakly … Read more

    A simulation framework for Formula 1 race strategy based on pit-stop optimization

  • Mario Borruso
  • Pasquale Avella
  • mattia_marino
    • Categories (Mixed) Integer Linear Programming, Linear Programming, Optimization Software and Modeling Systems Tags , , , ,

    In modern Formula~1, strict regulations and highly optimized cars limit performance gains through hardware, increasing the importance of strategic decision-making. This work tackles the problem of computing a race strategy that minimizes total race time by jointly optimizing tire stints, compound selection, fuel load, and Energy Recovery System (ERS) deployment. We present a high-performance simulation … Read more

    A Structural Equivalence of Symmetric TSP to a Constrained Group Steiner Tree Problem

  • Yılmaz Arslanoğlu
    • Categories (Mixed) Integer Linear Programming, Approximation Algorithms Tags , , , ,

    We present a brief structural equivalence between the symmetric TSP and a constrained Group Steiner Tree Problem (cGSTP) defined on a simplicial incidence graph. Given the complete weighted graph on the city set V, we form the bipartite incidence graph between triangles and edges. Selecting an admissible, disk-like set of triangles induces a unique boundary … Read more