search

atoptima / Coluna.jl

Branch-and-Price-and-Cut in Julia
https://www.atoptima.com
Other
193 stars 43 forks source link

Dependency on input parameter values #257

Closed persiflex closed 4 years ago

persiflex commented 4 years ago

Describe the bug I found the following issue: Depending on the values of some input parameters, Coluna is able to either find the same value as plain JuMP or not.

To Reproduce This test model is about the minimization of investment costs of machines: test_problem_vs1.txt When "decompose" is true (l. 10f.) and the first provided values for cost are taken (l. 83ff.), Coluna does not find the solution. When "decompose" is false (i.e. plain JuMP used) or the second pair of cost values is taken, the model can be solved.

Expected behavior Coluna should solve the problem for any value, as JuMP does. Not sure if it's related but the log returns after already the first iteration "CG Algo has converged" while I find it's usually at least two iterations. Also mlp, db and pb have all different values:

Coluna Version 0.2 - https://github.com/atoptima/Coluna.jl [ Info: Coluna ready to start. [ Info: Coluna.Params(10000, 100000, 1.0e-6, 6, Inf, -Inf, false, Coluna.Algorithm.GlobalStrategy(Coluna.Algorithm.SimpleBnP(Coluna.Algorithm.ColumnGeneration(1000, 1.0e-5, 1), Coluna.Algorithm.MasterIpHeuristic()), Coluna.Algorithm.BranchingStrategy(Coluna.Algorithm.BranchingPhase[], Coluna.Algorithm.MostFractionalCriterion, Coluna.Algorithm.AbstractBranchingRule[Coluna.Algorithm.VarBranchingRule(1.0, 1.0)]), Coluna.Algorithm.DepthFirst())) [ Info: Setting up node 1 before apply

1 open nodes. Treating node 1. Current best known bounds : [ -Inf , Inf ] Elapsed time: 2.57 seconds Subtree dual bound is -Inf

[ Info: Setting up Reformulation before applying or algorithm. [ Info: Setting up Reformulation before applying or algorithm. [ Info: Formulation is up-to-date, aborting preparation. [ LogLevel(1): Column Generation Algorithm has converged. [ Info: Recording reformulation state after solving node. [ Info: Recording master info. [ Info: Recording sp 7 info. [ Info: Recording sp 4 info. [ Info: Recording sp 9 info. [ Info: Recording sp 10 info. [ Info: Recording sp 2 info. [ Info: Recording sp 3 info. [ Info: Recording sp 11 info. [ Info: Recording sp 5 info. [ Info: Recording sp 8 info. [ Info: Recording sp 6 info. [ LogLevel(1): Phase one determines infeasibility. [ Info: Recording reformulation state after solving node. [ Info: Recording master info. [ Info: Recording sp 7 info. [ Info: Recording sp 4 info. [ Info: Recording sp 9 info. [ Info: Recording sp 10 info. [ Info: Recording sp 2 info. [ Info: Recording sp 3 info. [ Info: Recording sp 11 info. [ Info: Recording sp 5 info. [ Info: Recording sp 8 info. [ Info: Recording sp 6 info.

Node 1 is treated Generated 0 children nodes Node bounds after treatment : [ -Inf , Inf ]

[ Info: Updating tree. ─────────────────────────────────────────────────────────────────────────────────────────────────────────────── Time Allocations
────────────────────── ─────────────────────── Tot / % measured: 9627s / 0.19% 3.46GiB / 18.4%

Section ncalls time %tot avg alloc %tot avg ─────────────────────────────────────────────────────────────────────────────────────────────────────────────── Coluna 1 18.4s 100% 18.4s 653MiB 100% 653MiB Coluna.Algorithm.ColumnGeneration(1000, 1.0e-5, 1) 1 12.6s 68.4% 12.6s 426MiB 65.3% 426MiB run 1 12.6s 68.4% 12.6s 426MiB 65.3% 426MiB LP restricted master 2 6.90s 37.5% 3.45s 274MiB 42.0% 137MiB Pricing subproblem 20 2.15s 11.7% 108ms 54.6MiB 8.36% 2.73MiB prepare 1 1.37μs 0.00% 1.37μs 0.00B 0.00% 0.00B ─────────────────────────────────────────────────────────────────────────────────────────────────────────────── [ LogLevel(1): Terminated [ LogLevel(1): Primal bound: Inf [ LogLevel(1): Dual bound: -Inf

Environment (please complete the following information):

ATTENTION: For testing this I used the second-to-last commit of Coluna master, since the latest returns "ERROR: LoadError: UndefVarError: GlobalStrategy not defined"

guimarqu commented 4 years ago

I updated the documentation for the GlobalStrategy error (see #258).

persiflex commented 4 years ago

Thanks! I updated the problem file accordingly and tested on the current master but the bug remains:( test_problem_vs1.txt

guimarqu commented 4 years ago

Thanks! I updated the problem file accordingly and tested on the current master but the bug remains:( test_problem_vs1.txt

Yes, I think the bug is in the colgen algorithm

guimarqu commented 4 years ago

Artifical/setup variables have a too small cost... So it costs less to keep the artificial variable in the solution instead of using a column and ColGen concludes that the problem is infeasible.

guimarqu commented 4 years ago

Hi !

You have to define a primal bound on your objective function : 

objectiveprimalbound!(model, 1000000.0)
persiflex commented 4 years ago

Thanks a lot for fixing this!