[Dip] issues with print, dual values etc

[Shahin Gelareh]

Thank you for the reply.

I removed all questions for which I am convinced and I comemnt on the rest:

>> 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').

But I do supply an initial column why should that not be taken into account?


>> 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.

Yes I do initialize with an initial column which is feasible. It does not
immediately update gUB, but it comes quite some time later.




>> 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".).

I do supply an objective value, beside other things,  when I create the
DecomVar instance. So the bound is given. But DIP understands somwhow that
the subproblem is not solved to optimality.

Thank you again.
Shahin



On Sun, Mar 16, 2014 at 2:19 PM, Matthew Galati <matthew.galati at gmail.com>wrote:

> 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/fe8b1687/attachment.html>