search

inria-UFF / VRPSolverEasy

A simple Python interface for VRPSolver, a state-of-the-art Branch-Cut-and-Price exact solver for vehicle routing problems
https://vrpsolvereasy.readthedocs.io/en/latest/
MIT License
106 stars 10 forks source link

Bucket graph for G_1 is regenerated as bucket steps were adjusted for XX vertices #12

Closed taox142 closed 7 months ago

taox142 commented 8 months ago

Hello,

I am running a pretty large VRPTW instance. And from time to time, I came across this issue. It seems the model stops running after showing this message. For example, "Bucket graph for G_1 is regenerated as bucket steps were adjusted for 861 vertices"

What does this message mean? Does this mean the graph is too large? The full log is attached below.

Thank you and have a good time! Tao

VRPSolver v0.5.28, 16/03/2023, © Inria Bordeaux, France, vrpsolver.math.u-bordeaux.fr
Corresponds to the solver by Pessoa, Sadykov, Uchoa and Vanderbeck (2020)
Paper: dx.doi.org/10.1007/s10107-020-01523-z

BaPCod v0.77, 23/03/2023, © Inria Bordeaux, France, bapcod.math.u-bordeaux.fr THIS CODE IS PROVIDED AS IS, USE IT AT YOUR OWN RISK


