No feasible solution obtained with Coluna

[vulcanyao]

No feasible solution
I am using the Coluna to solve a mixed integer programming, the code doesn't return a feasible solution during the solution process, and returns an error code: ERROR: LoadError: Unexpected variable state during column insertion.
To Reproduce
Main function: BVRP-Iterative.jl
Input data: RealMap_11_test.mat

Expected behavior
A clear and concise description of what you expected to happen.
If possible, copy the error message with the stacktrace.

Environment (please complete the following information):

• Julia version [e.g. 1.2]
• OS: [e.g. Linux, Windows, MacOs]

Additional context
Add any other context about the problem here.

[guimarqu]

BlockDecomposition will now warn the user in case of incorrect decomposition -> atoptima/BlockDecomposition.jl#79

[vulcanyao]

Hi, the following error occurred when running the code with lasted Coluna and BlockDecomposition.

Coluna
Version 0.3.12 | 2022-02-17 | https://github.com/atoptima/Coluna.jl

---

**** BaB tree root node
**** Local DB = -Inf, global bounds : [ -Inf , Inf ], time = 0.01 sec.

---

┌ Warning: Solver has no result to show.
└ @ Coluna.Algorithm ~/.julia/packages/Coluna/SvqHX/src/Algorithm/basic/solvelpform.jl:73
┌ Warning: Solver has no result to show.
└ @ Coluna.Algorithm ~/.julia/packages/Coluna/SvqHX/src/Algorithm/basic/solvelpform.jl:73
┌ Warning: Solver has no result to show.
└ @ Coluna.Algorithm ~/.julia/packages/Coluna/SvqHX/src/Algorithm/basic/solvelpform.jl:73
┌ Warning: Solver has no result to show.
└ @ Coluna.Algorithm ~/.julia/packages/Coluna/SvqHX/src/Algorithm/basic/solvelpform.jl:73
┌ Warning: Solver has no result to show.
└ @ Coluna.Algorithm ~/.julia/packages/Coluna/SvqHX/src/Algorithm/basic/solvelpform.jl:73
<it= 1> <et= 0.02> <mst= 0.00> <sp= 0.01> <cols= 0> <al= 0.00> <DB= 0.0000> <mlp=50000.0000> <PB=Inf>
[ Info: No new column generated by the pricing problems.
[ Info: Running Restricted Master IP heuristic
┌ Warning: Solver has no result to show.
└ @ Coluna.Algorithm ~/.julia/packages/Coluna/SvqHX/src/Algorithm/basic/solvelpform.jl:73
[ Info: No branching candidates found. No children will be generated.
──────────────────────────────────────────────────────────────────────────────────────
Time Allocations
─────────────────────── ────────────────────────
Tot / % measured: 34.5s / 0.1% 392MiB / 1.1%

Section ncalls time %tot avg alloc %tot avg
──────────────────────────────────────────────────────────────────────────────────────
Coluna 1 25.2ms 100.0% 25.2ms 4.13MiB 100.0% 4.13MiB
SolveLpForm 1 2.52ms 10.0% 2.52ms 907KiB 21.4% 907KiB
Update reduced costs 1 68.0μs 0.3% 68.0μs 112KiB 2.6% 112KiB
Store records 1 16.2μs 0.1% 16.2μs 896B 0.0% 896B
Getting primal solution 1 14.7μs 0.1% 14.7μs 336B 0.0% 336B
Cleanup columns 1 9.09μs 0.0% 9.09μs 208B 0.0% 208B
Restore/remove records 1 6.77μs 0.0% 6.77μs 0.00B 0.0% 0.00B
Update Lagrangian bound 1 2.07μs 0.0% 2.07μs 128B 0.0% 128B
Smoothing update 1 1.32μs 0.0% 1.32μs 80.0B 0.0% 80.0B
──────────────────────────────────────────────────────────────────────────────────────
[ Info: Terminated
[ Info: Primal bound: Inf
[ Info: Dual bound: Inf
ERROR: LoadError: Invalid result index.
Stacktrace:
[1] error(::String) at ./error.jl:33
[2] get(::Coluna.Optimizer, ::MathOptInterface.VariablePrimal, ::MathOptInterface.VariableIndex) at /Users/vulcanyao/.julia/packages/Coluna/SvqHX/src/MOIwrapper.jl:883
[3] get(::MathOptInterface.Bridges.LazyBridgeOptimizer{Coluna.Optimizer}, ::MathOptInterface.VariablePrimal, ::MathOptInterface.VariableIndex) at /Users/vulcanyao/.julia/packages/MathOptInterface/YDdD3/src/Bridges/bridge_optimizer.jl:1039
[4] get(::MathOptInterface.Utilities.CachingOptimizer{MathOptInterface.AbstractOptimizer,MathOptInterface.Utilities.UniversalFallback{MathOptInterface.Utilities.GenericModel{Float64,MathOptInterface.Utilities.ModelFunctionConstraints{Float64}}}}, ::MathOptInterface.VariablePrimal, ::MathOptInterface.VariableIndex) at /Users/vulcanyao/.julia/packages/MathOptInterface/YDdD3/src/Utilities/cachingoptimizer.jl:757
[5] _moi_get_result(::MathOptInterface.Utilities.CachingOptimizer{MathOptInterface.AbstractOptimizer,MathOptInterface.Utilities.UniversalFallback{MathOptInterface.Utilities.GenericModel{Float64,MathOptInterface.Utilities.ModelFunctionConstraints{Float64}}}}, ::MathOptInterface.VariablePrimal, ::Vararg{Any,N} where N) at /Users/vulcanyao/.julia/packages/JuMP/klrjG/src/JuMP.jl:1199
[6] get(::Model, ::MathOptInterface.VariablePrimal, ::VariableRef) at /Users/vulcanyao/.julia/packages/JuMP/klrjG/src/JuMP.jl:1232
[7] value(::VariableRef; result::Int64) at /Users/vulcanyao/.julia/packages/JuMP/klrjG/src/variables.jl:943
[8] #40 at /Users/vulcanyao/.julia/packages/JuMP/klrjG/src/aff_expr.jl:494 [inlined]
[9] value(::GenericAffExpr{Float64,VariableRef}, ::JuMP.var"#40#41"{Int64}) at /Users/vulcanyao/.julia/packages/JuMP/klrjG/src/aff_expr.jl:280
[10] #value#39 at /Users/vulcanyao/.julia/packages/JuMP/klrjG/src/aff_expr.jl:494 [inlined]
[11] value(::GenericAffExpr{Float64,VariableRef}) at /Users/vulcanyao/.julia/packages/JuMP/klrjG/src/aff_expr.jl:494
[12] BVRP_BDD(::Int64, ::Int64, ::Int64, ::Float64, ::Float64, ::Float64, ::Int64) at /Users/vulcanyao/OneDrive - 南方科技大学/PDF Expert/Research Yao/code_VRPPD/[J3]Bilevel EVRP with time flexibility/J3-V1/BVRP-Iterative.jl:136
[13] main() at /Users/vulcanyao/OneDrive - 南方科技大学/PDF Expert/Research Yao/code_VRPPD/[J3]Bilevel EVRP with time flexibility/J3-V1/BVRP-Iterative.jl:171
[14] top-level scope at /Users/vulcanyao/OneDrive - 南方科技大学/PDF Expert/Research Yao/code_VRPPD/[J3]Bilevel EVRP with time flexibility/J3-V1/BVRP-Iterative.jl:186
in expression starting at /Users/vulcanyao/OneDrive - 南方科技大学/PDF Expert/Research Yao/code_VRPPD/[J3]Bilevel EVRP with time flexibility/J3-V1/BVRP-Iterative.jl:186

[guimarqu]

Hey, I get this error

ERROR: LoadError: BlockDecomposition.MasterVarInDwSp(tau_var[1], c3[2,1,1] : -100 x[1,2,1] + tau_var[1] - tau_var[2] ≥ -94.79524)

[vulcanyao]

Does it mean that the constraints c3 is infeasible? In fact, the number of right hand side should be a nonnegative constant, which denotes the pickup or delivery time.

[guimarqu]

Does it mean that the constraints c3 is infeasible? In fact, the number of right hand side should be a nonnegative constant, which denotes the pickup or delivery time.

No it just means that the constraint c3 that belongs to a subproblem has master variable which is not possible. So the decomposition is incorrect. This is the error we fixed by replacing k in K with k in 1:nb_vehicles.

[guimarqu]

I solved the your formulation with Gurobi, retrieved the optimal solution, and I decided to fix the value of non-zero x variables in the formulation.
To do so, I added the following constraints:

    @constraint(BVRP, g0[K[1]], x[1,1,7] == 1)
    @constraint(BVRP, g1[K[1]], x[1,7,11] == 1)
    @constraint(BVRP, g2[K[2]], x[2,1,6] == 1)
    @constraint(BVRP, g3[K[2]], x[2,6,8] == 1)
    @constraint(BVRP, g4[K[2]], x[2,8,11] == 1)
    @constraint(BVRP, g5[K[3]], x[3,1,11] == 1)
    @constraint(BVRP, g6[K[4]], x[4,1,11] == 1)
    @constraint(BVRP, g7[K[5]], x[5,1,11] == 1)

The good news is that Coluna finds the same optimal solution as Gurobi (968.104 with Coluna).
This solution is found at the second column generation iteration at the root node we gave a lot of information to the subproblems to generate good columns):

<it= 1> <et=13.13> <mst= 2.04> <sp= 2.30> <cols=10> <al= 0.00> <DB=-2256.9378> <mlp=50000.0000> <PB=Inf>
<it= 2> <et=13.69> <mst= 0.03> <sp= 0.02> <cols= 5> <al= 0.00> <DB=-1553.7337> <mlp= 968.1050> <PB=968.1050>

The bad news is that the linear relaxation of the master is not good.
Even with these x-variables fixed, the dual bound at the root node is still 913.935. It means that the root gap is about 5.9% which is quite large.

Two ways of improvement:

1. if your subproblems are identical, you should take a look to the following section: https://atoptima.github.io/Coluna.jl/latest/man/decomposition/#Dantzig-Wolfe-with-identical-subproblems-(alpha)
   Multiplicity breaks symmetry and therefore speeds up the branch-cut-price.

2. valid inequalities to strengthen your formulation.
   I started to write a section in the manual (https://atoptima.github.io/Coluna.jl/latest/start/cuts/). The example should be clarified but syntax is here.