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.
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.
brock200-1.lp brock200-2.lp brock200-3.lp brock200-4.lp
brock400-1.lp brock400-2.lp brock400-3.lp brock400-4.lp
C125-9.lp C250-9.lp C500-9.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