Minimal Mod-k Cuts for Packing, Covering and Partitioning Problems
This research was carried out by Richard W. Eglese and Adam N. Letchford and supported by the EPSRC under research grant number GR/L88795.
This page was last updated on 4th August 2000.
The papers arising from the research are available from http://www.lancs.ac.uk/staff/letchfoa/pubs.htm
Two sets of test problems have been created for set packing and are available from this web site (in a format suitable for CPLEX or LINDO).
These instances were created by setting each constraint coefficient to one randomly with probability 0.05. A description of these problems and layout of the files is available here.
Results for upper bounds from LP relaxation and best known solutions (most optimal) are available here.
Test Problems:
pk11c.lp pk12c.lp pk13c.lp pk14c.lp
pk21c.lp pk22c.lp pk23c.lp pk24c.lp
pk31c.lp pk32c.lp pk33c.lp pk34c.lp
pk41c.lp pk42c.lp pk43c.lp pk44c.lp
pk11w.lp pk12w.lp pk13w.lp pk14w.lp
pk21w.lp pk22w.lp pk23w.lp pk24w.lp
pk31w.lp pk32w.lp pk33w.lp pk34w.lp
pk41w.lp pk42w.lp pk43w.lp pk44w.lp
These instances were created by transforming some standard max-clique instances into set packing problems. (The original max-clique instances were used in the second DIMACS implementation challenge.)
Results for upper bounds from LP relaxation and best known solutions (many optimal) are available here.
Test Problems:
brock200-1.lp brock200-2.lp brock200-3.lp brock200-4.lp
brock400-1.lp brock400-2.lp brock400-3.lp brock400-4.lp
p-hat300-1.lp p-hat300-2.lp p-hat300-3.lp p-hat500-1.lp p-hat500-2.lp p-hat500-3.lp
san200-7-2.lp san400-5-1.lp san400-7-1.lp san400-7-2.lp san400-7-3.lp
sanr200-7.lp sanr200-9.lp sanr400-5.lp sanr400-7.lp
Test problems for Set Covering and Set Partitioning may be found on ORLIB
Return to Richard Eglese's home page