Following are the compressed Linear Ordering Problems in the paper "xQx
as a Modeling and Solution Framework for the Linear Ordering Problem" by
Mark Lewis , Bahram Alidaee, Fred Glover, and Gary Kochenberger.
At the bottom of the page is the executable I used to generate the problems.
|
Problem ID |
n |
# binary variables |
# CPLEX rows |
|
20 |
190 |
2280 |
|
|
30 |
435 |
8,120 |
|
|
40 |
780 |
19,760 |
|
|
50 |
1225 |
39,200 |
|
|
60 |
1770 |
68,440 |
|
|
70 |
2415 |
109,480 |
|
|
80 |
3160 |
164,320 |
|
|
90 |
4005 |
234,960 |
|
|
100 |
4950 |
323,400 |
|
|
LO_LAK_150 |
150 |
11175 |
1,102,600 |
|
LO_LAK_200 |
200 |
19900 |
2,626,800 |
The last two problems are big (LAK150 is 7 MB, and LAK200 is 17 MB), so the
following link is to the executable that will recreate any of the problems
listed, just follow the text directions (enter 1 for yes, 0 for no).
ProblemSets/LinearOrderingProblems/linear_ordering1.exe
Results we obtained on these problems using a path-linking multi-start tabu search (maximization).
|
|
|
|
CPLEX |
|
|
|
MSTR |
||
|
Problem ID |
Tree Nodes |
Time to Sol |
Total Time |
Final MIP Gap |
Solution |
|
Time to Sol |
Total Time |
Solution |
|
LAK_20 |
0 |
1 |
1 |
0% |
160 |
|
1 |
60 |
160 |
|
LAK_30 |
94 |
114 |
150 |
0% |
240 |
|
7 |
150 |
240 |
|
LAK_40 |
850 |
2,363 |
3,310 |
0% |
611 |
|
103 |
364 |
600 |
|
LAK_50 |
2651 |
171,145 |
175,671 |
6% |
732 |
|
676 |
1332 |
705 |
|
LAK_60 |
550 |
129,657 |
175,491 |
14% |
1084 |
|
534 |
5402 |
1010 |
|
LAK_70 |
48 |
34,588 |
54,398 |
87% |
970 |
|
5111 |
5402 |
1307 |
|
LAK_80 |
30 |
7,601 |
175,158 |
134% |
930 |
|
5045 |
5711 |
1453 |
|
LAK_90 |
10 |
18,237 |
170,105 |
133% |
1150 |
|
5742 |
7704 |
1687 |
|
LAK_100 |
2 |
24,632 |
88,108 |
155% |
1363 |
|
7994 |
8923 |
1943 |
|
LAK_150 |
- |
- |
- |
- |
- |
|
14950 |
16063 |
2857 |
|
LAK_200 |
- |
- |
- |
- |
- |
|
21175 |
50005 |
2875 |
TABLE 2. Comparison of CPLEX and Multi-start Tabu Search