subtour elimination

Binary Integer Program Reformulation: A Set System Approximation Approach

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

    This paper presents a generic reformulation framework for binary integer programs (BIPs) without imposing additional specifications for the objective function or constraints. To facilitate such generality, we introduce a set system approximation theory designed to identify the tightest inner and outer approximations for any binary solution space using special types of set systems. This development … 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