(Mixed) Integer Linear 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

    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

    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

    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

    Optimization-based Learning for Dynamic Load Planning in Trucking Service Networks

  • Ritesh Ojha
  • Reem Khir
  • Alan L. Erera
    • Categories (Mixed) Integer Linear Programming, Production and Logistics, Transportation Tags , ,

    CitationOjha, R., Chen, W., Zhang, H., Khir, R., Erera, A. & Van Hentenryck, P. (2023). Optimization-based Learning for Dynamic Load Planning in Trucking Service Networks.ArticleDownload View PDF

    Shattering Inequalities for Learning Optimal Decision Trees

  • Justin Boutilier
  • Carla Michini
  • Zachary Zhou
    • Categories (Mixed) Integer Linear Programming, Optimization in Data Science

    Recently, mixed-integer programming (MIP) techniques have been applied to learn optimal decision trees. Empirical research has shown that optimal trees typically have better out-of-sample performance than heuristic approaches such as CART. However, the underlying MIP formulations often suffer from weak linear programming (LP) relaxations. Many existing MIP approaches employ big-M constraints to ensure observations are … Read more

    The set partitioning problem in a quantum context

  • Rafael Farias Cacao
  • Lucas Ramos Cardoso Tinoco Cortez
  • Jackson Forner
  • Hamidreza Validi
  • Ismael de Farias
  • Illya V. Hicks
    • Categories (Mixed) Integer Linear Programming, Combinatorial Optimization, Integer Programming

    The set partitioning problem and its decision variant (i.e., the exact cover problem) are combinatorial optimization problems that were historically crucial in the quantum optimization community. This problem is also employed in the main problem of the branch-and-price approach in many real-world optimization problems, including, but not limited to, redistricting and scheduling. Motivated by recent … Read more

    Mixed-Integer Programming for a Class of Robust Submodular Maximization Problems

  • Hsin-Yi Huang
  • Hao-Hsiang Wu
  • Simge Küçükyavuz
    • Categories (Mixed) Integer Linear Programming, Robust Optimization, Stochastic Programming

    We consider robust submodular maximization problems (RSMs), where given a set of \(m\) monotone submodular objective functions, the robustness is with respect to the worst-case (scaled) objective function. The model we consider generalizes two variants of robust submodular maximization problems in the literature, depending on the choice of the scaling vector. On one hand, by using … Read more