[Dip] issues with print, dual values etc

[Matthew Galati]

Hi Shahin.

I'll respond below off the top of my head. Later this week, I'll try to
find some time to look over the code.

Note - I have not looked at this code in a few years. So, I might not
remember everything.


> 1) There is a function in DIP called print, which prints the variables.
It is implemented by starting as follows:
>
> in the output always colIndex: always appears to be -1.  I have no idea
what is this and why always appears as -1.
> VAR c: 231 rc: 0 eff: 0 block: 0 colIndex: -1
>
> why m_colMasterIndex is always -1? Is that okay? something is missing?


The colIndex is the column index in the master LP. When a column is
created, it is initialized to -1. Most likely you are printing the column
before it has been added to the master LP. That function is just a
debugging utility.




> 2) When one initialized CG with initial columns, then one expects that
dual values in the first iteration become meaningful (i.e. the redCost
become meaningful).
> But I always get  my redCost == OrgCost and the dual variable associated
to the convex combination is always infinity in the first call to the
solveRelaxed.


The first thing DIP does is try to generate seed columns by solving the
oracle with the original cost vector. Since this is the original pass to
seed the columns, there is no dual solution yet (i.e., any column is
acceptable to enter the master problem) - that is why we use infinity for
the dual variable to start (so the seed columns are not rejected when
checking 'negative reduced cost').




> Moreover, it takes a lot of iterations until DIP show that it reports the
initial columns as upper bound solution for the problem. Up to that point,
the upper bound is always infinity.


Do you mean the continuous upper bound (the DW upper bound?) or the integer
upper bound (global upper bound - gUB)? If the latter, then it is not too
surprising. It has to either 'get lucky' or solve the master IP heuristic
successfully before it finds a gUB. Are you adding seed columns yourself
which are integer feasible to the original model? If so, it should return
those to you the first time it hits the master IP heuristic. If it does
not, that might be a bug (?) - I would need to run your code to check.
There are options (if I recall) to control how often the master IP
heuristic is called.





>
> 3)  in DecompAlgo.cpp (6631)
>
>    if ((!m_isColGenExact && nNewVars <= 0) || (m_param.SolveRelaxAsIp ==
2)) {
> .......
>       assert(subprobSI);
>       double   rcBestCol    = DecompInf;
> a) If in at least one block I do not generate any further column, then
this assert is hit and the program terminates.
> But it seems logical to me that sometime one block does not generate any
column but the other blocks keep proposing other improving solutions.

I'll have to look at the code to remember about this one. But, probably
"SolveRelaxAsIp" is telling DECOMP to use the built-in MILP solver to use
CBC (or whatever MILP solver you have attached) to solve the pricing
problem. SolveRelaxAsIP=2 is probably a debugging utility to double check
the user's implementation. The assert is checking that you actually created
an OSI object for the pricing problem. If you use SolveRelaxAsIP=2, you
have to create the subproblem (so MILP can be used). Does your application
have a user-defined oracle for the subproblem? Did you also define the MILP
explicitly so the built-in subproblem solver could be used?



> b) How DIP knows whether I the column generated in solveRelaxed is an
optimal column or just an improving one?


I forget the details. But, I think the API must ask for a bound as well as
the column objective (and a solver status). The bound on the subproblem is
used for the overall bound. If you cannot provide a bound, then it probably
has to assume your column objective is optimal (e.g., many combinatorial
oracles don't provide a bound - just "optimal" or "failed".).
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://list.coin-or.org/pipermail/dip/attachments/20140316/083a3c5a/attachment.html>