[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