variable fixing

The Terminator: An Integration of Inner and Outer Approximations for Solving Regular and Distributionally Robust Chance Constrained Programs via Variable Fixing

  • Nan Jiang
  • Weijun Xie
    • Categories Stochastic Programming Tags , ,

    We present a novel approach aimed at enhancing the efficacy of solving both regular and distributionally robust chance constrained programs using an empirical reference distribution. In general, these programs can be reformulated as mixed-integer programs (MIPs) by introducing binary variables for each scenario, indicating whether a scenario should be satisfied. While existing methods have predominantly … Read more

    Decremental State-Space Relaxations for the Basic Traveling Salesman Problem with a Drone

  • Marcos Blufstein
  • Gonzalo Lera-Romero
  • Francisco J. Soulignac
    • Categories Dynamic Programming, Transportation Tags , , , , ,

    Truck-and-drone routing problems have become an important topic of research in the last decade due to their applications for last-mile deliveries. Despite the large number of publications in this area, the most efficient exact algorithms designed thus far struggle to solve the benchmark instances with 39 or more customers. This fact is true even for … Read more

    Feasible rounding approaches and diving strategies in branch-and-bound methods for mixed-integer optimization

  • Christoph Neumann
  • Stefan Schwarze
  • Oliver Stein
  • Benjamin Müller
    • Categories (Mixed) Integer Linear Programming, (Mixed) Integer Nonlinear Programming Tags , , , , ,

    In this paper, we study the behavior of feasible rounding approaches for mixed-integer linear and nonlinear optimization problems (MILP and MINLP, respectively) when integrated into tree search of branch-and-bound. Our research addresses two important aspects. First, we develop insights into how an (enlarged) inner parallel set, which is the main component for feasible rounding approaches, … Read more

    Orbitopal Fixing

  • Volker Kaibel
  • Marc E. Pfetsch
  • Peinhardt Matthias
    • Categories 0-1 Programming, Branch and Cut Algorithms, Polyhedra Tags , ,

    The topic of this paper are integer programming models in which a subset of 0/1-variables encode a partitioning of a set of objects into disjoint subsets. Such models can be surprisingly hard to solve by branch-and-cut algorithms if the permutation of the subsets of the partition is irrelevant. This kind of symmetry unnecessarily blows up … Read more