D. C. Tozoni

A Practical Iterative Algorithm for the Art Gallery Problem using Integer Linear Programming

  • Pedro J. de Rezende
  • Cid C. de Souza
  • D. C. Tozoni
    • Categories Combinatorial Optimization, Integer Programming Tags , , ,

    In the last few decades, the search for exact algorithms for known NP-hard geometric problems has intensified. Many of these solutions make use of Integer Linear Programming (ILP) modeling and rely on state of the art solvers, to be able to find optimal solutions for large instances in a matter of minutes. In this work, … Read more

    The Quest for Optimal Solutions for the Art Gallery Problem: a Practical Iterative Algorithm

  • Pedro J. de Rezende
  • Cid C. de Souza
  • D. C. Tozoni
    • Categories Combinatorial Optimization Tags , , , , ,

    The general Art Gallery Problem (AGP) consists in finding the minimum number of guards sufficient to ensure the visibility coverage of an art gallery represented by a polygon. The AGP is a well known NP-hard problem and, for this reason, all algorithms proposed so far to solve it are unable to guarantee optimality except in … Read more