--- VRPSOLVER PARAMETERS ---
GlobalTimeLimit = 0
MaxNbOfBBtreeNodeTreated = 100000
treeSearchStrategy = 1
RCSPstopCutGenTimeThresholdInPricing = 10
RCSPhardTimeThresholdInPricing = 20
RCSPredCostFixingTimeThreshold = 100
RCSPnumberOfBucketsPerVertex = 25
RCSPdynamicBucketSteps = 1
RCSPuseBidirectionalSearch = 2
RCSPapplyReducedCostFixing = 1
RCSPredCostFixingFalseGap = 0
RCSPmaxNumOfColsPerIteration = 30
RCSPmaxNumOfColsPerExactIteration = 150
StabilizationMinPhaseOfStage = 0
RCSPmaxNumOfLabelsInEnumeration = 1000000
RCSPmaxNumOfEnumeratedSolutions = 1000000
RCSPmaxNumOfEnumSolutionsForMIP = 10000
RCSPinitNGneighbourhoodSize = 8
RCSPmaxNGneighbourhoodSize = 0
RCSPrankOneCutsMaxNumPerRound = 100
RCSPrankOneCutsMaxNumRows = 5
RCSPrankOneCutsMemoryType = 2
CutTailingOffThreshold = 0.02
CutTailingOffCounterThreshold = 3
SafeDualBoundScaleFactor = -1
StrongBranchingPhaseOneCandidatesNumber = 100
StrongBranchingPhaseOneTreeSizeEstimRatio = 0.3
StrongBranchingPhaseTwoCandidatesNumber = 3
StrongBranchingPhaseTwoTreeSizeEstimRatio = 0.1
MaxTimeForRestrictedMasterIpHeur = -1
DivingHeurUseDepthLimit = -1
MaxLDSbreadth = 0
MaxLDSdepth = 0
Model is built TIME = 0h0m7s54t = 754
************************************************************************************************
**** BaB tree root node
**** Local DB = -1e+12, global bounds : [ -1e+12 , 87505.2 ], TIME = 0h0m7s54t = 754
**** 1 open nodes, 0 columns (0 active), 0 dyn. constrs. (0 active), 1720 art. vars. (1720 active)
************************************************************************************************
<DWph=2> <it= 10> <et=12.96> <Mt= 0.07> <Spt= 4.57> <nCl=300> <DB=-8529462.9402> <Mlp=9654210.0060> <PB=87505.2> 
<DWph=2> <it= 20> <et=17.58> <Mt= 0.14> <Spt= 4.47> <nCl=300> <DB=-7560972.7277> <Mlp=6386983.0241> <PB=87505.2> 
<DWph=2> <it= 30> <et=22.34> <Mt= 0.30> <Spt= 4.44> <nCl=300> <DB=-7722995.3577> <Mlp=4824800.6132> <PB=87505.2> 
<DWph=2> <it= 40> <et=27.07> <Mt= 0.41> <Spt= 4.32> <nCl=300> <DB=-6175141.7326> <Mlp=3810118.0973> <PB=87505.2> 
<DWph=2> <it= 50> <et=31.92> <Mt= 0.47> <Spt= 4.36> <nCl=300> <DB=-5829809.8399> <Mlp=3259668.7045> <PB=87505.2> 
<DWph=2> <it= 60> <et=36.78> <Mt= 0.67> <Spt= 4.17> <nCl=300> <DB=-5209936.3167> <Mlp=2509834.1966> <PB=87505.2> 
<DWph=2> <it= 70> <et=41.81> <Mt= 0.71> <Spt= 4.31> <nCl=287> <DB=-6757403.6967> <Mlp=2133169.9270> <PB=87505.2> 
<DWph=2> <it= 80> <et=46.88> <Mt= 0.82> <Spt= 4.24> <nCl=300> <DB=-5330209.4980> <Mlp=1816169.1539> <PB=87505.2> 
<DWph=2> <it= 90> <et=52.46> <Mt= 1.17> <Spt= 4.39> <nCl=300> <DB=-4169331.1374> <Mlp=1465987.2680> <PB=87505.2> 
<DWph=2> <it=100> <et=58.22> <Mt= 1.38> <Spt= 4.37> <nCl=300> <DB=-4055218.2170> <Mlp=1187239.5206> <PB=87505.2> 
<DWph=2> <it=110> <et=63.91> <Mt= 1.18> <Spt= 4.49> <nCl=300> <DB=-4931079.4171> <Mlp=1064474.8854> <PB=87505.2> 
<DWph=2> <it=120> <et=69.39> <Mt= 1.18> <Spt= 4.28> <nCl=300> <DB=-4536686.5488> <Mlp=969208.9019> <PB=87505.2> 
<DWph=2> <it=130> <et=74.93> <Mt= 1.15> <Spt= 4.38> <nCl=300> <DB=-4355331.9214> <Mlp=888580.8075> <PB=87505.2> 
<DWph=2> <it=140> <et=81.21> <Mt= 1.67> <Spt= 4.59> <nCl=300> <DB=-4392910.4076> <Mlp=774954.2875> <PB=87505.2> 
<DWph=2> <it=150> <et=87.20> <Mt= 1.53> <Spt= 4.45> <nCl=300> <DB=-4031503.9333> <Mlp=700653.7514> <PB=87505.2> 
<DWph=2> <it=160> <et=93.86> <Mt= 1.90> <Spt= 4.75> <nCl=300> <DB=-4068179.2032> <Mlp=619298.1728> <PB=87505.2> 
<DWph=2> <it=170> <et=100.54> <Mt= 1.80> <Spt= 4.86> <nCl=300> <DB=-3705945.2716> <Mlp=564303.1376> <PB=87505.2> 
<DWph=2> <it=180> <et=107.40> <Mt= 2.25> <Spt= 4.59> <nCl=300> <DB=-4659148.5294> <Mlp=474729.3553> <PB=87505.2> 
<DWph=2> <it=190> <et=113.98> <Mt= 2.12> <Spt= 4.44> <nCl=300> <DB=-3546785.7259> <Mlp=409571.8901> <PB=87505.2> 
<DWph=2> <it=200> <et=119.82> <Mt= 1.50> <Spt= 4.33> <nCl=300> <DB=-3493182.4391> <Mlp=377291.7169> <PB=87505.2> 
<DWph=2> <it=210> <et=126.22> <Mt= 2.03> <Spt= 4.35> <nCl=300> <DB=-3029427.9823> <Mlp=337225.1997> <PB=87505.2> 
<DWph=2> <it=220> <et=133.14> <Mt= 2.61> <Spt= 4.29> <nCl=300> <DB=-2199943.2025> <Mlp=304114.5169> <PB=87505.2> 
<DWph=2> <it=230> <et=140.55> <Mt= 2.86> <Spt= 4.54> <nCl=300> <DB=-1938067.6699> <Mlp=272191.0835> <PB=87505.2> 
<DWph=2> <it=240> <et=147.81> <Mt= 2.66> <Spt= 4.59> <nCl=300> <DB=-1835857.8149> <Mlp=248541.0940> <PB=87505.2> 
<DWph=2> <it=250> <et=154.51> <Mt= 2.22> <Spt= 4.47> <nCl=300> <DB=-777417.4917> <Mlp=240642.1714> <PB=87505.2> 
<DWph=2> <it=260> <et=161.06> <Mt= 2.02> <Spt= 4.51> <nCl=300> <DB=-379440.2326> <Mlp=234917.3161> <PB=87505.2> 
<DWph=2> <it=270> <et=168.08> <Mt= 2.52> <Spt= 4.48> <nCl=300> <DB=-263883.7407> <Mlp=228137.2792> <PB=87505.2> 
<DWph=2> <it=280> <et=175.37> <Mt= 2.77> <Spt= 4.50> <nCl=300> <DB=-261359.7604> <Mlp=221293.5327> <PB=87505.2> 
<DWph=2> <it=290> <et=183.14> <Mt= 3.19> <Spt= 4.56> <nCl=282> <DB=-149809.9022> <Mlp=214868.1581> <PB=87505.2> 
<DWph=2> <it=300> <et=190.11> <Mt= 2.38> <Spt= 4.57> <nCl=299> <DB=-218314.9434> <Mlp=211025.8885> <PB=87505.2> 
<DWph=2> <it=310> <et=197.74> <Mt= 3.03> <Spt= 4.59> <nCl=300> <DB=-118507.5779> <Mlp=205107.9348> <PB=87505.2> 
<DWph=2> <it=320> <et=205.51> <Mt= 3.00> <Spt= 4.76> <nCl=300> <DB=-72840.8157> <Mlp=199192.9726> <PB=87505.2> 
<DWph=2> <it=330> <et=213.47> <Mt= 3.14> <Spt= 4.80> <nCl=298> <DB=-196591.3722> <Mlp=193157.3782> <PB=87505.2> 
<DWph=2> <it=340> <et=220.94> <Mt= 2.54> <Spt= 4.81> <nCl=246> <DB=-108532.8693> <Mlp=188624.8923> <PB=87505.2> 
<DWph=2> <it=350> <et=227.24> <Mt= 1.55> <Spt= 4.74> <nCl=300> <DB=-99527.9312> <Mlp=186283.3984> <PB=87505.2> 
<DWph=2> <it=360> <et=233.66> <Mt= 1.98> <Spt= 4.42> <nCl=260> <DB=-169784.5206> <Mlp=182594.7395> <PB=87505.2> 
<DWph=2> <it=370> <et=240.09> <Mt= 1.83> <Spt= 4.58> <nCl=290> <DB=-122591.0033> <Mlp=178829.6998> <PB=87505.2> 
<DWph=2> <it=380> <et=246.86> <Mt= 1.96> <Spt= 4.80> <nCl=299> <DB=-32744.4309> <Mlp=175312.6655> <PB=87505.2> 
<DWph=2> <it=390> <et=253.07> <Mt= 1.75> <Spt= 4.45> <nCl=291> <DB= -872.6876> <Mlp=172112.6548> <PB=87505.2> 
<DWph=2> <it=400> <et=259.52> <Mt= 2.01> <Spt= 4.42> <nCl=289> <DB=26797.5963> <Mlp=168351.9374> <PB=87505.2> 
<DWph=2> <it=410> <et=266.04> <Mt= 2.05> <Spt= 4.45> <nCl=283> <DB=-66711.8383> <Mlp=165209.3863> <PB=87505.2> 
<DWph=2> <it=420> <et=273.38> <Mt= 2.67> <Spt= 4.65> <nCl=300> <DB=-22217.0064> <Mlp=160239.6038> <PB=87505.2> 
<DWph=2> <it=430> <et=279.95> <Mt= 1.94> <Spt= 4.62> <nCl=297> <DB=-23775.9991> <Mlp=157691.2233> <PB=87505.2> 
<DWph=2> <it=440> <et=287.22> <Mt= 2.54> <Spt= 4.71> <nCl=300> <DB=19709.2361> <Mlp=153721.5346> <PB=87505.2> 
<DWph=2> <it=450> <et=294.60> <Mt= 2.52> <Spt= 4.84> <nCl=300> <DB= 7671.5007> <Mlp=150492.9924> <PB=87505.2> 
<DWph=2> <it=460> <et=301.81> <Mt= 2.02> <Spt= 5.05> <nCl=300> <DB=-25964.4597> <Mlp=148015.9902> <PB=87505.2> 
<DWph=2> <it=470> <et=307.75> <Mt= 1.27> <Spt= 4.65> <nCl=277> <DB=33429.1380> <Mlp=146273.7664> <PB=87505.2> 
<DWph=2> <it=480> <et=314.02> <Mt= 1.40> <Spt= 4.86> <nCl=260> <DB=29417.6954> <Mlp=144601.8886> <PB=87505.2> 
<DWph=2> <it=490> <et=320.90> <Mt= 1.57> <Spt= 5.29> <nCl=270> <DB= 8562.5935> <Mlp=142910.1004> <PB=87505.2> 
<DWph=2> <it=500> <et=327.13> <Mt= 1.54> <Spt= 4.67> <nCl=264> <DB= 2154.0543> <Mlp=141206.5037> <PB=87505.2> 
<DWph=2> <it=510> <et=333.75> <Mt= 1.90> <Spt= 4.71> <nCl=272> <DB=-15575.0202> <Mlp=138668.8670> <PB=87505.2> 
<DWph=2> <it=520> <et=340.22> <Mt= 1.57> <Spt= 4.89> <nCl=245> <DB=15027.2950> <Mlp=136788.6599> <PB=87505.2> 
<DWph=2> <it=530> <et=346.87> <Mt= 1.69> <Spt= 4.94> <nCl=271> <DB=53704.7499> <Mlp=135090.8109> <PB=87505.2> 
<DWph=2> <it=540> <et=353.10> <Mt= 1.73> <Spt= 4.47> <nCl=273> <DB=32628.5256> <Mlp=133249.3217> <PB=87505.2> 
<DWph=2> <it=550> <et=359.23> <Mt= 1.70> <Spt= 4.42> <nCl=280> <DB=22262.9413> <Mlp=131091.4121> <PB=87505.2> 
<DWph=2> <it=560> <et=365.46> <Mt= 1.78> <Spt= 4.44> <nCl=286> <DB=22905.3921> <Mlp=128819.8248> <PB=87505.2> 
<DWph=2> <it=570> <et=371.34> <Mt= 1.46> <Spt= 4.40> <nCl=220> <DB=72721.3517> <Mlp=127206.1063> <PB=87505.2> 
<DWph=2> <it=580> <et=377.72> <Mt= 1.81> <Spt= 4.56> <nCl=276> <DB=91807.7715> <Mlp=125988.3238> <PB=87505.2> 
<DWph=2> <it=590> <et=383.43> <Mt= 1.02> <Spt= 4.56> <nCl=223> <DB=43404.8018> <Mlp=125356.6838> <PB=87505.2> 
<DWph=2> <it=600> <et=388.95> <Mt= 1.01> <Spt= 4.49> <nCl=281> <DB=97713.0757> <Mlp=124574.3960> <PB=87505.2> 
<DWph=2> <it=610> <et=395.21> <Mt= 1.08> <Spt= 5.16> <nCl=310> <DB=69912.6001> <Mlp=123858.6611> <PB=87505.2> 
<DWph=2> <it=620> <et=401.46> <Mt= 1.22> <Spt= 5.03> <nCl=247> <DB=60293.5634> <Mlp=123028.3868> <PB=87505.2> 
<DWph=2> <it=630> <et=407.24> <Mt= 1.25> <Spt= 4.51> <nCl=278> <DB=75242.4719> <Mlp=122201.9457> <PB=87505.2> 
<DWph=2> <it=640> <et=412.25> <Mt= 0.63> <Spt= 4.37> <nCl=256> <DB=46872.8861> <Mlp=121937.5753> <PB=87505.2> 
<DWph=2> <it=650> <et=417.59> <Mt= 0.89> <Spt= 4.43> <nCl=243> <DB=48562.0586> <Mlp=121537.1856> <PB=87505.2> 
<DWph=2> <it=660> <et=423.25> <Mt= 0.87> <Spt= 4.77> <nCl=253> <DB=-89220.2866> <Mlp=120978.8065> <PB=87505.2> 
<DWph=2> <it=670> <et=428.44> <Mt= 0.81> <Spt= 4.37> <nCl=262> <DB=63955.3074> <Mlp=120658.4692> <PB=87505.2> 
<DWph=2> <it=680> <et=434.05> <Mt= 1.11> <Spt= 4.49> <nCl=268> <DB=11010.8137> <Mlp=120091.2249> <PB=87505.2> 
<DWph=2> <it=690> <et=440.23> <Mt= 1.20> <Spt= 4.95> <nCl=253> <DB=-13014.8717> <Mlp=119580.5200> <PB=87505.2> 
<DWph=2> <it=700> <et=445.87> <Mt= 1.11> <Spt= 4.53> <nCl=252> <DB=96676.8832> <Mlp=118939.7760> <PB=87505.2> 
<DWph=2> <it=710> <et=452.13> <Mt= 1.03> <Spt= 5.21> <nCl=269> <DB=82923.3634> <Mlp=118608.3048> <PB=87505.2> 
<DWph=2> <it=720> <et=458.29> <Mt= 0.97> <Spt= 5.05> <nCl=227> <DB=77814.1804> <Mlp=118280.4174> <PB=87505.2> 
<DWph=2> <it=730> <et=465.05> <Mt= 1.14> <Spt= 5.60> <nCl=258> <DB=-160123.5609> <Mlp=117513.9616> <PB=87505.2> 
<DWph=2> <it=740> <et=470.70> <Mt= 0.85> <Spt= 4.79> <nCl=268> <DB=96512.1275> <Mlp=117035.2298> <PB=87505.2> 
<DWph=2> <it=750> <et=476.54> <Mt= 0.70> <Spt= 5.12> <nCl=231> <DB=97494.3264> <Mlp=116744.1054> <PB=87505.2> 
<DWph=2> <it=760> <et=481.92> <Mt= 0.91> <Spt= 4.46> <nCl=286> <DB=103160.6043> <Mlp=116233.4785> <PB=87505.2> 
<DWph=2> <it=770> <et=487.48> <Mt= 0.93> <Spt= 4.62> <nCl=206> <DB=96578.5300> <Mlp=115751.5391> <PB=87505.2> 
<DWph=2> <it=780> <et=493.00> <Mt= 0.78> <Spt= 4.71> <nCl=262> <DB=83740.1043> <Mlp=115535.4752> <PB=87505.2> 
<DWph=2> <it=790> <et=498.49> <Mt= 0.99> <Spt= 4.49> <nCl=259> <DB=82984.6227> <Mlp=115222.2514> <PB=87505.2> 
<DWph=2> <it=800> <et=504.25> <Mt= 0.84> <Spt= 4.91> <nCl=248> <DB=91317.8105> <Mlp=114924.6562> <PB=87505.2> 
<DWph=2> <it=810> <et=509.72> <Mt= 0.93> <Spt= 4.53> <nCl=250> <DB=104739.2475> <Mlp=114611.1079> <PB=87505.2> 
<DWph=2> <it=820> <et=515.19> <Mt= 0.36> <Spt= 5.08> <nCl=133> <DB=110040.1255> <Mlp=114587.1607> <PB=87505.2> 
<DWph=2> <it=830> <et=520.63> <Mt= 0.37> <Spt= 5.07> <nCl=131> <DB=112051.3208> <Mlp=114561.7196> <PB=87505.2> 
<DWph=2> <it=840> <et=526.01> <Mt= 0.43> <Spt= 4.93> <nCl=111> <DB=103366.7493> <Mlp=114514.0440> <PB=87505.2> 
<DWph=2> <it=850> <et=532.13> <Mt= 0.72> <Spt= 5.39> <nCl=191> <DB=111648.1835> <Mlp=114265.3404> <PB=87505.2> 
<DWph=2> <it=860> <et=539.47> <Mt= 0.84> <Spt= 6.48> <nCl=226> <DB=89749.5364> <Mlp=113915.0832> <PB=87505.2> 
<DWph=2> <it=863> <et=541.49> <Mt= 0.12> <Spt= 1.91> <nCl=  7> <DB=113904.5751> <Mlp=113904.5751> <PB=87505.2> 
<DWph=1> <it=870> <et=555.75> <Mt= 1.55> <Spt=12.58> <nCl=210> <DB=-758848.4172> <Mlp=111249.9326> <PB=87505.2> 
<DWph=1> <it=880> <et=575.69> <Mt= 0.89> <Spt=19.04> <nCl=300> <DB=-294016.7480> <Mlp=109081.1219> <PB=87505.2> 
<DWph=1> <it=890> <et=598.21> <Mt= 1.65> <Spt=20.84> <nCl=300> <DB=-160933.7848> <Mlp=106465.0784> <PB=87505.2> 
<DWph=1> <it=900> <et=621.15> <Mt= 2.39> <Spt=20.54> <nCl=300> <DB=-134646.2566> <Mlp=100482.7542> <PB=87505.2> 
<DWph=1> <it=910> <et=645.94> <Mt= 2.58> <Spt=22.19> <nCl=277> <DB=-92044.8116> <Mlp=94455.3375> <PB=87505.2> 
<DWph=1> <it=920> <et=671.28> <Mt= 2.61> <Spt=22.71> <nCl=279> <DB=-71150.8645> <Mlp=88288.8580> <PB=87505.2> 
<DWph=1> <it=930> <et=698.16> <Mt= 3.25> <Spt=23.61> <nCl=276> <DB=-122789.1942> <Mlp=80204.5869> <PB=87505.2> 
<DWph=1> <it=940> <et=724.73> <Mt= 3.32> <Spt=23.24> <nCl=274> <DB=-53313.9676> <Mlp=72381.2722> <PB=87505.2> 
<DWph=1> <it=950> <et=752.60> <Mt= 3.42> <Spt=24.42> <nCl=268> <DB=-18581.4885> <Mlp=63516.9270> <PB=87505.2> 
<DWph=1> <it=960> <et=782.32> <Mt= 3.16> <Spt=26.54> <nCl=256> <DB=-64731.0647> <Mlp=56267.3386> <PB=87505.2> 
<DWph=1> <it=970> <et=814.27> <Mt= 2.88> <Spt=29.06> <nCl=287> <DB=-15144.7777> <Mlp=51413.3910> <PB=87505.2> 
<DWph=1> <it=980> <et=847.19> <Mt= 3.50> <Spt=29.40> <nCl=257> <DB= 2306.4000> <Mlp=45251.3758> <PB=87505.2> 
<DWph=1> <it=990> <et=880.17> <Mt= 3.26> <Spt=29.70> <nCl=235> <DB=22605.1326> <Mlp=43125.9690> <PB=87505.2> 
<DWph=1> <it=1000> <et=904.55> <Mt= 2.48> <Spt=21.74> <nCl=296> <DB=23422.6867> <Mlp=42400.9007> <PB=87505.2> 
<DWph=1> <it=1010> <et=926.01> <Mt= 2.16> <Spt=19.26> <nCl=261> <DB=36092.6088> <Mlp=41902.9272> <PB=87505.2> 
<DWph=1> <it=1020> <et=946.21> <Mt= 1.93> <Spt=18.23> <nCl=278> <DB=36816.7703> <Mlp=41557.1821> <PB=87505.2> 
<DWph=1> <it=1030> <et=963.92> <Mt= 1.68> <Spt=16.00> <nCl=238> <DB=38244.2728> <Mlp=41258.5815> <PB=87505.2> 
<DWph=1> <it=1040> <et=981.22> <Mt= 1.34> <Spt=15.92> <nCl=270> <DB=37481.9247> <Mlp=41115.4813> <PB=87505.2> 
<DWph=1> <it=1050> <et=998.56> <Mt= 1.05> <Spt=16.27> <nCl=262> <DB=37225.6431> <Mlp=41038.4628> <PB=87505.2> 
<DWph=1> <it=1060> <et=1016.22> <Mt= 0.98> <Spt=16.64> <nCl=253> <DB=39187.1042> <Mlp=40954.3673> <PB=87505.2> 
<DWph=1> <it=1070> <et=1033.65> <Mt= 0.67> <Spt=16.74> <nCl=224> <DB=39663.4283> <Mlp=40895.0998> <PB=87505.2> 
<DWph=1> <it=1080> <et=1051.22> <Mt= 0.42> <Spt=17.12> <nCl=203> <DB=40197.8283> <Mlp=40877.3134> <PB=87505.2> 
<DWph=1> <it=1090> <et=1068.80> <Mt= 0.36> <Spt=17.19> <nCl=180> <DB=38768.2167> <Mlp=40867.1277> <PB=87505.2> 
<DWph=1> <it=1100> <et=1089.79> <Mt= 0.26> <Spt=20.71> <nCl=118> <DB=39867.4701> <Mlp=40862.6394> <PB=87505.2> 
<DWph=1> <it=1107> <et=1105.93> <Mt= 0.13> <Spt=15.98> <nCl= 25> <DB=40862.5108> <Mlp=40862.5108> <PB=87505.2> 
<DWph=0> <it=1110> <et=1113.29> <Mt= 0.38> <Spt= 6.97> <nCl=443> <DB=38023.1666> <Mlp=40800.9082> <PB=87505.2> 
<DWph=0> <it=1120> <et=1137.37> <Mt= 0.44> <Spt=23.50> <nCl=397> <DB=40782.0202> <Mlp=40782.0202> <PB=87505.2> 
Reduced cost fixing for graph G_1... took 24.81 sec., 1342619 buck. arcs remain (97.9% from prev., 40.8% from max.)
Run enumeration... took 0.26 sec. and not succeeded.
ColGenEvalAlg final dual bound: 40782 (rounded: 40782)
----- Add fac. cuts : CAP(100), max.viol = 0.5, aver.viol = 0.303285, sep/add took 17.4136/0.0800919 sec. -----
6634 columns (6634 active), 100 dyn. constrs. (100 active), 1820 art. vars. (1820 active)
<DWph=2> <it=  4> <et=1183.98> <Mt= 0.46> <Spt= 3.16> <nCl= 35> <DB=40857.2641> <Mlp=40857.2641> <PB=87505.2> 
<DWph=1> <it= 10> <et=1195.40> <Mt= 0.44> <Spt=10.96> <nCl=178> <DB=37884.2105> <Mlp=40838.8359> <PB=87505.2> 
<DWph=1> <it= 20> <et=1213.02> <Mt= 0.37> <Spt=17.23> <nCl=150> <DB=40710.8117> <Mlp=40835.7463> <PB=87505.2> 
<DWph=1> <it= 24> <et=1221.21> <Mt= 0.06> <Spt= 8.11> <nCl= 16> <DB=40835.7241> <Mlp=40835.7241> <PB=87505.2> 
<DWph=0> <it= 30> <et=1235.00> <Mt= 0.14> <Spt=13.64> <nCl=166> <DB=40832.7141> <Mlp=40832.7141> <PB=87505.2> 
ColGenEvalAlg final dual bound: 40832.7 (rounded: 40832.7)
----- Add fac. cuts : CAP(99), max.viol = 0.377171, aver.viol = 0.148822, sep/add took 17.6433/0.0874268 sec. -----
7179 columns (7179 active), 199 dyn. constrs. (122 active), 1919 art. vars. (1842 active)
<DWph=2> <it=  7> <et=1258.85> <Mt= 0.66> <Spt= 5.10> <nCl= 36> <DB=40867.6064> <Mlp=40867.6064> <PB=87505.2> 
<DWph=1> <it= 10> <et=1264.02> <Mt= 0.18> <Spt= 4.99> <nCl= 90> <DB=37608.5719> <Mlp=40864.0541> <PB=87505.2> 
<DWph=1> <it= 20> <et=1281.65> <Mt= 0.66> <Spt=16.94> <nCl=192> <DB=39938.3747> <Mlp=40858.8677> <PB=87505.2> 
<DWph=1> <it= 29> <et=1303.57> <Mt= 0.18> <Spt=21.71> <nCl= 61> <DB=40858.8268> <Mlp=40858.8268> <PB=87505.2> 
<DWph=0> <it= 30> <et=1305.86> <Mt= 0.01> <Spt= 2.27> <nCl= 70> <DB=39353.8571> <Mlp=40858.8268> <PB=87505.2> 
<DWph=0> <it= 34> <et=1315.79> <Mt= 0.16> <Spt= 9.77> <nCl= 99> <DB=40858.1148> <Mlp=40858.1148> <PB=87505.2> 
ColGenEvalAlg final dual bound: 40858.1 (rounded: 40858.1)
----- Add fac. cuts : CAP(69), max.viol = 0.361484, aver.viol = 0.161238, sep/add took 22.6501/0.0786515 sec. -----
7727 columns (7727 active), 191 dyn. constrs. (115 active), 1988 art. vars. (1835 active)
<DWph=2> <it=  6> <et=1344.76> <Mt= 0.58> <Spt= 5.20> <nCl= 35> <DB=40871.0954> <Mlp=40871.0954> <PB=87505.2> 
<DWph=1> <it= 10> <et=1352.02> <Mt= 0.22> <Spt= 7.02> <nCl=113> <DB=38778.1792> <Mlp=40868.4548> <PB=87505.2> 
<DWph=1> <it= 19> <et=1371.43> <Mt= 0.24> <Spt=19.15> <nCl= 69> <DB=40868.1388> <Mlp=40868.1388> <PB=87505.2> 
<DWph=0> <it= 20> <et=1373.74> <Mt= 0.01> <Spt= 2.29> <nCl= 20> <DB=40562.7543> <Mlp=40868.1388> <PB=87505.2> 
<DWph=0> <it= 22> <et=1381.98> <Mt= 0.05> <Spt= 8.19> <nCl= 21> <DB=40868.1340> <Mlp=40868.1340> <PB=87505.2> 
ColGenEvalAlg final dual bound: 40868.1 (rounded: 40868.1)
----- Add fac. cuts : CAP(80) R1C(153), max.viol = 0.5, aver.viol = 0.276465, sep/add took 26.4118/0.569745 sec. -----
7985 columns (7985 active), 348 dyn. constrs. (287 active), 2221 art. vars. (2007 active)
<DWph=2> <it= 10> <et=1417.54> <Mt= 2.57> <Spt= 5.56> <nCl=118> <DB=40908.1075> <Mlp=41132.1235> <PB=87505.2> 
<DWph=2> <it= 19> <et=1425.66> <Mt= 0.47> <Spt= 7.62> <nCl= 74> <DB=41126.5644> <Mlp=41126.5644> <PB=87505.2> 
<DWph=1> <it= 20> <et=1428.19> <Mt= 0.01> <Spt= 2.52> <nCl= 30> <DB=29159.4731> <Mlp=41126.5644> <PB=87505.2> 
<DWph=1> <it= 30> <et=1457.88> <Mt= 2.39> <Spt=27.27> <nCl=267> <DB=38989.8372> <Mlp=41038.6147> <PB=87505.2> 
<DWph=1> <it= 40> <et=1485.83> <Mt= 0.90> <Spt=27.02> <nCl=241> <DB=40621.7118> <Mlp=41030.6487> <PB=87505.2> 
<DWph=1> <it= 50> <et=1514.24> <Mt= 0.35> <Spt=28.02> <nCl= 93> <DB=40971.3173> <Mlp=41030.0470> <PB=87505.2> 
<DWph=1> <it= 58> <et=1548.30> <Mt= 0.17> <Spt=33.87> <nCl= 28> <DB=41029.9728> <Mlp=41029.9728> <PB=87505.2> 
<DWph=0> <it= 60> <et=1556.67> <Mt= 0.34> <Spt= 8.02> <nCl=253> <DB=39730.7874> <Mlp=41021.5000> <PB=87505.2> 
<DWph=0> <it= 68> <et=1590.04> <Mt= 0.37> <Spt=32.97> <nCl=152> <DB=41018.0432> <Mlp=41018.0433> <PB=87505.2> 
ColGenEvalAlg final dual bound: 41018 (rounded: 41018)
----- Add fac. cuts : CAP(82) R1C(152), max.viol = 0.467039, aver.viol = 0.231534, sep/add took 22.0115/0.670863 sec. -----
9241 columns (9241 active), 521 dyn. constrs. (341 active), 2455 art. vars. (2061 active)
<DWph=2> <it=  7> <et=1621.79> <Mt= 2.01> <Spt= 6.59> <nCl= 45> <DB=41179.6181> <Mlp=41179.6181> <PB=87505.2> 
<DWph=1> <it= 10> <et=1630.74> <Mt= 0.78> <Spt= 8.16> <nCl= 90> <DB=37529.1165> <Mlp=41147.1860> <PB=87505.2> 
<DWph=1> <it= 20> <et=1662.33> <Mt= 1.82> <Spt=29.73> <nCl=259> <DB=40638.4024> <Mlp=41126.5919> <PB=87505.2> 
<DWph=1> <it= 30> <et=1690.75> <Mt= 0.48> <Spt=27.91> <nCl= 94> <DB=40332.1236> <Mlp=41125.1290> <PB=87505.2> 
<DWph=1> <it= 36> <et=1717.91> <Mt= 0.34> <Spt=26.79> <nCl= 38> <DB=41122.3643> <Mlp=41122.3643> <PB=87505.2> 
<DWph=0> <it= 40> <et=1732.55> <Mt= 0.61> <Spt=13.98> <nCl=452> <DB=40791.8170> <Mlp=41113.4125> <PB=87505.2> 
<DWph=0> <it= 44> <et=1754.10> <Mt= 0.13> <Spt=21.41> <nCl= 47> <DB=41113.3533> <Mlp=41113.3533> <PB=87505.2> 
ColGenEvalAlg final dual bound: 41113.4 (rounded: 41113.4)
----- Add fac. cuts : CAP(51) R1C(150), max.viol = 0.5, aver.viol = 0.201641, sep/add took 25.3539/0.560669 sec. -----
10237 columns (6843 active), 542 dyn. constrs. (364 active), 2656 art. vars. (2084 active)
<DWph=2> <it=  9> <et=1790.02> <Mt= 1.91> <Spt= 7.61> <nCl= 30> <DB=41197.0823> <Mlp=41197.0823> <PB=87505.2> 
<DWph=1> <it= 10> <et=1792.92> <Mt= 0.01> <Spt= 2.88> <nCl= 30> <DB=34010.6806> <Mlp=41197.0823> <PB=87505.2> 
<DWph=1> <it= 20> <et=1823.62> <Mt= 1.70> <Spt=28.98> <nCl=195> <DB=41021.7882> <Mlp=41173.1401> <PB=87505.2> 
<DWph=1> <it= 28> <et=1855.39> <Mt= 0.29> <Spt=31.45> <nCl= 41> <DB=41172.9540> <Mlp=41172.9540> <PB=87505.2> 
<DWph=0> <it= 30> <et=1863.95> <Mt= 0.36> <Spt= 8.19> <nCl=227> <DB=39659.0349> <Mlp=41166.8845> <PB=87505.2> 
<DWph=0> <it= 34> <et=1882.68> <Mt= 0.28> <Spt=18.43> <nCl= 86> <DB=41166.1883> <Mlp=41166.1883> <PB=87505.2> 
ColGenEvalAlg final dual bound: 41166.2 (rounded: 41166.2)
----- Add fac. cuts : CAP(47) R1C(251), max.viol = 0.45144, aver.viol = 0.192318, sep/add took 32.2142/0.820735 sec. -----
10846 columns (7452 active), 662 dyn. constrs. (532 active), 2954 art. vars. (2252 active)
<DWph=2> <it=  6> <et=1925.71> <Mt= 2.67> <Spt= 6.78> <nCl= 49> <DB=41272.5248> <Mlp=41272.5248> <PB=87505.2> 
<DWph=1> <it= 10> <et=1939.30> <Mt= 1.43> <Spt=12.14> <nCl=120> <DB=37166.0434> <Mlp=41251.2300> <PB=87505.2> 
<DWph=1> <it= 20> <et=1970.79> <Mt= 1.92> <Spt=29.53> <nCl=210> <DB=40019.6306> <Mlp=41235.9774> <PB=87505.2> 
<DWph=1> <it= 29> <et=2000.12> <Mt= 0.40> <Spt=28.89> <nCl= 49> <DB=41235.4275> <Mlp=41235.4275> <PB=87505.2> 
<DWph=0> <it= 30> <et=2005.00> <Mt= 0.02> <Spt= 4.86> <nCl=149> <DB=38431.4461> <Mlp=41235.4275> <PB=87505.2> 
<DWph=0> <it= 37> <et=2040.17> <Mt= 0.98> <Spt=34.16> <nCl=245> <DB=41226.5804> <Mlp=41226.5804> <PB=87505.2> 
ColGenEvalAlg final dual bound: 41226.6 (rounded: 41226.6)
----- Add fac. cuts : CAP(44) R1C(350), max.viol = 0.396774, aver.viol = 0.192592, sep/add took 51.1097/1.19023 sec. -----
11668 columns (8274 active), 926 dyn. constrs. (691 active), 3348 art. vars. (2411 active)
<DWph=2> <it= 10> <et=2107.33> <Mt= 4.86> <Spt= 9.40> <nCl= 81> <DB=41078.0742> <Mlp=41310.3901> <PB=87505.2> 
<DWph=2> <it= 14> <et=2110.52> <Mt= 0.16> <Spt= 3.02> <nCl=  5> <DB=41310.3486> <Mlp=41310.3486> <PB=87505.2> 
<DWph=1> <it= 20> <et=2131.66> <Mt= 2.46> <Spt=18.66> <nCl=180> <DB=39133.4999> <Mlp=41285.4747> <PB=87505.2> 
<DWph=1> <it= 30> <et=2167.41> <Mt= 1.48> <Spt=34.22> <nCl=143> <DB=41251.5801> <Mlp=41282.5877> <PB=87505.2> 
<DWph=1> <it= 34> <et=2189.20> <Mt= 0.12> <Spt=21.65> <nCl=  6> <DB=41282.5742> <Mlp=41282.5742> <PB=87505.2> 
<DWph=0> <it= 40> <et=2218.77> <Mt= 1.35> <Spt=28.19> <nCl=341> <DB=41166.4700> <Mlp=41276.3252> <PB=87505.2> 
<DWph=0> <it= 44> <et=2246.21> <Mt= 0.16> <Spt=27.26> <nCl= 25> <DB=41276.3190> <Mlp=41276.3190> <PB=87505.2> 
Bucket graph for G_1 is regenerated as bucket steps were adjusted for 861 vertices
taox142 commented 8 months ago

