pnavaro
commented
4 months ago poke @jeremyomer @aysnrarsln
Closed WPettersson closed 3 months ago
pnavaro
commented
4 months ago poke @jeremyomer @aysnrarsln
pnavaro
commented
4 months ago I added an example to reproduce the error
pnavaro
commented
3 months ago related to #16
WPettersson
commented
2 months ago Sorry it took time to get back to this, but I think this might still be somewhat broken. With current master:
% ~/opt/julia-1.10.1/bin/julia examples/solve_with_bppicef.jl ✭ [13:34:06]
********************************************************************************
Solve 00036-00000001 with (K,L) = (3,2) using branch-and-price
- master model uses PIEF = true
- time limit is 7200.0 seconds
********************************************************************************
----------------------------------------------------------
Parse the input file
----------------------------------------------------------
the instance is not vertex weighted!
----------------------------------------------------------
Preprocessing: compute the graph copies
----------------------------------------------------------
----------------------------------------------------------
Solve with branch-and-price
----------------------------------------------------------
Initialize column pool with 2-cycles when using PIEF
- number of initial columns: 37
Processing node 1
Iteration 1:
- current master value: 9.0
- nb of cycles added = 0
Node relaxation is solved to optimality
- node upper bound is 9.0, tree lower bound is 0.0
The number of columns increased:
search for a feasible solution at node 1
- number of columns in master IP: 37
Running HiGHS 1.6.0: Copyright (c) 2023 HiGHS under MIT licence terms
Presolving model
16 rows, 37 cols, 74 nonzeros
16 rows, 37 cols, 74 nonzeros
Objective function is integral with scale 0.941176
Solving MIP model with:
16 rows
37 cols (37 binary, 0 integer, 0 implied int., 0 continuous)
74 nonzeros
Nodes | B&B Tree | Objective Bounds | Dynamic Constraints | Work
Proc. InQueue | Leaves Expl. | BestBound BestSol Gap | Cuts InLp Confl. | LpIters Time
0 0 0 0.00% 11.6875 -inf inf 0 0 0 0 0.0s
T 0 0 0 0.00% 11.6875 9.5625 22.22% 0 0 0 12 0.0s
Solving report
Status Optimal
Primal bound 9.5625
Dual bound 9.5625
Gap 0% (tolerance: 0.01%)
Solution status feasible
9.5625 (objective)
0 (bound viol.)
0 (int. viol.)
0 (row viol.)
Timing 0.00 (total)
0.00 (presolve)
0.00 (postsolve)
Nodes 1
LP iterations 12 (total)
0 (strong br.)
0 (separation)
0 (heuristics)
New incumbent found with value 9.0 found by solving the IP with every column of the pool
Termination status : OPTIMAL
After processing root node: LB = 9.0, UB = 9.0
The node is either infeasible or pruned by bound
LB = 9.0, UB = 9.0
----------------------------------------------------------
The execution of the branch-and-price is complete
- the solution is optimal
- best solution found: value 9.0 with gap 0.0 %
----------------------------------------------------------
Numbers of cycles per cycle length
- k = 2: 7 cycles
In total, 14 pairs are covered by cycles
ERROR: LoadError: An edge of the solution is not in the KEP graph
Stacktrace:
[1] error(s::String)
@ Base ./error.jl:35
[2] print_and_check_solution(cycles::Vector{Vector{Int64}}, chains::Vector{Vector{Int64}}, instance::KidneyExchange.Instance, verbose::Bool)
@ KidneyExchange ~/.julia/packages/KidneyExchange/07zMq/src/utils.jl:75
[3] solve_with_BP(filename::String, K::Int64, L::Int64, bp_params::BP_params, timer::TimerOutput, time_limit::Float64, unweight::Bool)
@ KidneyExchange ~/.julia/packages/KidneyExchange/07zMq/src/branch&price/branch_and_price.jl:51
[4] solve_with_BP(filename::String, K::Int64, L::Int64, bp_params::BP_params, timer::TimerOutput, time_limit::Float64)
@ KidneyExchange ~/.julia/packages/KidneyExchange/07zMq/src/branch&price/branch_and_price.jl:29
[5] top-level scope
@ ~/src/git/KidneyExchange.jl/examples/solve_with_bppicef.jl:38
in expression starting at /home/wpette/src/git/KidneyExchange.jl/examples/solve_with_bppicef.jl:38Strange it works for me on branch master
$ julia --project examples/solve_with_bppicef.jl
********************************************************************************
Solve 00036-00000001 with (K,L) = (3,2) using branch-and-price
- master model uses PIEF = true
- time limit is 7200.0 seconds
********************************************************************************
----------------------------------------------------------
Parse the input file
----------------------------------------------------------
----------------------------------------------------------
Preprocessing: compute the graph copies
----------------------------------------------------------
----------------------------------------------------------
Solve with branch-and-price
----------------------------------------------------------
Initialize column pool with 2-cycles when using PIEF
- number of initial columns: 2
Processing node 1
Iteration 1:
- current master value: 4.0
- nb of cycles added = 0
Node relaxation is solved to optimality
- node upper bound is 4.0, tree lower bound is 0.0
The number of columns increased:
search for a feasible solution at node 1
- number of columns in master IP: 2
Running HiGHS 1.7.0 (git hash: 50670fd4c): Copyright (c) 2024 HiGHS under MIT licence terms
Coefficient ranges:
Matrix [1e+00, 1e+00]
Cost [1e+00, 2e+00]
Bound [1e+00, 1e+00]
RHS [1e+00, 1e+00]
Presolving model
0 rows, 0 cols, 0 nonzeros 0s
0 rows, 0 cols, 0 nonzeros 0s
Presolve: Optimal
Solving report
Status Optimal
Primal bound 4.25
Dual bound 4.25
Gap 0% (tolerance: 0.01%)
Solution status feasible
4.25 (objective)
0 (bound viol.)
0 (int. viol.)
0 (row viol.)
Timing 0.00 (total)
0.00 (presolve)
0.00 (postsolve)
Nodes 0
LP iterations 0 (total)
0 (strong br.)
0 (separation)
0 (heuristics)
New incumbent found with value 4.0 found by solving the IP with every column of the pool
Termination status : OPTIMAL
After processing root node: LB = 4.0, UB = 4.0
The node is either infeasible or pruned by bound
LB = 4.0, UB = 4.0
----------------------------------------------------------
The execution of the branch-and-price is complete
- the solution is optimal
- best solution found: value 4.0 with gap 0.0 %
----------------------------------------------------------
Numbers of cycles per cycle length
- k = 2: 2 cycles
In total, 4 pairs are covered by cycles
The computed cost of the solution is 4.0
─────────────────────────────────────────────────────────────────────────────
Time Allocations
─────────────────────── ────────────────────────
Tot / % measured: 5.07s / 97.8% 306MiB / 98.7%
Section ncalls time %tot avg alloc %tot avg
─────────────────────────────────────────────────────────────────────────────
B&P 1 3.60s 72.6% 3.60s 255MiB 84.4% 255MiB
Process_Node 1 1.53s 30.9% 1.53s 124MiB 40.9% 124MiB
Bellman-Ford 2 617ms 12.4% 308ms 30.1MiB 10.0% 15.0MiB
opt_master 1 130ms 2.6% 130ms 12.8MiB 4.2% 12.8MiB
IP_master 1 4.43ms 0.1% 4.43ms 113KiB 0.0% 113KiB
Parser 1 781ms 15.8% 781ms 13.5MiB 4.5% 13.5MiB
Preprocessing 1 577ms 11.6% 577ms 33.7MiB 11.1% 33.7MiB
─────────────────────────────────────────────────────────────────────────────Yup, sorry that was my bad. I'm still getting my head around Julia, and Julia wasn't using the new version of the code but an old version still. Sorry!
pnavaro
commented
2 months ago No worries William, I prefer this kind of issue 😄
Assuming that .wmd/.dat file loading from the branch 16-file-format-description-seems-off is incorporated, I am getting the following error when running
julia ../../KEPTestBPPICEF.jl 00036-00000001 3 2I include full output when using Gurobi as a solver below, but the same happens if I use HiGHS so I'm guessing it's not a solver issue. Also I can confirm that KEPTestBP.jl does not exhibit this behaviour.
Full output