(Mixed) Integer Linear Programming

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

    An Algorithm-Independent Measure of Progress for Linear Constraint Propagation

  • Ambros Gleixner
  • Sebastian Pokutta
  • Boro Sofranac
    • Categories (Mixed) Integer Linear Programming Tags ,

    Propagation of linear constraints has become a crucial sub-routine in modern Mixed-Integer Programming (MIP) solvers. In practice, iterative algorithms with tolerance-based stopping criteria are used to avoid problems with slow or infinite convergence. However, these heuristic stopping criteria can pose difficulties for fairly comparing the efficiency of different implementations of iterative propagation algorithms in a … Read more

    Optimal Eco-Routing for Hybrid Vehicles with Mechanistic/Data-Driven Powertrain Model Embedded

  • Adrian Caspari
  • Alexander Mitsos
  • Steffen Fahr
    • Categories (Mixed) Integer Linear Programming, Applications - Science and Engineering, Transportation Tags , , , , , ,

    Hybrid Electric Vehicles (HEVs) are regarded as an important (transition) element of sustainable transportation. Exploiting the full potential of HEVs requires (i) a suitable route selection and (ii) suitable power management, i.e., deciding on the split between combustion engine and electric motor usage as well as the mode of the electric motor, i.e., driving or … Read more

    Markov Chain Sampling of Hidden Relay States for Economic Dispatch with Cascading Failures

  • John Birge
  • Arnab Sur
    • Categories (Mixed) Integer Linear Programming, Energy, Stochastic Programming Tags , , , , ,

    Independent system operators (ISO) of electric power networks aim to dispatch electricity economically while maintaining system reliability. NERC (North America Electric Reliability Council) requires the transmission network to be (N-1)-secure, i.e., to have sufficient supply to satisfy demand in the event of the failure of any single resource in the network. Such a policy is … Read more

    On the Polyhedrality of the Chvatal-Gomory Closure

  • Haoran Zhu
    • Categories (Mixed) Integer Linear Programming, Cutting Plane Approaches, Polyhedra Tags , ,

    In this paper, we provide an equivalent condition for the Chvatal-Gomory (CG) closure of a closed convex set to be finitely-generated. Using this result, we are able to prove that, for any closed convex set that can be written as the Minkowski sum of a compact convex set and a closed convex cone, its CG … Read more