Month: November 2020

Face Dimensions of General-Purpose Cutting Planes for Mixed-Integer Linear Programs

  • Matthias Walter
    • Categories (Mixed) Integer Linear Programming, Cutting Plane Approaches, Polyhedra Tags , ,

    Cutting planes are a key ingredient to successfully solve mixed-integer linear programs. For specific problems, their strength is often theoretically assessed by showing that they are facet-defining for the corresponding mixed-integer hull. In this paper we experimentally investigate the dimensions of faces induced by general-purpose cutting planes generated by a state-of-the-art solver. Therefore, we relate … Read more

    Complexity, Exactness, and Rationality in Polynomial Optimization

  • Daniel Bienstock
  • Alberto Del Pia
  • Robert Hildebrand
    • Categories Global Optimization Theory, Nonlinear Optimization Tags , ,

    We study representation of solutions and certificates to quadratic and cubic optimization problems. Specifically, we focus on minimizing a cubic function over a polyhedron and also minimizing a linear function over quadratic constraints. We show when there exist rational feasible solutions (and if we can detect them) and when we can prove feasibility of sublevel … 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

    Mixed-Integer Reformulations of Resource-Constrained Two-Stage Assignment Problems

  • Lena Hupp
  • Frauke Liers
  • Manu Kapolke
  • Alexander Martin
  • Robert Weismantel
    • Categories (Mixed) Integer Linear Programming, Airline Optimization, Combinatorial Optimization Tags , , ,

    The running time for solving a mixed-integer linear optimization problem (MIP) strongly depends on the number of its integral variables. Bader et al. [Math. Progr. 169 (2018) 565–584] equivalently reformulate an integer program into an MIP that contains a reduced number of integrality constraints, when compared to the original model. Generalizing the concept of totally … Read more

    Exact Methods for the Traveling Salesman Problem with Multiple Drones

  • Sara Cavani
  • Manuel Iori
  • Roberto Roberti
    • Categories Transportation

    Drone delivery is drawing increasing attention in last-mile delivery. Effective solution methods to solve decision-making problems arising in drone delivery allow to run and assess drone delivery systems. In this paper, we focus on delivery systems with a single traditional vehicle and multiple drones working in tandem to fulfill customer requests. We address the Traveling … Read more

    Constrained stochastic blackbox optimization using a progressive barrier and probabilistic estimates

  • Kwassi Joseph Dzahini
  • Michael Kokkolaras
  • Sébastien Le Digabel
    • Categories Constrained Nonlinear Optimization, Nonlinear Optimization, Stochastic Approaches Tags , , ,

    This work introduces the StoMADS-PB algorithm for constrained stochastic blackbox optimization, which is an extension of the mesh adaptive direct-search (MADS) method originally developed for deterministic blackbox optimization under general constraints. The values of the objective and constraint functions are provided by a noisy blackbox, i.e., they can only be computed with random noise whose … Read more

    Exterior-point Optimization for Nonconvex Learning

  • Shuvomoy Das Gupta
  • Bartolomeo Stellato
  • Bart Paul Gerard Van Parys
    • Categories Constrained Nonlinear Optimization, Nonsmooth Optimization, Statistics Tags , , ,

    In this paper we present the nonconvex exterior-point optimization solver (NExOS)—a novel first-order algorithm tailored to constrained nonconvex learning problems. We consider the problem of minimizing a convex function over nonconvex constraints, where the projection onto the constraint set is single-valued around local minima. A wide range of nonconvex learning problems have this structure including … Read more

    A Reformulation-Linearization Technique for Optimization over Simplices

  • Aras Selvi
  • Dick den Hertog
  • Wolfram Wiesemann
    • Categories Constrained Nonlinear Optimization, Global Optimization, Global Optimization Theory Tags , ,

    We study non-convex optimization problems over simplices. We show that for a large class of objective functions, the convex approximation obtained from the Reformulation-Linearization Technique (RLT) admits optimal solutions that exhibit a sparsity pattern. This characteristic of the optimal solutions allows us to conclude that (i) a linear matrix inequality constraint, which is often added … Read more

    An Exact Method for Assortment Optimization under the Nested Logit Model

  • Laurent Alfandari
  • Ivana Ljubić
  • Alborz Hassanzadeh
    • Categories Applications - OR and Management Sciences Tags , , , ,

    We study the problem of finding an optimal assortment of products maximizing the expected revenue, in which customer preferences are modeled using a Nested Logit choice model. This problem is known to be polynomially solvable in a specific case and NP-hard otherwise, with only approximation algorithms existing in the literature. For the NP-hard cases, we … Read more

    A modern POPMUSIC matheuristic for the capacitated vehicle routing problem

  • Eduardo Queiroga
  • Ruslan Sadykov
  • Eduardo Uchoa
    • Categories Applications - OR and Management Sciences, Combinatorial Optimization, Meta Heuristics

    This work proposes a partial optimization metaheuristic under special intensification conditions (POPMUSIC) for the classical capacitated vehicle routing problem (CVRP). The proposed approach uses a branch-cut-and-price algorithm as a powerful heuristic to solve subproblems whose dimensions are typically between 25 and 200 customers. The whole algorithm can be seen as the application of local search … Read more