Other Topics

An Exact Projection-Based Algorithm for Bilevel Mixed-Integer Problems with Nonlinearities

  • Maximilian Merkert
  • Galina Orlinskaya
  • Dieter Weninger
    • Categories (Mixed) Integer Nonlinear Programming, Game Theory, Global Optimization Tags , , , ,

    We propose an exact global solution method for bilevel mixed-integer optimization problems with lower-level integer variables and including nonlinear terms such as, \eg, products of upper-level and lower-level variables. Problems of this type are extremely challenging as a single-level reformulation suitable for off-the-shelf solvers is not available in general. In order to solve these problems … Read more

    A dynamic programming approach to segmented isotonic regression

  • Victor Bucarey
  • Martine LabbĂ©
  • Juan M. Morales
  • Salvador Pineda
    • Categories Data-Mining, Dynamic Programming, Energy Tags , , , , ,

    This paper proposes a polynomial-time algorithm to construct the monotone stepwise curve that minimizes the sum of squared errors with respect to a given cloud of data points. The fitted curve is also constrained on the maximum number of steps it can be composed of and on the minimum step length. Our algorithm relies on … Read more

    The Moment-SOS hierarchy and the Christoffel-Darboux kernel

  • Jean-Bernard Lasserre
    • Categories Global Optimization Theory, Other Topics

    We consider the global minimization of a polynomial on a compact set B. We show that each step of the Moment-SOS hierarchy has a nice and simple interpretation that complements the usual one. Namely, it computes coefficients of a polynomial in an orthonormal basis of $L^2(B,\mu)$ where $\mu$ is an arbitrary reference measure whose support … Read more

    Cost-Sharing Mechanism Design for Ride-Sharing

  • Maged M. Dessouky
  • Nelson A. Uhan
  • Shichun Hu
  • Phebe Vayanos
    • Categories Game Theory, Transportation

    In this paper, we focus on the cost-sharing problem for ride-sharing that determines how to allocate the total ride cost between the driver and the passengers. We identify the properties that a desirable cost-sharing mechanism should have and develop a general framework which can be used to create specific cost-sharing mechanisms. We propose specific mechanisms … Read more

    The Price of Anarchy in Series-Parallel Network Congestion Games

  • Bainian Hao
  • Carla Michini
    • Categories Combinatorial Optimization, Game Theory Tags , ,

    We study the inefficiency of pure Nash equilibria in symmetric network congestion games defined over series-parallel networks with affine edge delays. For arbitrary networks, Correa (2019) proved a tight upper bound of 5/2 on the PoA. On the other hand, for extension-parallel networks, a subclass of series-parallel networks, Fotakis (2010) proved that the PoA is … Read more

    An equivalent mathematical program for games with random constraints

  • Monika Arora
  • Abdel Lisser
  • Vikas Vikram Singh
    • Categories Game Theory, Stochastic Programming Tags , , ,

    This paper shows that there exists a Nash equilibrium of an n-player chance-constrained game for elliptically symmetric distributions. For a certain class of payoff functions, we suitably construct an equivalent mathematical program whose global maximizer is a Nash equilibrium. Article Download View An equivalent mathematical program for games with random constraints

    Valid Inequalities for Mixed Integer Bilevel Linear Optimization Problems

  • Ted K. Ralphs
  • Sahar Tahernejad
    • Categories Cutting Plane Approaches, Game Theory, Polyhedra Tags , ,

    Despite the success of branch-and-cut methods for solving mixed integer bilevel linear optimization problems (MIBLPs) in practice, there have remained some gaps in the theory surrounding these methods. In this paper, we take a first step towards laying out a theory of valid inequalities and cutting-plane methods for MIBLPs that parallels the existing theory for … Read more

    Discrete Multi-Module Capacitated Lot-Sizing Problems with Multiple Items

  • Manish Bansal
  • Kartik Kulkarni
    • Categories 0-1 Programming, Dynamic Programming, Production and Logistics Tags , , , ,

    We study single-item discrete multi-module capacitated lot-sizing problems where the amount produced in each time period is equal to the summation of binary multiples of the capacities of n available different modules (or machines). For fixed n≥2, we develop fixed-parameter tractable (polynomial) exact algorithms that generalize the algorithms of van Vyve (2007) for n=1. We … Read more

    An approximation algorithm for multi-objective optimization problems using a box-coverage

  • Gabriele Eichfelder
  • Leo Warnow
    • Categories Global Optimization, Multi-Criteria Optimization Tags , , , ,

    For a continuous multi-objective optimization problem, it is usually not a practical approach to compute all its nondominated points because there are infinitely many of them. For this reason, a typical approach is to compute an approximation of the nondominated set. A common technique for this approach is to generate a polyhedron which contains the … Read more

    On Distributionally Robust Multistage Convex Optimization: New Algorithms and Complexity Analysis

  • Xu Andy Sun
  • Shixuan Zhang
    • Categories Dynamic Programming, Robust Optimization, Stochastic Programming

    This paper presents a novel algorithmic study and complexity analysis of distributionally robust multistage convex optimization (DR-MCO). We propose a new class of algorithms for solving DR-MCO, namely a sequential dual dynamic programming (Seq-DDP) algorithm and its nonsequential version (NDDP). The new algorithms generalize and strengthen existing DDP-type algorithms by introducing the technique of regularization … Read more