(Mixed) Integer Linear Programming

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

    A Joint Demand and Supply Management Approach to Large Scale Urban Evacuation Planning: Evacuate or Shelter-in-Place, Staging and Dynamic Resource Allocation

  • Vedat Bayram
  • Hande Yaman
    • Categories (Mixed) Integer Linear Programming, Network Optimization, Transportation

    Urban evacuation management is challenging to implement as it requires planning and coordination over a large geographical area. To address these challenges and to bolster evacuation planning and management, joint supply and demand management strategies should be considered. In this study, we explore and jointly optimize evacuate or shelter-in-place, dynamic resource allocation, and staging decisions … Read more

    High-Rank Matrix Completion by Integer Programming

  • Jeff Linderoth
  • James R. Luedtke
  • Daniel Pimentel-Alarcon
  • Akhilesh Soni
    • Categories (Mixed) Integer Linear Programming, Applications - OR and Management Sciences

    In the High-Rank Matrix Completion (HRMC) problem, we are given a collection of n data points, arranged into columns of a matrix X, and each of the data points is observed only on a subset of its coordinates. The data points are assumed to be concentrated near a union of low-dimensional subspaces. The goal of … Read more

    Solving the Home Service Assignment, Routing, and Appointment Scheduling (H-SARA) problem with Uncertainties

  • Syu-Ning Johnn
  • Yiran Zhu
  • Andrés Miniguano-Trujillo
  • Akshay Gupte
    • Categories (Mixed) Integer Linear Programming, Stochastic Programming, Transportation Tags , , , ,

    The Home Service Assignment, Routing, and Appointment scheduling (H-SARA) problem integrates the strategical fleet-sizing, tactical assignment, operational vehicle routing and scheduling subproblems at different decision levels, with a single period planning horizon and uncertainty (stochasticity) from the service duration, travel time, and customer cancellation rate. We propose a two-stage stochastic mixed-integer linear programming model for … Read more

    Integrated Vehicle Routing and Service Scheduling under Time and Cancellation Uncertainties with Application in Non-Emergency Medical Transportation

  • Siqian Shen
  • Huizhu Wang
  • Xian Yu
    • Categories (Mixed) Integer Linear Programming, Applications - OR and Management Sciences

    In this paper, we consider an integrated vehicle routing and service scheduling problem for serving customers in distributed locations who need pick-up, drop-off or delivery services. We take into account the random trip time, non-negligible service time and possible customer cancellations, under which an ill-designed schedule may lead to undesirable vehicle idleness and customer waiting. … Read more

    Designing an optimal sequence of non-pharmaceutical interventions for controlling COVID-19

  • Laurent Alfandari
  • Debajyoti Biswas
    • Categories (Mixed) Integer Linear Programming, Applications - OR and Management Sciences, Biomedical Applications

    The COVID-19 pandemic has had an unprecedented impact on global health and the economy since its inception in December, 2019 in Wuhan, China. Non-pharmaceutical interventions (NPI) like lockdowns and curfews have been deployed by affected countries for controlling the spread of infections. In this paper, we develop a Mixed Integer Non-Linear Programming (MINLP) epidemic model … Read more

    Exact Logit-Based Product Design

  • İrem Akçakuş
  • Velibor Mišić
    • Categories (Mixed) Integer Linear Programming, (Mixed) Integer Nonlinear Programming, Marketing

    The share-of-choice product design (SOCPD) problem is to find the product, as defined by its attributes, that maximizes market share arising from a collection of customer types or segments. When customers follow a logit model of choice, the market share is given by a weighted sum of logistic probabilities, leading to the logit-based share-of-choice product … Read more

    The Graphical Traveling Salesperson Problem has no Integer Programming Formulation in the Original Space

  • Matthias Walter
    • Categories (Mixed) Integer Linear Programming, Graphs and Matroids

    The Graphical Traveling Salesperson Problem (GTSP) is the problem of assigning, for a given weighted graph, a nonnegative number x_e to each edge e such that the induced multi-subgraph is of minimum weight among those that are spanning, connected and Eulerian. Naturally, known mixed-integer programming formulations use integer variables x_e in addition to others. Denis … Read more

    Cardinality Minimization, Constraints, and Regularization: A Survey

  • Daniel Bienstock
  • Andrea Lodi
  • Andreas M. Tillmann
  • Alexandra Schwartz
    • Categories (Mixed) Integer Linear Programming, (Mixed) Integer Nonlinear Programming, Constrained Nonlinear Optimization Tags , , , , , , ,

    We survey optimization problems that involve the cardinality of variable vectors in constraints or the objective function. We provide a unified viewpoint on the general problem classes and models, and give concrete examples from diverse application fields such as signal and image processing, portfolio selection, or machine learning. The paper discusses general-purpose modeling techniques and … Read more

    New Valid Inequalities and Formulation for the Static Chance-constrained Lot-Sizing Problem

  • Chuanhou Gao
  • James R. Luedtke
  • Zeyang Zhang
    • Categories (Mixed) Integer Linear Programming, Stochastic Programming Tags , ,

    We study the static chance-constrained lot sizing problem, in which production decisions over a planning horizon are made before knowing random future demands, and the backlog and inventory variables are then determined by the demand realizations. The chance constraint imposes a service level constraint requiring that the probability that any backlogging is required should be … Read more