Skip to content

Implementation of different techniques to solve the Set Covering Problem (SCP).

License

Notifications You must be signed in to change notification settings

caerbannogwhite/set-covering-problem

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

31 Commits
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

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:

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.