Test Problems Home
 
 

Combinatorial Optimization Problems


Many problems arising from diverse areas can be formulated as integer programming problems. One can argue that Combinatorial Optimization and Integer programming are synonymous terms. This is because the majority (if not all) of the combinatorial optimization problems are integer programming problems, usually involving binary variables.

Section1: Test problems in the Internet

The OR-Library, is a collection of several combinatorial optimization test problems (including integer programming, scheduling problems, set covering problems, and graph planarization). Information on the OR-Library can be obtained at http://mscmga.ms.ic.ac.uk/.

During the second DIMACS Implementation Challenge a set of instances were chosen to provide the satisfiability benchmarks. These problems can be found at http://dimacs.rutgers.edu/Challenges/index.html.

A large collection of Traveling Salesman test problems is available at http://www.iwr.uni-heidelberg.de/iwr/comopt/soft/TSPLIB95/TSPLIB.html.

A QAP test problem generator with a known optimal solution is available. The Fortran code of this generator can be obtained by sending an e-mail message to coap@math.ufl.edu and in the body of the message put ``send 92006''.

There is a large collection, QAPLIB, of electronically available data instances for the Quadratic Assignment Problem. The data (and the updated best known solution) are available at http://www.diku.dk/users/karisch/qaplib/inst.html.

During the second DIMACS Implementation Challenge a set of 32 graph instances were chosen to provide benchmarks for the Graph Coloring Problem. These problems can be found at http://dimacs.rutgers.edu/Challenges/index.html.

Section 2: AMPL Test Problems

Test Problem
Description
AMPL Model File
AMPL Data File
1
Quadratic Integer Problem
HCP13.2.1.mod
HCP13.2.1.dat
2
Quadratic Integer Problem
HCP13.2.2.mod
HCP13.2.2.dat
3
Quadratic Assignment Problem
HCP13.5.1.mod
HCP13.5.1.dat
4
Quadratic Assignment Problem
.mod
.dat
5
Quadratic Assignment Problem
.mod
.dat
6
Steiner Problems in Graphs
.mod
.dat
7
Steiner Problems in Graphs
.mod
.dat
8
Steiner Problems in Graphs
.mod
.dat
9
Steiner Problems in Graphs
.mod
.dat
10
Steiner Problems in Graphs
.mod
.dat

 

Test Problems Home