Anyone had the same issue before? It it quite tricky as this issue is not viewed as an error or exception. Otherwise, it can be handled by "try except" logic in python.

rrsadykov commented 8 months ago

Dear @taox142, Sorry for a late reply. Probably there is a bug in the code. It would be tricky to debug as it appears after 2000 seconds of runtime. What is the smallest instance for which you encountered this issue? I would need a JSON file for the this smallest instance. One workaround is deactivate dynamic bucket graph regeneration through advanced parameterisation (by specifying a config_file). I need my other computer to give the exact parameter to change. I will do it later.

taox142 commented 8 months ago

Dear Ruslan (@rrsadykov),

Thank you for looking into this issue. I've attached a smaller case with 286 nodes. This instance will trigger the issue very quickly.

Thanks again. And would love to learn more about the workaround solution.

vrp_debug.json

rrsadykov commented 8 months ago

I have managed to reproduce the bug, thank you for spotting it! I will debug when I have time.

Meanwhile, bc.cfg.txt is the configuration file to give to VRPSolverEasy, through config_file property to workaround the bug.

rrsadykov commented 8 months ago

I have resolved bug, it is tolerance-related, but I do not know how long it takes to "propagate" this code change to VRPSolverEasy. Meanwhile, I think you can avoid the bug if you round your time window bounds with precision less than 6 (number of digits after the decimal point).

