ALPS: No primal ray is available for decomposition
maramos874 opened this issue · 13 comments
Hi,
I'm trying to solve a large-scale model with DSP, and have tried the stochastic and non-stochastic formulations by following the farmer examples included. Also, I have successfully solved the problem with straight JuMP + Gurobi by modeling it manually in its explicit form, so I know it is feasible in all constraints. Nevertheless, when trying to solve it with DSPopt, ALPS always throws the "No primal ray is available" message, in stochastic and non-stochastic formulation, Dual or Extensive forms. Is it something which may be documented in the past? I could eventually share lps files of the model.
Kind regards!
Can you share with me the DSPopt files?
Sure! Can you please point me to the path where they are stored?
I meant, can you share with me your DSPopt example files? so that I can test your files.
Just sent you an email with them ;)
I can reproduce that and will look into this.
Building optimization model...
Building optimization model sets...
Optimization model sets built in 0.00283957 seconds.
Building optimization model variables...
Optimization model variables built in 0.15803929700000002 seconds.
Building optimization model constraints...
Optimization model constraints built in 0.810828211 seconds.
Optimization model built in 1.2440911350000001 seconds.
Solving optimization model...
Unable to open parameter file </mnt/workspace/projects/targets/src/params.txt>.
Initializing subproblems ...
Initializing master problem ...
Initializing ALPS framework ...
DwModelSmip constructor.
Created BRANCH_NONANT2 rule.
== Welcome to the Abstract Library for Parallel Search (ALPS)
== Copyright 2000-2017 Lehigh University and others
== All Rights Reserved.
== Distributed under the Eclipse Public License 1.0
== Version: Trunk (unstable)
== Build Date: Sep 14 2020
Alps0250I Starting search ...
Not implemented. in OsiScipSolverInterface::getPrimalRays
No primal ray is available. in DwWorker::generateCols
Exception occurred at /Users/kibaekkim/Documents/REPOS/DSP/src/Solver/DantzigWolfe/DwWorker.cpp:347
Error code 1 in /Users/kibaekkim/Documents/REPOS/DSP/src/Solver/DantzigWolfe/DwMaster.cpp:782
Error code 1 in /Users/kibaekkim/Documents/REPOS/DSP/src/Solver/DantzigWolfe/DwBundleDual.cpp:99
[0.341747] curLb 1.79769313e+308, bestUb 1.00000000e+75, bestLb 1.79769313e+308
The current node is fathomed.
Alps0240I Proc: 1, Part: 0, Cand: 0, Best N: 1e+75, Best S: 1e+75
Alps0208I Search completed.
Alps0260I Best solution found had quality 1e+75
Alps0264I Number of nodes processed: 1
Alps0267I Number of nodes branched: 0
Alps0268I Number of nodes pruned before processing: 0
Alps0270I Number of nodes left: 0
Alps0272I Tree depth: 0
Alps0274I Search CPU time: 0.34 seconds
Alps0278I Search wall-clock time: 0.34 seconds
Time spent in heuristics: 0.00 seconds
Awesome! Thank you very much. I'm going to do some test on my side and will keep you posted if anything comes up.
I found the toy example is quite large.. Instead of looking into the model, I ran the extensive form with the following modification in your code:
status=jump.optimize!(model.model,
is_stochastic=true, # Needs to indicate that the model is of the stochastic program.
# solve_type=DSPopt.Dual, # see instances(DSPopt.Methods) for other methods
solve_type=DSPopt.ExtensiveForm,
param="params.txt"
)
The solution status is dual infeasible, which is consistent to what you see from the dual decomposition. I suggest to first check whether your model is correctly formulated. If you believe so, can you make it a tiny example so that we can examine the model manually?
I'm sure that the model is feasible, since I can solve it in its manual extended form. I just sent you a tiny toy example.
I tried writing the deterministic and stochastic models in MPS files.
Deterministic equivalent model
- I have added the following line to
opt_model_deter.jl:
JuMP.write_to_file(model.model, "tiny_ext.mps")
- When reading the file to CPLEX, I got this error:
CPLEX> read tiny_ext
Selected objective sense: MINIMIZE
Selected objective name: OBJ
Selected RHS name: rhs
Selected bound name: bounds
CPLEX Error 1455: Line 538: 'FR' bound type illegal when prior bound given.
No file read.
Stochastic model
- I have added the following right next to
optimize!inopt_model_stoch_imp_DSPopt.jl. The line wrote the extensive form of your stochastic model example into MPS file.
DSPopt.@dsp_ccall("writeMps", Cvoid, (Ptr{Cvoid}, Ptr{UInt8}), DSPopt.dspenv.p, "tiny")
Can you try to fix, if necessary, the deterministic equivalent model first and compare the two resulting MPS files.
Weird, I can solve the generated MPS with Gurobi...
$GUROBI_BIN/gurobi_cl tiny_ext.mps
Using license file /mnt/workspace/gurobi.lic
Gurobi Optimizer version 9.0.2 build v9.0.2rc0 (linux64)
Copyright (c) 2020, Gurobi Optimization, LLC
Read MPS format model from file tiny_ext.mps
Reading time = 0.01 seconds
: 546 rows, 92 columns, 1308 nonzeros
Optimize a model with 546 rows, 92 columns and 1308 nonzeros
Model fingerprint: 0x80000f46
Variable types: 46 continuous, 46 integer (46 binary)
Coefficient statistics:
Matrix range [5e-01, 1e+03]
Objective range [1e-01, 1e+00]
Bounds range [1e+00, 1e+03]
RHS range [1e+00, 3e+03]
Presolve removed 534 rows and 84 columns
Presolve time: 0.00s
Presolved: 12 rows, 8 columns, 26 nonzeros
Variable types: 0 continuous, 8 integer (2 binary)
Found heuristic solution: objective 3306.1989955
Root relaxation: objective 3.166199e+03, 0 iterations, 0.00 seconds
Nodes | Current Node | Objective Bounds | Work
Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time
* 0 0 0 3166.1989955 3166.19900 0.00% - 0s
Explored 0 nodes (0 simplex iterations) in 0.13 seconds
Thread count was 32 (of 64 available processors)
Solution count 2: 3166.2 3306.2
Optimal solution found (tolerance 1.00e-04)
Best objective 3.166198995533e+03, best bound 3.166198995533e+03, gap 0.0000%
Although, the deterministic equivalent is in the opt_model_stoch_exte_non_double.jl file, not in opt_model_deter.jl.
I just sent you both .mps by mail.
The comparison is quite difficult, since DSPopt writes a generic .mps without constraints/variable names. I tried solving with gurobi the tiny_dsp.mps and is indeed infeasible.
$GUROBI_BIN/gurobi_cl tiny_dsp.mps
Using license file /mnt/workspace/gurobi.lic
Gurobi Optimizer version 9.0.2 build v9.0.2rc0 (linux64)
Copyright (c) 2020, Gurobi Optimization, LLC
Read MPS format model from file tiny_dsp.mps
Reading time = 0.01 seconds
OsiGrb_p: 546 rows, 92 columns, 1308 nonzeros
Optimize a model with 546 rows, 92 columns and 1308 nonzeros
Model fingerprint: 0x93d70574
Variable types: 46 continuous, 46 integer (0 binary)
Coefficient statistics:
Matrix range [5e-01, 1e+03]
Objective range [1e-01, 1e+00]
Bounds range [2e+02, 1e+03]
RHS range [1e+00, 3e+03]
Presolve removed 446 rows and 43 columns
Presolve time: 0.00s
Explored 0 nodes (0 simplex iterations) in 0.05 seconds
Thread count was 1 (of 64 available processors)
Solution count 0
Model is infeasible or unbounded
Best objective -, best bound -, gap -
Is it maybe the way I'm writing the model by using different functions and variable containers?
I think may have found the problem. By analyzing the Gurobi stats of the model in the .mps file generated through DSPopt, I realized that binary variables were transformed into unbounded or something integer variables. I added lower and upper bounds to binary variables (0, 1 obviously), and now the model is successfully solved. I sent you both .mps files (original => no bounds => infeasible, and new => bounds => working) by mail.
Great. Yes, I confirm that the example is running with explicit bounds.
I guess that recent updates in Julia or JuMP may have changed how the column bounds are set. I will address this in DSP itself with this issue Argonne-National-Laboratory/DSP#104.
Awesome, Happy to help! Also, (don't know if it is related), but the model is successfully solved in it's extensive form and with the Legacy method, but seems to fail with the Dual one (that, or the final output is misleading: best found 1e75). Will update soon if can find a lead. Thank you very much!