3
$\begingroup$

Can somebody help me with Localsolver? I have installed the academic license and want to solve Split Delivery VRP. I'm using the same model as seen in the website here and using the same instances too (I'm using S51D4). But, why is the gap is always 100% when running?

Is there something wrong with my machine or installation perhaps? I'm running it on Intel i5 7th on 8GB RAM.

Here is the log with a 10 minute time limit.

LocalSolver 11.0.20220721-Win64. All rights reserved.
Load sdvrp.lsp...
Run input...
Run model...
Run param...
Run solver...

Model:  expressions = 13905, decisions = 2550, constraints = 101, objectives = 1
Param:  time limit = 360 sec, no iteration limit

[objective direction ]:     minimize

[  0 sec,       0 itr]: No feasible solution found (infeas = 51)
[  1 sec,   39085 itr]:         2445
[  2 sec,  133145 itr]:         1929
[  3 sec,  232519 itr]:         1833
[  4 sec,  318825 itr]:         1784
[  5 sec,  393069 itr]:         1764
[  6 sec,  464380 itr]:         1761
[  7 sec,  535342 itr]:         1755
[  8 sec,  607587 itr]:         1747
[  9 sec,  680000 itr]:         1732
[ 10 sec,  749683 itr]:         1728
[ optimality gap     ]:      100.00%
[ 11 sec,  822365 itr]:         1727
[ 12 sec,  885106 itr]:         1708
[ 13 sec,  928483 itr]:         1708
[ 14 sec,  982151 itr]:         1708
[ 15 sec, 1034334 itr]:         1707
[ 16 sec, 1079856 itr]:         1707
[ 17 sec, 1132541 itr]:         1695
[ 18 sec, 1200000 itr]:         1695
[ 19 sec, 1274687 itr]:         1695
[ 20 sec, 1274687 itr]:         1695
[ optimality gap     ]:      100.00%
[ 21 sec, 1338878 itr]:         1695
[ 22 sec, 1466325 itr]:         1695
[ 23 sec, 1529968 itr]:         1695
[ 24 sec, 1599581 itr]:         1689
[ 25 sec, 1640000 itr]:         1686
[ 26 sec, 1688389 itr]:         1686
[ 27 sec, 1759810 itr]:         1682
[ 28 sec, 1759810 itr]:         1682
[ 29 sec, 1880854 itr]:         1682
[ 30 sec, 1880854 itr]:         1682
[ optimality gap     ]:      100.00%
[ 31 sec, 1999512 itr]:         1682
[ 32 sec, 2039631 itr]:         1678
[ 33 sec, 2085455 itr]:         1678
[ 34 sec, 2143392 itr]:         1678
[ 35 sec, 2143392 itr]:         1672
[ 36 sec, 2275360 itr]:         1672
[ 37 sec, 2336860 itr]:         1672
[ 38 sec, 2406899 itr]:         1672
[ 39 sec, 2480000 itr]:         1672
[ 40 sec, 2547043 itr]:         1672
[ optimality gap     ]:      100.00%
[ 41 sec, 2547043 itr]:         1672
[ 42 sec, 2680000 itr]:         1672
[ 43 sec, 2747689 itr]:         1672
...
[ optimality gap      ]:      100.00%
[311 sec, 19858963 itr]:         1603
[312 sec, 19926467 itr]:         1603
[313 sec, 19976892 itr]:         1603
[314 sec, 20041597 itr]:         1603
[315 sec, 20113488 itr]:         1603
[316 sec, 20148399 itr]:         1603
[317 sec, 20148399 itr]:         1603
[318 sec, 20240000 itr]:         1603
[319 sec, 20280000 itr]:         1603
[320 sec, 20314286 itr]:         1603
[ optimality gap      ]:      100.00%
[321 sec, 20356044 itr]:         1603
[322 sec, 20400000 itr]:         1603
[323 sec, 20438525 itr]:         1603
[324 sec, 20438525 itr]:         1603
[325 sec, 20481118 itr]:         1603
[326 sec, 20589307 itr]:         1603
[327 sec, 20633734 itr]:         1603
[328 sec, 20680000 itr]:         1603
[329 sec, 20720000 itr]:         1603
[330 sec, 20794236 itr]:         1603
[ optimality gap      ]:      100.00%
[331 sec, 20852580 itr]:         1603
[332 sec, 20901515 itr]:         1602
[333 sec, 20966356 itr]:         1602
[334 sec, 21024270 itr]:         1601
[335 sec, 21092709 itr]:         1601
[336 sec, 21147857 itr]:         1601
[337 sec, 21210912 itr]:         1601
[338 sec, 21263487 itr]:         1601
[339 sec, 21337642 itr]:         1601
[340 sec, 21409656 itr]:         1601
[ optimality gap      ]:      100.00%
[341 sec, 21479419 itr]:         1601
[342 sec, 21548873 itr]:         1601
[343 sec, 21601571 itr]:         1601
[344 sec, 21601571 itr]:         1601
[345 sec, 21756027 itr]:         1601
[346 sec, 21833407 itr]:         1601
[347 sec, 21909596 itr]:         1601
[348 sec, 21986893 itr]:         1601
[349 sec, 22065020 itr]:         1601
[350 sec, 22129717 itr]:         1601
[ optimality gap      ]:      100.00%
[351 sec, 22196673 itr]:         1601
[352 sec, 22196673 itr]:         1601
[353 sec, 22314615 itr]:         1601
[354 sec, 22373794 itr]:         1599
[355 sec, 22373794 itr]:         1599
[356 sec, 22440000 itr]:         1599
[357 sec, 22558681 itr]:         1599
[358 sec, 22558681 itr]:         1599
[359 sec, 22700231 itr]:         1599
[360 sec, 22767261 itr]:         1599
[ optimality gap      ]:      100.00%
[360 sec, 22767261 itr]:         1599
[ optimality gap      ]:      100.00%