@najibprog, I have updated the RCSP solver code to version 0.6.11. Does it take long to update BaPCod binaries with it? We should also include this advise in the documentation to avoid using very high precision floating point numbers with VRPSolverEasy.

taox142 commented 8 months ago

Hi Ruslan (@rrsadykov),

Thank you for your help. Changing the config does solve the issue.

But as for the second solution you suggested, it didn't work for me. I tried to round the time window bounds to 5,4,3 and even 1 digits after the decimal point, but none of them solve the issue.

Below please find the model json file where I rounded the number to 3 digits.

vrp_precision_fixed.json

Regards, Tao

taox142 commented 8 months ago

I have managed to reproduce the bug, thank you for spotting it! I will debug when I have time.

Meanwhile, bc.cfg.txt is the configuration file to give to VRPSolverEasy, through config_file property to workaround the bug.

One more question, what feature do we lose when switching off the dynamic adjustment bucket steps? Will the solver be slower when we do that?

rrsadykov commented 8 months ago

But as for the second solution you suggested, it didn't work for me. I tried to round the time window bounds to 5,4,3 and even 1 digits after the decimal point, but none of them solve the issue.

Below please find the model json file where I rounded the number to 3 digits.

Thank you for testing the rounding and for the JSON file. I will investigate this issue further.

