Monaldo Mastrolilli

On the integrality Gap of Small Asymmetric Travelling Salesman Problems: A Polyhedral and Computational Approach

  • Eleonora Vercesi
  • Luca Maria Gambardella
  • Stefano Gualandi
  • Monaldo Mastrolilli
  • Janos
    • Categories Combinatorial Optimization, Integer Programming, Linear, Cone and Semidefinite Programming Tags ,

    \(\) In this paper, we investigate the integrality gap of the Asymmetric Traveling Salesman Problem (ATSP) with respect to the linear relaxation given by the Asymmetric Subtour Elimination Problem (ASEP) for small-sized instances. In particular, we focus on the geometric properties and symmetries of the ASEP polytope ( \(P_{ASEP}^n\) ) and its vertices. The polytope’s … Read more

    On the generation of Metric TSP instances with a large integrality gap by branch-and-cut.

  • Luca Maria Gambardella
  • Stefano Gualandi
  • Monaldo Mastrolilli
  • Eleonora Vercesi
    • Categories (Mixed) Integer Linear Programming, Combinatorial Optimization Tags , , ,

    This paper introduces a computational method for generating metric Travelling Salesperson Problem (TSP) instances having a large integrality gap. The method is based on the solution of an NP-hard problem, called IH-OPT, that takes in input a fractional solution of the Subtour Elimination Problem (SEP) on a TSP instance and compute a TSP instance having … Read more

    Minimizing the sum of weighted completion times in a concurrent open shop

  • Monaldo Mastrolilli
  • Maurice Queyranne
  • Andreas S. Schulz
  • Nelson A. Uhan
  • Ola Svensson
    • Categories (Mixed) Integer Linear Programming, Approximation Algorithms, Scheduling Tags , , ,

    We study minimizing the sum of weighted completion times in a concurrent open shop. We give a primal-dual 2-approximation algorithm for this problem. We also show that several natural linear programming relaxations for this problem have an integrality gap of 2. Finally, we show that this problem is inapproximable within a factor strictly less than … Read more