Wednesday, March 25, 2015

Sparse sum: set cover problem in GAMS

In a set cover problem (http://en.wikipedia.org/wiki/Set_cover_problem)  we can organize the sets in two different ways:

  1. Use a (sparse) two dimensional set. The cover equation will contain a construct like: sum[c(s,i), x(s)].
  2. Use a (sparse) zero-one parameter. In this case the cover equation can have something like: sum[s, c(s,i)*x(s)].

The question came up. What is better? I like the set construct a bit better but that is purely based on aesthetics. The performance is exactly the same.

Data structure: set Data structure: 0/1 parameter
image image

The sets are randomly generated. We solve here just as an LP as we are only interested in the performance of GAMS generating the problem.