Set Covering Problem

A computational study of different approaches with CPLEX

The present work deals with the implementation of several methods for the preprocessing and the exact resolution of the Set Covering Problem (SCP) with techniques of Mixed-Integer Linear Programming (MILP).

The main ideas used in this project were provided by the works of E. Balas and A. Ho (1, 2). The implemented approaches have been tested on the scpnre1-scpnrf5 instances available on the OR-Library. The results obtained are described in this report.

The solver requires the following software:

• CPLEX, only if you want to build the cpxsol
• Boost
• Armadillo
• OpenBLAS (required by Armadillo)
• ARPACK (required by Armadillo)
• LAPACK (required by Armadillo)
• SuperLU (required by Armadillo)

To install the last four libraries (required by Armadillo), on Ubuntu or Debian, you can run the following command:

$ sudo apt update
$ sudo apt install cmake libopenblas-dev liblapack-dev libarpack2-dev libsuperlu-dev

Once you have installed them in your computer, you should change the CPLEX_HOME and the BOOST_HOME variables in Makefile.

To build the solver, type:

$ mkdir lib
$ make cpxsol   # to build the solver with cplex, or
$ make balsol   # to build the Balas solver

Try the solver:

$ ./lib/cpxsol --inputFile data/scpnre1.txt --solver cplex --timeLimit 10

Available Features

	Available
Presolver	none (default)
	cpxdom
Solver	cplex (default)
	maxcol

Extensions

Future extensions of the project include performance improvements and the implementation of a solver (both heuristic and with optimality test) that does not depend on CPLEX.