http://www.amsterdamoptimization.com/models/etc/ran14x18.gms. Some notes on this model from a posting on sci.op-research:
The story of the instance ran14x18
We tried CPLEX 5.0 on this instance, obtaining a solution with objective value 3712 but
without proving optimality. The same solution was also found in some runs of the genetic
algorithm from reference 1.
In response to my posting on sci.op-research, some people tried exact solvers on this
instance (fctp, mps), but without success. I also contacted CPLEX, but they also failed
to prove optimality.
On Friday, 13 November 1998, I announced this web page on sci.op-research. Some
hours later I received good news: Jeff proved optimality for ran14x18. Some time later,
a parallel CPLEX version also solved this problem to optimality. I thank the people cited
below for their efforts and comments concerning this problem!
To get an impression of the difficulty of this instance, have a look at the discussion
about the problem, which has remained unsolved for more than 10 months.
Jeff Linderoth (..@mcs.anl.gov)
[Tue, 18 Aug 1998] Probably (repeat probably) a MIP solver that uses flow cover
inequalities would be able to solve the instances. (At least it should do better than
CPLEX for problems of this class). If you don’t have too many instances, then you can
send me the MPS files, and I would be happy to try the solver MINTO out on them for you.
[Fri, 28 Aug 1998] For the problem ran14x18.mps, I ran MINTO until it ran out of memory,
and was only able to improve the lower bound to 3617.994472. When I get the opportunity,
I will perform some longer runs and also try out PARINO (which is like a parallel
version of MINTO) on the problem. I also tried XPRESS and CPLEX and MINTO was much
better than either of these packages (due to flow cover inequalities). How did bc-opt
do? I’ll email more results later. (If you don’t hear from me, send me an email to
remind me). Anyway, sorry I wasn’t able to prove optimality for you, but hopefully the
results are somewhat useful.
[Fri, 13 Nov 1998] I proved the optimality of the solution 3712 for the ran14x18 FCTP
instance. In order to do this I ran my PARINO parallel MIP code for about 52 hours on
32 Pentium II (300MHz) processors. 7624677 nodes of the branch and bound tree were
evaluated in this time. PARINO adds "flow cover inequalities" which are usually quite
useful in helping to improve the LP bounds for these types of problems. Also, I used a
parallel pseudocost-type branching rule which is often better than the CPLEX default or
CPLEX’s strong branching.
Mark Wiley (..@lindo.com)
[Tue, 18 Aug 1998] I saw your recent posting regarding solving randomly generated fixed
charge transportation models. As Jeff Linderoth mentioned in a subsequent posting, flow
cover cuts should help significantly on this type of problem. Our LINGO and What’sBest
packages include this enhancement. If you have some examples in MPS format we could try
them out.
[Fri, 21 Aug 1998] Thanks for sending the model. Unfortunately, flow cover cuts (or at
least our implementation) don’t do as much for your models as I would have liked. Almost
immediately LINGO finds a feasible integer solution of 4151 and a bound of 3359.81.
However, after that it makes virtually no progress. I’d be curious to know how MINTO
performs. I wish I could have given you better news. We will keep your model in our IP
test set. Perhaps a future version will be able to solve it quickly. It is an
interesting problem, small but tough.
Good luck.
[Fri, 23 Oct 1998] We tinkered with some cut options and let it run a bit longer and
found a better solution but failed to solve to optimality. Our best solution was 3764
with a bound of 3522.
Ed Klotz (..@cplex.com)
[Mon, 2 Feb 1998] I tried a few runs with your problem, without success. I tried this on
a very fast machine, and it did not help. I think the fundamental difficulty with this
problem is that is very easy for the optimizer to move fractional solutions in the LP
subproblems from one variable to the next with little or no degradation in the objective
value. Adding cuts, or removing the symmetry of the problem, can help.
[Tue, 3 Feb 1998] Thinking about it [the FCTP model], it’s not very surprising that this
is difficult for the branch and bound to solve. When you relax the integrality
requirement on the y_ij, the problem essentially reduces to a regular transportion
problem (except that the cost coefficients are no longer cij). So the convex hull of the
LP relaxation is quite different from the convex hull of the integer feasible solutions.
This characteristic tends to lead to difficult MIPs. And, I am not the only one who
thinks this is the case. Here’s what Nemhauser and Wolsey say about this problem on page
498 of "Integer and Combinatorial Optimization." "Unfortunately, the bounds obtained
from these relaxations are frequently very poor primarily because they do not accurately
represent the fixed costs..." I do not think we will be able to get CPLEX 5.0 to solve
this problem quickly just by changing parameters. It may be possible to come up with a
priority order file, but I think the best strategy will be to tighten the formulation
by adding cuts.
[Mon, 9 Nov 1998] While CPLEX 6.0 did not perform significantly better on this problem,
we have a development code that established a bound of 3578.6418 in two hours on a fast
machine. The associated integer solution of 3774 is therefore within 5.46 percent of
optimal. We obtained these results with default settings except for setting the
heuristicfreq parameter to 5 (i.e. we applied a rounding heuristic on every 5th node).
We also did a run with variableselect 3 (strong branching), heuristicfreq 5 that we let
go for several days. It eventually found a solution of 3714 and a bound of 3655. So,
CPLEX found a solution within 2 percent of optimal, although it took a long time to do
so. I suspect that with additional experimentation we can get the development version
of CPLEX to find a 2 percent solution in a more reasonable amount of time.
Irv Lustig (..@cplex.com)
[Wed, 25 Nov 1998] We are in the process of developing a new version of CPLEX, so we
decided to try the ran14x18 problem with our new version on a large number of parallel
processors. We used an SGI Origin system with 64 processors. Our parallel development
code solved it with the following output:
Integer optimal solution (0.0001/0): Objective = 3.7120000000e+03
Current MIP best bound = 3.7116289184e+03 (gap = 0.371082, 0.010%)
Solution time = 11517.98 sec.
Iterations = 500288158 Nodes = 8982253 (101132)
This corresponds to 3 hours, 12 minutes wall clock time.
By default, we solve the problem to a .01% gap, but we could decrease this and the time
would only go up a little bit.
Just ran the model on a (cheap) quad core PC with Cplex 11 using default settings (we used threads 4):
S O L V E S U M M A R Y
MODEL m OBJECTIVE cost
TYPE MIP DIRECTION MINIMIZE
SOLVER CPLEX FROM LINE 168
**** SOLVER STATUS 1 NORMAL COMPLETION
**** MODEL STATUS 1 OPTIMAL
**** OBJECTIVE VALUE 3712.0000
RESOURCE USAGE, LIMIT 630.895 3600.000
ITERATION COUNT, LIMIT 48023779 10000000
So we need 630 seconds on this machine to prove optimality (optcr=0).
No comments:
Post a Comment