Integer Programming

A relax-fix-and-exclude algorithm for an MINLP problem with multilinear interpolations

  • Bruno Machado Pacheco
  • Laio Seman
    • Categories (Mixed) Integer Nonlinear Programming, Chemical Engineering, Global Optimization Applications Tags , ,

    This paper introduces a novel algorithm for Mixed-Integer Nonlinear Programming (MINLP) problems with multilinear interpolations of look-up tables. These problems arise when objectives or constraints contain black-box functions only known at a finite set of evaluations on a predefined grid. We derive a piecewise-linear relaxation for the multilinear interpolants, which require an MINLP formulation. Supported … Read more

    Two-way Cutting-plane Algorithm for Best Subset Selection Considering Multicollinearity

  • Yuichi Takano
    • Categories Global Optimization, Integer Programming, Optimization in Data Science Tags , , , ,

    When linear dependence exists between some explanatory variables in a regression model, the estimates of regression coefficients become unstable, thereby making the interpretation of the estimation results unreliable. To eliminate such multicollinearity, we propose a high-performance method for selecting the best subset of explanatory variables for linear and logistic regression models. Specifically, we first derive … Read more

    Branch-and-Cut for Mixed-Integer Nash Equilibrium Problems

  • Alois Duguet
  • Tobias Harks
  • Martin Schmidt
  • Julian Schwarz
    • Categories (Mixed) Integer Linear Programming, Bilevel Optimization, Game Theory Tags , , , ,

    We consider Nash equilibrium problems with mixed-integer variables in which each player solves a mixed-integer optimization problem parameterized in the rivals’ strategies. We distinguish between standard Nash equilibrium problems (NEP), where the parameterization acts only on the players’ cost functions and generalized Nash equilibrium problems (GNEPs), where, additionally, the strategy spaces of the players may … Read more

    On Multidimensonal Disjunctive Inequalities for Chance-Constrained Stochastic Problems with Finite Support

  • Diego Cattaruzza
  • Martine Labbé
  • Matteo Petris
  • Marius Roland
  • Martin Schmidt
    • Categories (Mixed) Integer Linear Programming, Stochastic Programming Tags , , , ,

    We consider mixed-integer linear chance-constrained problems for which the random vector that parameterizes the feasible region has finite support. Our key objective is to improve branch-and-bound or -cut approaches by introducing new types of valid inequalities that improve the dual bounds and, by this, the overall performance of such methods. We introduce so-called primal-dual as … Read more

    Mixed-Feature Logistic Regression Robust to Distribution Shifts

  • Qingshi Sun
  • Nathan Justin
  • Andrés Gómez
  • Phebe Vayanos
    • Categories Applications - OR and Management Sciences, Integer Programming, Robust Optimization Tags , , ,

    Logistic regression models are widely used in the social and behavioral sciences and in high-stakes domains, due to their simplicity and interpretability properties. At the same time, such domains are permeated by distribution shifts, where the distribution generating the data changes between training and deployment. In this paper, we study a distributionally robust logistic regression … Read more

    Inverse Optimization via Learning Feasible Regions

  • Ke Ren
  • Peyman Mohajerin Esfahani
  • Angelos Georghiou
    • Categories (Mixed) Integer Linear Programming, Nonsmooth Optimization, Robust Optimization Tags , , ,

    We study inverse optimization (IO), where the goal is to use a parametric optimization program as the hypothesis class to infer relationships between input-decision pairs. Most of the literature focuses on learning only the objective function, as learning the constraint function (i.e., feasible regions) leads to nonconvex training programs. Motivated by this, we focus on … Read more

    A surplus-maximizing two-sided multi-period non-convex ISO auction market

  • Richard O'Neill
  • Yonghong Chen
    • Categories (Mixed) Integer Linear Programming, Applications - OR and Management Sciences, Other Topics Tags , , ,

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

    Responsible Machine Learning via Mixed-Integer Optimization

  • Nathan Justin
  • Qingshi Sun
  • Andrés Gómez
  • Phebe Vayanos
    • Categories Applications - OR and Management Sciences, Integer Programming, Optimization in Data Science Tags , , , , , ,

    In the last few decades, Machine Learning (ML) has achieved significant success across domains ranging from healthcare, sustainability, and the social sciences, to criminal justice and finance. But its deployment in increasingly sophisticated, critical, and sensitive areas affecting individuals, the groups they belong to, and society as a whole raises critical concerns around fairness, transparency … Read more

    Alternating Methods for Large-Scale AC Optimal Power Flow with Unit Commitment

  • Matthew Brun
  • Thomas Lee
  • Dirk Lauinger
  • Xin Chen
  • Xu Andy Sun
    • Categories (Mixed) Integer Nonlinear Programming, Energy Tags , , ,

    Security-constrained unit commitment with alternating current optimal power flow (SCUC-ACOPF) is a central problem in power grid operations that optimizes commitment and dispatch of generators under a physically accurate power transmission model while encouraging robustness against component failures.  SCUC-ACOPF requires solving large-scale problems that involve multiple time periods and networks with thousands of buses within … Read more

    A Graphical Global Optimization Framework for Parameter Estimation of Statistical Models with Nonconvex Regularization Functions

  • Danial Davarnia
    • Categories (Mixed) Integer Nonlinear Programming, Branch and Cut Algorithms, Global Optimization Theory Tags , , , ,

    Optimization problems with norm-bounding constraints appear in various applications, from portfolio optimization to machine learning, feature selection, and beyond. A widely used variant of these problems relaxes the norm-bounding constraint through Lagrangian relaxation and moves it to the objective function as a form of penalty or regularization term. A challenging class of these models uses … Read more