(Mixed) Integer Linear Programming

Best-Response Dynamics for Large-Scale Integer Programming Games with Applications to Aquatic Invasive Species Prevention

  • HYUNWOO LEE
  • Robert Hildebrand
  • cai
  • esratoy
    • Categories (Mixed) Integer Linear Programming, Applications - OR and Management Sciences, Game Theory Tags , , , ,

    This paper presents a scalable algorithm for computing the best pure Nash equilibrium (PNE) in large-scale integer programming games (IPGs). While recent advances in IPG algorithms are extensive, existing methods are limited to a small number of players, typically đť‘› = 2, 3. Motivated by a county-level aquatic invasive species (AIS) prevention problem involving 84 … Read more

    A Dantzig-Wolfe Single-Level Reformulation for Mixed-Integer Linear Bilevel Optimization: Exact and Heuristic Approaches

  • Henri Lefebvre
  • Martin Schmidt
    • Categories (Mixed) Integer Linear Programming, Bilevel Optimization, Branch and Cut Algorithms Tags , , , ,

    Bilevel optimization problems arise in numerous real-world applications. While single-level reformulations are a common strategy for solving convex bilevel problems, such approaches usually fail when the follower’s problem includes integer variables. In this paper, we present the first single-level reformulation for mixed-integer linear bilevel optimization, which does not rely on the follower’s value function. Our … Read more

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

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

    Generalized Nash equilibrium problems with mixed-integer variables form an important class of games in which each player solves a mixed-integer optimization problem with respect to her own variables and the strategy space of each player depends on the strategies chosen by the rival players. In this work, we introduce a branch-and-cut algorithm to compute exact … 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

    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

    Optimization over Trained (and Sparse) Neural Networks: A Surrogate within a Surrogate

  • Hung Pham
  • Zhiyi Ren
  • Jiatai Tong
  • Thiago Serra
    • Categories (Mixed) Integer Linear Programming, Integer Programming

    We can approximate a constraint or an objective function that is uncertain or nonlinear with a neural network that we embed in the optimization model. This approach, which is known as constraint learning, faces the challenge that optimization models with neural network surrogates are harder to solve. Such difficulties have motivated studies on model reformulation, … Read more

    Data-driven robust menu planning for food services: Reducing food waste by using leftovers

  • Marloes Remijnse
  • Marjolein Buisman
  • Ahmadreza Marandi
  • S.U.K Rohmer
  • Tom Van Woensel
    • Categories (Mixed) Integer Linear Programming, Applications - OR and Management Sciences, Robust Optimization Tags , , , ,

    With food waste levels of about 30%, mostly caused by overproduction, reducing food waste poses an important challenge in the food service sector. As food is prepared in advance rather than on demand, there is a significant risk that meals or meal components remain uneaten. Flexible meal planning can promote the reuse of these leftovers … Read more

    Global Optimization of Gas Transportation and Storage: Convex Hull Characterizations and Relaxations

  • Bahar Okumusoglu
  • Burak Kocuk
    • Categories (Mixed) Integer Linear Programming, Energy, Global Optimization Tags , , ,

    Gas transportation and storage has become one of the most relevant and important optimization problems in energy systems. This problem inherently includes highly nonlinear and nonconvex aspects due to gas physics, and discrete aspects due to the control decisions of active network elements. Obtaining even locally optimal solutions for this problem presents significant mathematical and … Read more

    An interactive optimization framework for incorporating a broader range of human feedback into stochastic multi-objective mixed integer linear programs

  • Damsara Jayarathne
  • Jennifer Pazour
  • John E. Mitchell
    • Categories (Mixed) Integer Linear Programming, Multi-Criteria Optimization, Stochastic Programming Tags , , , ,

    Interactive optimization leverages the strengths of optimization frameworks alongside the expertise of human users. Prior research in this area tends to either ask human users for the same type of information, or when varying information is requested, users must manually modify the optimization model directly. These limitations restrict the incorporation of wider human knowledge into … Read more