subtour elimination

Set System Approximation for Binary Integer Programs: Reformulations and Applications

  • Ningji Wei
    • Categories 0-1 Programming, Cutting Plane Approaches, Integer Programming Tags , , , ,

    Covering and elimination inequalities are central to combinatorial optimization, yet their role has largely been studied in problem-specific settings or via no-good cuts. This paper introduces a unified perspective that treats these inequalities as primitives for set system approximation in binary integer programs (BIPs). We show that arbitrary set systems admit tight inner and outer … Read more

    Traveling Salesman Problem Formulations with \log N$ Number of Binary Variables

  • Raul Conejeros
  • Thomas A. Pogiatzis
  • Vassilios S. Vassiliadis
    • Categories (Mixed) Integer Linear Programming, Transportation Tags , ,

    Abstract This paper presents a novel formulation for the Traveling Salesman Problem (TSP), utilizing a binary list data-structure allocating cities to its leaves to form sequentially the tour of the problem. The structure allows the elimination of subtours from the formulation and at the same time reducing the number of binary variables to ${\cal O}(N\log_{2}N)$. … Read more