Carla Michini

Totally Unimodular Congestion Games

  • Alberto Del Pia
  • Michael C. Ferris
  • Carla Michini
    • Categories 0-1 Programming, Game Theory, Polyhedra Tags , ,

    We investigate a new class of congestion games, called Totally Unimodular Congestion Games, in which the strategies of each player are expressed as binary vectors lying in a polyhedron defined using a totally unimodular constraint matrix and an integer right-hand side. We study both the symmetric and the asymmetric variants of the game. In the … Read more

    How tight is the corner relaxation? Insights gained from the stable set problem

  • Gérard Cornuéjols
  • Carla Michini
  • Giacomo Nannicini
    • Categories (Mixed) Integer Linear Programming, Cutting Plane Approaches, Polyhedra Tags , ,

    The corner relaxation of a mixed-integer linear program is a central concept in cutting plane theory. In a recent paper Fischetti and Monaci provide an empirical assessment of the strength of the corner and other related relaxations on benchmark problems. In this paper we give a precise characterization of the bounds given by these relaxations … Read more