News - Xpress 2006 Improved and Found Optimal Solutions in MIPLIB 2003

ENGLEWOOD CLIFFS, NJ and LONDON: Dash Optimization announced today that using Xpress-MP 2006B the Dash Optimizer Team obtained the following results for the 11 open problems from MIPLIB 2003:

3 problems were solved for the first time.
The first feasible solution was found for 1 problem
Improved solutions were found for the remaining 7 problems

In addition, 2 previously solved problems were solved for the first time using a standard computer.

Three Mixed Integer Programming (MIP) problems from MIPLIB 2003 (atlanta-ip, msc98-ip, and rd-rplusc-21) were solved by the Dash Optimizer Team for the first time (see Table 1). In addition, two MIPs (a1c1s1 and swath) from MIPLIB 2003 were solved for the first time using a standard computer (see Table 2). These optimal solutions were obtained without the use of logical cuts derived from the knowledge of the model formulation.

Table 1: Objective values and solve times of the new optimal solutions found in MIPLIB 2003 using Xpress-MP 2006.

Problem	Computer System	Solve Time	Optimum is
atlanta-ip	3GHz Intel Core 2 Duo	5h 30 min	90.00987861
msc98-ip	3GHz Intel Core 2 Duo	1h 30 min	19839497.005874
rd-rplusc-21	Xeon 3.0 GHz, 2 CPU, 4 GB RAM	14 min	165395.2753

Table 2: Objective values and solve times found using Xpress-MP v2006B for 2 MIPLIB 2003 problems that were solved for the first time using a standard computer.

Problem	Computer System	Solve Time	Optimum is
a1c1s1	3GHz Intel Core 2 Duo / 2 threads	31 h	11503.444125
swath	3GHz Intel Core 2 Duo / 2 threads	66 h	467.407491

The first feasible solution to stp3d has been found by the Dash Optimizer team using Xpress-MP 2006B. Moreover, improved solutions were found for all of the remaining (seven) open problems from MIPLIB 2003 (see Table 3).

Table 3: Improved objective values found using Xpress-MP 2006.

Problem	Old Best Known Obj.Value (*)	Xpress Improved Obj. Value (**)	GAIN (\|1-(*)/()\|)
ds	283.4425	116.59	58.9%
momentum3	370177.036	236426.335	36.1%
t1717	193221	170195	11.9%
protfold	-30	-31	3.3%
liu	1172	1138	2.9%
dano3mip	691.2	687.733333	0.5%
sp97ar	664565103.76	661670441.4	0.4%

In addition to finding improved solutions for the remaining eight open problems of the MIPLIB 2003, the Dash Optimizer Team also reports that for each of these problems they were able to considerably close the relative gap (See Table 4).

With respect to the stp3d problem where the Dash Optimizer team found the first feasible solution, they were able to close the relative gap by applying new Local Search Heuristics, built on top of Xpress-MP 2006B, to the initial solution thereby reducing the gap to 3% (See Table 4).

Table 4: Current relative gap of the remaining eight open problems from MIPLIB 2003.

Problem	Upper Bound (**)	Lower Bound (*)	GAP (\|1-(*)/()\|)
sp97ar	661670441.4	657862912	0.6%
protfold	-31	-32	3.1%
stp3d	500.736	484.71817	3.3%
dano3mip	687.733333	578.05603	19.0%
t1717	170195	136538.4219	24.6%
ds	116.59	76.32504272	52.8%
liu	1138	560	103.2%
momentum3	236426.335	94824.16406	149.3%

As a result of this recent work on this well know publicly available benchmark the Dash Optimizer Team changed the status of the MIPLIB 2003 set of problems such that 1 new problem has been solved within 1 hour and 2 new problems have been solved as shown in Figure 1.

Figure 1: Comparative analysis of the status of MIPLIB 2003 on Sep-2006 and on Oct-2006.

*Note: For the comparative analysis table, the problems were solved with Xpress-MP v2006B with default settings on a P4 3.6 GHz with 2GB RAM machine running Windows XP.