Integer Programming

ODTlearn: A Package for Learning Optimal Decision Trees for Prediction and Prescription

  • Patrick Vossler
  • Sina Aghaei
  • Nathan Justin
  • Nathanael Jo
  • Andrés Gómez
  • Phebe Vayanos
    • Categories (Mixed) Integer Linear Programming, Optimization Software and Modeling Systems Tags , , , , , ,

    ODTLearn is an open-source Python package that provides methods for learning optimal decision trees for high-stakes predictive and prescriptive tasks based on the mixed-integer optimization (MIO) framework proposed in Aghaei et al. (2019) and several of its extensions. The current version of the package provides implementations for learning optimal classification trees, optimal fair classification trees, … Read more

    Delay-Resistant Robust Vehicle Routing with Heterogeneous Time Windows

  • Lukas Schürmann
  • Tim Niemann
  • Petra Mutzel
  • Andreas M. Tillmann
  • Sebastian Stiller
    • Categories Combinatorial Optimization, Integer Programming, Transportation Tags , , ,

    We consider a robust variant of the vehicle routing problem with heterogeneous time windows (RVRP-HTW) with a focus on delay-resistant solutions. Here, customers have different availability time windows for every vehicle and must be provided with a preferably tight appointment window for the planned service. Different vehicles are a possibility to model different days on … Read more

    Dual Conflict Analysis for Mixed-Integer Semidefinite Programs

  • Marc E. Pfetsch
    • Categories (Mixed) Integer Linear Programming, Semi-definite Programming Tags ,

    Conflict analysis originally tried to exploit the knowledge that certain nodes in a relaxation-based branch-and-bound are infeasible. It has been extended to derive valid constraints also from feasible nodes. This paper adapts this approach to mixed-integer semidefinite programs. Using dual solutions, the primal constraints are aggregated and the resulting inequalities can be used at different … Read more

    Solution Path of Time-varying Markov Random Fields with Discrete Regularization

  • Salar Fattahi
  • Andrés Gómez
    • Categories Dynamic Programming, Integer Programming, Optimization in Data Science

    \(\) We study the problem of inferring sparse time-varying Markov random fields (MRFs) with different discrete and temporal regularizations on the parameters. Due to the intractability of discrete regularization, most approaches for solving this problem rely on the so-called maximum-likelihood estimation (MLE) with relaxed regularization, which neither results in ideal statistical properties nor scale to … Read more

    A Tutorial on Solving Single-Leader-Multi-Follower Problems using SOS1 Reformulations

  • Didier Aussel
  • Cecile Egea
  • Martin Schmidt
    • Categories (Mixed) Integer Linear Programming, Complementarity and Variational Inequalities, Game Theory Tags , , ,

    In this tutorial we consider single-leader-multi-follower games in which the models of the lower-level players have polyhedral feasible sets and convex objective functions. This situation allows for classic KKT reformulations of the separate lower-level problems, which lead to challenging single-level reformulations of MPCC type. The main contribution of this tutorial is to present a ready-to-use … Read more

    Essays on Average Incremental Cost Pricing for Independent System Operators

  • Richard O'Neill
  • Yonghong Chen
  • Brent Eldridge
    • Categories (Mixed) Integer Linear Programming Tags ,

    In a series of essays, we introduce average incremental cost (AIC) pricing and present examples to help understand its advantages. In non-convex markets, AIC pricing is the rough equivalent to marginal cost pricing in convex markets. We present a qualitative comparison of current ISO pricing methods and the AIC approach. We argue that AIC better … Read more

    One-Pass Average Incremental Cost Pricing

  • Richard O'Neill
  • Yonghong Chen
    • Categories (Mixed) Integer Linear Programming Tags ,

    Since the inception of ISOs, Locational Marginal Prices (LMPs) alone were not incentive compatible because an auction winner who offered its avoidable costs could lose money at the LMP. ISOs used make-whole payments to ensure market participants did not lose money. Make-whole payments were not public creating transparency issues. Over time, the ISOs employed methods … Read more

    A Short Proof of Tight Bounds on the Smallest Support Size of Integer Solutions to Linear Equations

  • Yatharth Dubey
  • Siyue Liu
    • Categories Integer Programming, Other Topics Tags ,

    \(\) In this note, we study the size of the support of solutions to linear Diophantine equations $Ax=b, ~x\in\Z^n$ where $A\in\Z^{m\times n}, b\in\Z^n$. We give an asymptotically tight upper bound on the smallest support size, parameterized by $\|A\|_\infty$ and $m$, and taken as a worst case over all $b$ such that the above system has … Read more

    Cutting planes from the simplex tableau for quadratically constrained optimization problems

  • Mustafa Vora
  • Ashutosh Mahajan
    • Categories Cutting Plane Approaches, Global Optimization Tags , ,

    We describe a method to generate cutting planes for quadratically constrained optimization problems. The method uses information from the simplex tableau of a linear relaxation of the problem in combination with McCormick estimators. The method is guaranteed to cut off a basic feasible solution of the linear relaxation that violates the quadratic constraints in the … Read more

    Structured Pruning of Neural Networks for Constraints Learning

  • Matteo Cacciola
  • Andrea Lodi
  • Antonio Frangioni
    • Categories (Mixed) Integer Linear Programming, Combinatorial Optimization, Optimization in Data Science Tags , ,

    In recent years, the integration of Machine Learning (ML) models with Operation Research (OR) tools has gained popularity across diverse applications, including cancer treatment, algorithmic configuration, and chemical process optimization. In this domain, the combination of ML and OR often relies on representing the ML model output using Mixed Integer Programming (MIP) formulations. Numerous studies … Read more