One more question, what feature do we lose when switching off the dynamic adjustment bucket steps? Will the solver be slower when we do that?

We can lose some performance for some instances but it's not dramatic. You can read about this technique in this paper: https://inria.hal.science/hal-02378624/document, search for "dynamic adjustment of parameter ξ", Figure 6(a) gives the performance profile for this technique. Parameter RCSPnumberOfBucketsPerVertex in the config file corresponds to ξ.

taox142 commented 8 months ago

We can lose some performance for some instances but it's not dramatic. You can read about this technique in this paper: https://inria.hal.science/hal-02378624/document, search for "dynamic adjustment of parameter ξ", Figure 6(a) gives the performance profile for this technique. Parameter RCSPnumberOfBucketsPerVertex in the config file corresponds to ξ.

Thank you. I will check out the paper to learn more details.

rrsadykov commented 8 months ago

I have checked. I seems this bug cannot be workaround by modifying the data, only by switching off dynamic bucket graph regeneration in the config file. The bug is fixed in the code, but I do not know when the new version will be released.

najibprog commented 8 months ago

Hi @rrsadykov thanks for fixing the bug in RCSP solver, the new version can be published as soon as I return, i.e. in the week of December 4st.

Best regards, Najib

taox142 commented 7 months ago

Hi Ruslan (@rrsadykov),