22767261 iterations performed in 360 seconds

Feasible solution:
  obj    =         1599
  gap    =      100.00%
  bounds =            0

Run output...
$\endgroup$
5
  • $\begingroup$ please help @LocalSolver $\endgroup$
    – overboxed
    Commented Aug 8, 2022 at 6:32
  • $\begingroup$ It seems that localsolver finds a bound of 0, and is unable to improve on it. So the question is why does the lower bound not improve. $\endgroup$
    – Richard
    Commented Aug 8, 2022 at 7:47
  • $\begingroup$ yeah, i don't know why. i didn't modify the model nor the instances @Richard $\endgroup$
    – overboxed
    Commented Aug 8, 2022 at 8:13
  • 1
    $\begingroup$ Did you try solving it with Gurobi? (I work for Gurobi, hence my question :) ) $\endgroup$
    – Richard
    Commented Aug 10, 2022 at 9:45
  • $\begingroup$ Sadly no @Richard, because i'm stuck with subtour elimination constraint. Can you help me with this one? $\endgroup$
    – overboxed
    Commented Aug 19, 2022 at 4:35

1 Answer 1

2
$\begingroup$

Delivering good lower bounds in minutes is difficult, particularly regarding routing or scheduling problems. Seeing the lower bound's LocalSolver stuck to 0 after 5 minutes on such a highly combinatorial problem as the Split Delivery Vehicle Routing Problem (SDVRP) is unsurprising. We first focus on delivering high-quality feasible solutions, that is, quality primal/upper bounds. (Because this is the demand of our customers). Hence, on SDVRP, the solutions provided are very good (< 5%) compared to the state-of-the-art.

Hexaly relies on reformulation techniques combined with column and row generation to compute lower bounds on routing-like problems. Dramatic improvements for many families of vehicle routing problems have been obtained recently; these will be available in the next version (11.5) planned for October 2022.

For further support, I suggest you contact Hexaly support at [email protected]. This is the primary channel for getting fast and accurate support for any concern, even for academic users. The support is done by our optimization science team, which develops the solver. They will be pleased to answer all your questions and help you get the best from the solver.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.