arki001

the model originates in the metalurgic industry

The first reported solution is due to Anureet Saxena and Egon Balas, reported in Optimizing over the Split Closure, MSRR-674, December 2005. Solving time was about 64 hours.

Bob Bixby reports solving this instance by letting CPLEX run for nearly a month, computing more than 100,000,000 nodes.

Using SCIP with CPLEX 10.0 as LP-Solver Tobias Achterberg solved arki001 in less than 9 hours on an AMD Opteron 2.2 GHz computing only about 3 million nodes. Again strong branching seems to be the key to success, as the following settings were used:

• allfullstrong in the first 5 depth levels (this means to apply strong branching without iteration limit on ALL integer variables, not only the ones with fractional LP solution)
• fullstrong branching whenever the current node's dual bound is equal to the global dual bound (this means to apply strong branching without iteration limit to all integer variables with fractional LP solution)
• reliability branching on the remaining nodes (however, this seems to apply strong branching almost never, since the "available" strong branching iterations are already used up by fullstrong)
• In addition, aggressive conflict analysis was applied, even on infeasible and bound exceeding strong branching problems. Further experiments indicate that this reduces the number of nodes to explore considerably.

Alkis Vazacopoulos reports solving this instance using XPRESS 2006A in 4 hours on a 2 processor Xeon system, computing about 1,200,000 nodes.