[Scip] VRP example says "infeasible"
Marc Pfetsch
m.pfetsch at tu-bs.de
Tue Aug 4 16:13:33 MEST 2009
Hi Tuomo,
we read your previous email, but the matter is more involved than I thought:
The behavior is a bug in Clp as well as in SCIP. I will try to give a
short explanation:
0. The problem is in the dual ray that SCIP needs from Clp in order to
price out variables to obtain a feasible solution.
1. In Clp the dual ray has the wrong sign. This can be corrected either
in Clp or in lpi_clp.cpp of SCIP. In fact, the current trunk version of
Clp is already correct.
2. Because of a bug in SCIP, the status of Clp will never be infeasible,
but always "objective limit reached". This is not generally a problem,
but Clp does not generate a ray in this case. This can be fixed, but it
involves some changes in SCIP itself.
There are some further bugs in Clp as well as in lpi_clp.cpp. I am
working on it, but do not have a solution working in general. I think
that my current fix will not be helpful for you at the moment. I hope to
get a solution in the next weeks and will get back to you again. Can you
wait that long? My only current advice is to use a different LP solver.
If you are brave and want to fiddle around the interface I could give
you some hints of what to try, but I am not sure whether it will work.
Anyway, we plan a new release in September, which hopefully includes
fixes for the problems above.
Best,
Marc
P.S. The current version of Clp is 1.10 (not 2.2), as far as I know.
Tuomo Takkula wrok:
> Hi,
>
> the vrp executable from the VRP example reports "infeasible" whenever I feed it one of the CVRP data
> sets, see below.
>
> We use Clp 2.2 as LP solver. Am I missing something? (No, the -h option won't help).
>
>
> Cheers
> Tuomo
>
>
> $ ../bin/vrp eil7.vrp
> SCIP version 1.1.0 [precision: 8 byte] [memory: block] [mode: debug] [LP solver: Clp 1.8stable]
> Copyright (c) 2002-2008 Konrad-Zuse-Zentrum fuer Informationstechnik Berlin (ZIB)
>
> Max demand per tour 3
> presolving:
> presolving (1 rounds):
> 0 deleted vars, 0 deleted constraints, 0 tightened bounds, 0 added holes, 0 changed sides, 0
> changed coefficients
> 0 implications, 0 cliques
> presolved problem has 21 variables (0 bin, 21 int, 0 impl, 0 cont) and 33 constraints
> 33 constraints of type <linear>
> Presolving Time: 0.00
>
> time | node | left |LP iter| mem |mdpt |frac |vars |cons |ccons|cols |rows |cuts |confs|strbr|
> dualbound | primalbound | gap
> 0.0s| 1 | 0 | 7 | 116k| 0 | - | 21 | 33 | 33 | 21 | 33 | 0 | 0 | 0 |
> -- | -- | 0.00%
> 0.0s| 1 | 0 | 7 | 116k| 0 | - | 21 | 33 | 33 | 21 | 33 | 0 | 0 | 0 |
> -- | -- | 0.00%
>
> SCIP Status : problem is solved [infeasible]
> Solving Time (sec) : 0.00
> Solving Nodes : 1
> Primal Bound : +1.00000000000000e+20 (0 solutions)
> Dual Bound : +1.00000000000000e+20
> Gap : 0.00 %
> no solution available
>
>
>
More information about the Scip
mailing list