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.

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 (

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.

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.

[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).

[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.

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.

[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