ALPS: No primal ray is available for decomposition

maramos874 commented 4 years ago

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!

kibaekkim commented 4 years ago

Can you share with me the DSPopt files?

maramos874 commented 4 years ago

Sure! Can you please point me to the path where they are stored?

kibaekkim commented 4 years ago

I meant, can you share with me your DSPopt example files? so that I can test your files.

maramos874 commented 4 years ago

Just sent you an email with them ;)

kibaekkim commented 4 years ago

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

maramos874 commented 4 years ago

Awesome! Thank you very much. I'm going to do some test on my side and will keep you posted if anything comes up.

kibaekkim commented 4 years ago

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?

maramos874 commented 4 years ago

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.

kibaekkim commented 4 years ago

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! in opt_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.

maramos874 commented 4 years ago

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?

maramos874 commented 4 years ago

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.

kibaekkim commented 4 years ago

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 https://github.com/Argonne-National-Laboratory/DSP/issues/104.

maramos874 commented 4 years ago

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!

kibaekkim / DSPopt.jl

ALPS: No primal ray is available for decomposition #2

Deterministic equivalent model

Stochastic model