Combinatorial Optimization

Planar Maximum Coverage Location Problem with Partial Coverage, Continuous Spatial Demand, and Adjustable Quality of Service

  • Manish Bansal
  • Parshin Shojaee
    • Categories Combinatorial Optimization

    We consider a generalization of the classical planar maximum coverage location problem (PMCLP) in which partial coverage is allowed, facilities have adjustable quality of service (QoS) or service range, and demand zones and service zone of each facility are represented by two-dimensional spatial objects such as rectangles, circles, polygons, etc. We denote this generalization by … Read more

    Polyhedral Analysis of Symmetric Multilinear Polynomials over Box Constraints

  • Warren Adams
  • Akshay Gupte
  • Yibo Xu
    • Categories (Mixed) Integer Nonlinear Programming, Global Optimization Theory, Polyhedra Tags , , , ,

    It is well-known that the convex and concave envelope of a multilinear polynomial over a box are polyhedral functions. Exponential-sized extended and projected formulations for these envelopes are also known. We consider the convexification question for multilinear polynomials that are symmetric with respect to permutations of variables. Such a permutation-invariant structure naturally implies a quadratic-sized … Read more

    On Recognizing Staircase Compatibility

  • Andreas Bärmann
  • Maximilian Merkert
  • Patrick Gemander
  • Alexander Martin
    • Categories 0-1 Programming, Graphs and Matroids, Scheduling Tags , , ,

    For the problem to find an m-clique in an m-partite graph, staircase compatibility has recently been introduced as a polynomial-time solvable special case. It is a property of a graph together with an m-partition of the vertex set and total orders on each subset of the partition. In optimization problems involving m-cliques in m-partite graphs … Read more

    A Distributionally-Robust Service Center Location Problem with Decision Dependent Demand Induced from a Maximum Attraction Principle

  • Fengqiao Luo
    • Categories Applications - OR and Management Sciences, Combinatorial Optimization, Integer Programming Tags , , , ,

    We establish and analyze a service center location model with a simple but novel decision-dependent demand induced from a maximum attrac- tion principle. The model formulations are investigated in the distributionally- robust optimization framework. A statistical model that is based on the max- imum attraction principle for estimating customer demand and utility gain from service … Read more

    A Polyhedral Study for the Cubic Formulation of the Unconstrained Traveling Tournament Problem

  • Marije Siemann
  • Matthias Walter
    • Categories Applications - OR and Management Sciences, Polyhedra Tags ,

    We consider the unconstrained traveling tournament problem, a sports timetabling problem that minimizes traveling of teams. Since its introduction about 20 years ago, most research was devoted to modeling and reformulation approaches. In this paper we carry out a polyhedral study for the cubic integer programming formulation by establishing the dimension of the integer hull … Read more

    Implications, conflicts, and reductions for Steiner trees

  • Thorsten Koch
  • Daniel Rehfeldt
    • Categories Combinatorial Optimization Tags

    The Steiner tree problem in graphs (SPG) is one of the most studied problems in combinatorial optimization. In the last 10 years, there have been significant advances concerning approximation and complexity of the SPG. However, the state of the art in (practical) exact solution of the SPG has remained largely unchallenged for almost 20 years. … 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

    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

    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

    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