<div dir="ltr"><div>Thank you for the reply.<br></div><br>I removed all questions for which I am convinced and I comemnt on the rest:<br><br><div><div><div class="gmail_extra">>> 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).<br>
>> 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.<br><br><br>>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').<br><br></div><div class="gmail_extra">But I do supply an initial column why should that not be taken into account?<br><br><br>>> 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.<div><br></div>
<div><br></div><div>>>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. <br>
</div><div><br></div><div>Yes I do initialize with an initial column which is feasible. It does not immediately update gUB, but it comes quite some time later.<br></div><br></div><div class="gmail_extra"><br><br><br>>> b) How DIP knows whether I the column generated in solveRelaxed is an optimal column or just an improving one?<div>
<br></div><div><br></div><div>>> 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".).</div><br></div><div class="gmail_extra">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.<br>
<br></div><div class="gmail_extra">Thank you again.<br></div><div class="gmail_extra">Shahin<br></div><div class="gmail_extra"><br><br><br><div class="gmail_quote">On Sun, Mar 16, 2014 at 2:19 PM, Matthew Galati <span dir="ltr"><<a href="mailto:matthew.galati@gmail.com" target="_blank">matthew.galati@gmail.com</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr">Hi Shahin.<div><br></div><div>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. </div>
<div><br></div><div>Note - I have not looked at this code in a few years. So, I might not remember everything.</div><div class="">
<div><br></div><div><br>> 1) There is a function in DIP called print, which prints the variables. It is implemented by starting as follows:<br>></div></div><div class=""><div>> in the output always colIndex: always appears to be -1. I have no idea what is this and why always appears as -1.<br>
> VAR c: 231 rc: 0 eff: 0 block: 0 colIndex: -1</div><div>><br>> why m_colMasterIndex is always -1? Is that okay? something is missing?<br></div><div><br></div><div><br></div></div><div>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.</div>
<div><br></div><div><br></div><div><br></div><div><div class=""><br>> 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).<br>
> 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.<br><br><br></div>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').<div class="">
<br>
<br><br><br><br>> 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.</div></div><div>
<br></div>
<div><br></div><div>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. <br>
</div><div class=""><div><br></div><div><br></div><div><br></div><div><br></div><div><br>><br>> 3) in DecompAlgo.cpp (6631)<br>><br>> if ((!m_isColGenExact && nNewVars <= 0) || (m_param.SolveRelaxAsIp == 2)) {<br>
> .......<br>> assert(subprobSI);<br>> double rcBestCol = DecompInf;</div><div>> a) If in at least one block I do not generate any further column, then this assert is hit and the program terminates.<br>
> But it seems logical to me that sometime one block does not generate any column but the other blocks keep proposing other improving solutions.<br></div><div><br></div></div><div>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?</div>
<div class="">
<div><br></div><div><br><br>> b) How DIP knows whether I the column generated in solveRelaxed is an optimal column or just an improving one?</div><div><br></div><div><br></div></div><div>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".).</div>
<div><br></div><div><br><br></div></div>
</blockquote></div><br></div></div></div></div>