Machine-learning-enhanced strategies to generate subtour elimination constraints for the symmetric traveling salesman problem

  • FB Akcay
  • Maxence Delorme
  • Ulrich Pferschy
    • Categories Combinatorial Optimization, Integer Programming Tags , , , ,

    We present a machine learning (ML) component designed to enhance the well-known branch-and-cut (B&C) framework for the symmetric traveling salesman problem (TSP) in which only the subtour elimination constraints (SECs) violated by previously found integer solutions are considered. The objective of the ML component is to identify which SECs, from a pool of candidates, will … Read more

    An Interpretable Ensemble Heuristic for Principal-Agent Games with Machine Learning

  • I. Esra Buyuktahtakin Toy
    • Categories Applications - OR and Management Sciences, Game Theory, Optimization in Data Science

    This paper addresses the challenge of enhancing public policy decision-making by efficiently solving principal-agent models (PAMs) for public-private partnerships, a critical yet computationally demanding problem. We develop a fast, interpretable, and generalizable approach to support policy decisions under these settings. We propose an interpretable ensemble heuristic (EH) that integrates Machine Learning (ML), Operations Research (OR), … Read more

    Deep Learning for Sequential Decision Making under Uncertainty: Foundations, Frameworks, and Frontiers

  • I. Esra Buyuktahtakin Toy
    • Categories Data Science Algorithms, Optimization in Data Science, Stochastic Programming Tags , , , , , , , , , , ,

    Artificial intelligence (AI) is moving increasingly beyond prediction to support decisions in complex, uncertain, and dynamic environments. This shift creates a natural intersection with operations research and management sciences (OR/MS), which have long offered conceptual and methodological foundations for sequential decision-making under uncertainty. At the same time, recent advances in deep learning, including feedforward neural … Read more

    Decomposition-Based Reformulation of Nonseparable Quadratic Expressions in Convex MINLP

  • Joakim Blomqvist
  • Erik Tamm
  • Jan Kronqvist
  • Andreas Lundell
    • Categories (Mixed) Integer Nonlinear Programming, Convex Optimization, Global Optimization Tags , , , , , ,

    In this paper, we present a reformulation technique for convex mixed-integer nonlinear programming (MINLP) problems with nonseparable quadratic terms. For each convex non-diagonal matrix that defines quadratic expressions in the problem, we show that an eigenvalue or LDLT decomposition can be performed to transform the quadratic expressions into convex additively separable constraints. The reformulated problem … 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

    Multi-Leader Single-Follower Power-Market Modeling: The Impact of DC Market-Clearing on AC Feasibility

  • Martina Cerulli
  • Claudia D'Ambrosio
  • Leo Liberti
  • Martin Schmidt
    • Categories Bilevel Optimization, Energy Tags , , , ,

    We study the impact of DC power flow modeling in multi-leader single-follower market models on the AC feasibility of the market outcome. To this end, we consider strategically bidding power producers that are connected to an electricity network and a market-clearing executed by an ISO. The focus is on a pay-as-bid electricity market in which … Read more

    An Inexact Trust-Region Method for Structured Nonsmooth Optimization with Application to Risk-Averse Stochastic Programming

  • Drew P. Kouri
    • Categories Nonsmooth Optimization, Optimization of Systems modeled by PDEs, Stochastic Programming Tags , , , , ,

    We develop a trust-region method for efficiently minimizing the sum of a smooth function, a nonsmooth convex function, and the composition of a finite-valued support function with a smooth function. Optimization problems with this structure arise in numerous applications including risk-averse stochastic programming and subproblems for nonsmooth penalty nonlinear programming methods. Our method permits the … Read more

    Distributionally Robust Chance-Constrained Optimal Load Shedding Model for Active Distribution Networks Based on KDE

  • Xiaotong Qi
  • Wei Liu
  • Bo Yu
  • Li Yang
    • Categories Applications - Science and Engineering, Energy, Robust Optimization

    With the high penetration of distributed energy resources in active distribution networks(ADNs), forecast errors from renewables and loads pose significant risks of bilateral violations, including overvoltage/undervoltage and line overloads. To address this challenge, this paper proposes a KDE-DRCCO model that integrates kernel density estimation (KDE) with distributionally robust chance-constrained optimization (DRCCO). Leveraging the radial topology … 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

    On the Single-Multi-Commodity Gap: Lifting Single- to Multicommodity Flow Instances

  • Felix P. Broesamle
  • Stefan Nickel
    • Categories Applications - OR and Management Sciences, Linear Programming, Network Optimization Tags , , , , ,

    Benchmark instances for multicommodity flow problems frequently lack the structural nuances of real-world networks or fail to maintain a rigorous mathematical relationship with their single-commodity counterparts. This paper introduces a formal meta-generation framework that addresses these limitations by lifting single-commodity minimum-cost flow instances into the multicommodity space while strictly preserving the underlying network topology, capacity … Read more