Need your help again. I ran into this instance. If I run without the bc.cfg.txt, it will return a feasible solution, but if I set parameter with the config file, it generates a solution which violates the vehicle capacity condition.

Please see the instance attached. It is not large that you should be able to reproduce the issue in seconds. capacity_violation.json

Thanks again, Tao

rrsadykov commented 7 months ago

Dear @taox142,

I was not able for now to reproduce this issue. Can you please add DEFAULTPRINTLEVEL = 0 to the config file, run again and give the output of VRPSolverEasy. The infeasibility is detected by VRPSolverEasy or it is you who detect it? If you have infeasible solution, can you give it too.

@najibprog is back to office next week so I think VRPSolverEasy will be updated very soon to the new version which addresses the initial bug.

Ruslan

taox142 commented 7 months ago

Dear @rrsadykov ,

Sorry for the late reply. Let me clarify the issue.

The model is the same. But running with and without the config file will generate two different solutions. And I checked, the one generated with the config file violates the capacity constraints.

Running with config.txt, model output is with config file output.txt. Cost = 48688.6.

Running without the config file(using the default solver parameters), model output is without config file output.txt. Cost = 49188.2.

In the 48688.6 solution, I used the following code to check the capacity feasibility: for index, route in enumerate(model.solution.routes): print(f"Route No.: {index}.") print(f"Ids : {route.point_ids}.") print(f"Points demand: {[model.points[point].demand for point in route.point_ids]}," f"route total demand = {sum([model.points[point].demand for point in route.point_ids])}.") print(f"Load : {route.cap_consumption}.\n")

And I found a few routes with total demand larger than 200 (which is my vehicle capacity). For example: Route No.: 68. Ids : [0, 176, 177, 178, 179, 180, 169, 0]. Points demand: [0, 60, 60, 20, 20, 30, 30, 0],route total demand = 220. Load : [0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0].

Also notice the cap_consumption variable are all 0, which, based on my experiences running other instances, should be demand of the nodes in the route.

Great that the new version will come out soon. But would really appreciate it if you can help look into this issue. It has been a great learning experience for me.

Thanks, Tao

najibprog commented 7 months ago

Dear Tao,

Thank you for taking the time to test our package. We have released a new version of Bapcod. So you can fill out the form here to get the new package binaries. I hope this version will solve your issue.

Best regards, Najib

taox142 commented 7 months ago

Dear Najib,

Thank you for releasing the new version. I can't wait to test it out. I will close the issue later if the new version solves this issue.

Best, Tao

taox142 commented 7 months ago

Dear Najib and Ruslan,

I have tested the new version and comfirm that coping over the new libbapcod-shared.so file to VRPSolverEasy does solve the original issue.

I will close this issue now. Thank you both for your help.

Best regards, Tao