Parameterized Complexity

The Dantzig-Fulkerson-Johnson TSP formulation is easy to solve for few subtour constraints

  • Eleonora Vercesi
  • Austin Buchanan
    • Categories Combinatorial Optimization, Integer Programming, Network Optimization Tags , ,

    The most successful approaches for the TSP use the integer programming model proposed in 1954 by Dantzig, Fulkerson, and Johnson (DFJ). Although this model has exponentially many subtour elimination constraints (SECs), it has been observed that relatively few of them are needed to prove optimality in practice. This leads us to wonder: What is the … Read more

    Recursive McCormick Linearization of Multilinear Programs

  • Arvind U. Raghunathan
  • Carlos Cardonha
  • David Bergman
  • Carlos Nohra
    • Categories (Mixed) Integer Nonlinear Programming, Global Optimization Theory Tags , , ,

    Linear programming (LP) relaxations are widely employed in exact solution methods for multilinear programs (MLP). One example is the family of Recursive McCormick Linearization (RML) strategies, where bilinear products are substituted for artificial variables, which deliver a relaxation of the original problem when introduced together with concave and convex envelopes. In this article, we introduce … Read more