On Piecewise Linear Approximations of Bilinear Terms: Structural Comparison of Univariate and Bivariate Mixed-Integer Programming Formulations

  • Lukas Hager
  • Robert Burlacu
  • Andreas Bärmann
  • Thomas Kleinert
    • Categories (Mixed) Integer Linear Programming, Global Optimization Theory, Quadratic Programming Tags , , , ,

    Bilinear terms naturally appear in many optimization problems. Their inherent nonconvexity typically makes them challenging to solve. One approach to tackle this difficulty is to use bivariate piecewise linear approximations for each variable product, which can be represented via mixed-integer linear programming (MIP) formulations. Alternatively, one can reformulate the variable products as a sum of … Read more

    Linear Control Policies for Online Vehicle Relocation in Shared Mobility Systems

  • Yuichi Takano
  • Yasuhiro Yoshida
    • Categories Transportation

    In one-way station-based shared mobility systems, where system users share vehicles for making trips between vehicle stations, the accumulation of one-way trips inevitably causes vehicle imbalances between stations. To correct these imbalances, we focus on the effective use of linear control policies for calculating online vehicle relocations from a history of user trips. Our scenario-based … Read more

    Solving Graph Partitioning on Sparse Graphs: Cuts, Projections, and Extended Formulations

  • Demetrios Papazaharias
  • Jose L. Walteros
    • Categories Combinatorial Optimization, Network Optimization Tags , , , ,

    This paper explores new solution approaches for the graph partitioning problem. While the classic formulations for graph partitioning are compact, they either suffer from a poor relaxation, symmetry, or contain a cubic number of constraints regardless of the graph density. These shortcomings often result in poor branch-and-bound performance. We approach this problem from perspective of … Read more

    An abstract convergence framework with application to inertial inexact forward-backward methods

  • Silvia Bonettini
  • Peter Ochs
  • Marco Prato
  • Simone Rebegoldi
    • Categories Nonlinear Optimization, Nonsmooth Optimization Tags , , ,

    In this paper we introduce a novel abstract descent scheme suited for the minimization of proper and lower semicontinuous functions. The proposed abstract scheme generalizes a set of properties that are crucial for the convergence of several first-order methods designed for nonsmooth nonconvex optimization problems. Such properties guarantee the convergence of the full sequence of … Read more

    QCQP with Extra Constant Modulus Constraints: Theory and Applications on QoS Constrained Hybrid Beamforming for mmWave MU-MIMO

  • Xin He
    • Categories Constrained Nonlinear Optimization, Quadratic Programming, Telecommunications Tags , , , , , , , ,

    The constant modulus constraint is widely used in analog beamforming, hybrid beamforming, intelligent reflecting surface design, and radar waveform design. The quadratically constrained quadratic programming (QCQP) problem is also widely used in signal processing. However, the QCQP with extra constant modulus constraints was not systematically studied in mathematic programming and signal processing. For example, the … Read more

    Linear relaxation based branch-and-bound for multi-objective integer programming with warm-starting

  • Nicolas Forget
  • Sune Lauth Gadegaard
  • Lars Relund Nielsen
    • Categories Multi-Criteria Optimization

    In this paper we propose a generic branch-and-bound algorithm for solving multi-objective integer linear programming problems. % In the recent literature, competitive frameworks has been proposed for bi-objective 0-1 problems, and many of these frameworks rely on the use of the linear relaxation to obtain lower bound sets. When increasing the number of objective functions, … Read more

    Increasing Driver Flexibility through Personalized Menus and Incentives in Ridesharing and Crowdsourced Delivery Platforms

  • Hannah Horner
  • John E. Mitchell
  • Jennifer Pazour
    • Categories Applications - OR and Management Sciences, Stochastic Programming, Transportation Tags , , , , , ,

    Allowing drivers to choose which requests to fulfill provides drivers with much-needed autonomy in ridesharing and crowdsourced delivery platforms. While stochastic, a driver’s acceptance of requests in their menu is influenced by the platform’s offered compensation. Therefore, in this work, we create and solve an optimization model to determine personalized menus and incentives to offer … Read more

    A Reformulation Technique to Solve Polynomial Optimization Problems with Separable Objective Functions of Bounded Integer Variables

  • Andrew C. Trapp
  • Pitchaya Wiratchotisatian
    • Categories (Mixed) Integer Nonlinear Programming, Global Optimization Theory, Nonlinear Optimization Tags , , ,

    Real-world problems are often nonconvex and involve integer variables, representing vexing challenges to be tackled using state-of-the-art solvers. We introduce a mathematical identity-based reformulation of a class of polynomial integer nonlinear optimization (PINLO) problems using a technique that linearizes polynomial functions of separable and bounded integer variables of any degree. We also introduce an alternative … Read more

    Decision Intelligence for Nationwide Ventilator Allocation

  • Jiajun Xu
  • Suvrajeet Sen
    • Categories Applications - OR and Management Sciences, Basic Sciences Applications, Optimization of Simulated Systems Tags , , , ,

    Many states in the U.S. have faced shortages of medical resources because of the surge in the number of patients suffering from COVID-19. As many projections indicate, the situation will be far worse in coming months. The upcoming challenge is not only due to the exponential growth in cases but also because of inherent uncertainty … Read more

    Multi-criteria Course Mode Selection and Classroom Assignment Under Sudden Space Scarcity

  • Mehran Navabi-Shirazi
  • Mohamed El Tonbari
  • Natashia Boland
  • Dima Nazzal
  • Lauren Steimle
    • Categories Applications - OR and Management Sciences, Multi-Criteria Optimization, Scheduling Tags , , , ,

    Problem Definition: While physical (or ‘social’) distancing is an important public health intervention during airborne pandemics, physical distancing dramatically reduces the effective capacity of classrooms. During the COVID-19 pandemic, this presented a unique problem to campus planners who hoped to deliver a meaningful amount of in-person instruction in a way that respected physical distancing. This … Read more