[Dip] Implicit Polyhedra and GAP

[Kipp Martin]

Hi Matt:
> 
>     I ran the GAP example for  VERSION1. Got it to run with no problem.
>     Very useful. I was hoping you could clarify the folloiwng.
> 
>     1) It looks like the only place where the blocks get defined are in
>     235-238:
> 
>        for(i = 0; i < nMachines; i++){
>           modelName = "KP" + UtilIntToStr(i);
>           setModelRelax(NULL, modelName, i);
>        }
> 
>     It looks like you are NOT creating a DecompConstraintSet for each
>     block and you are NOT specifying the variables that go into the
>     blocks. Is this correct? You simply tell the master how many blocks
>     there are with setModelRelax().
> 
> 
> That is correct. There is no "explicit" polyhedron in this example. It 
> is implicitly defined by the oracle (solveRelaxed).

The above is easy and simple, I like it.
> 

> 
> Yes, master-only would be included in redCostX and as a user you would 
> want to ignore them. Each master-only is considered its own block and is 
> dealt with internally. I guess I should add an example that shows 
> implicit polyhdreon and master-only variables? Is that the case you 
> have? If so, I can work on that soon. Yes, you should delcare them and 
> explicitly state them as master-only.

Yes, it is the case I have, depending on how I organize my blocks and 
coupling constrains.
> 
> 
> 
>  
> 
> 
>     4) This is related to 3). If indeed, redCostX is the vector of all
>     variables then I suppose I could easily do what I wrote you about
>     earlier this  summer, namely solve the blocks in parallel. That is I
>     could take redCostX and in my own code, in parallel solve a problem
>     for each block and then when each solveRelaxed() is called in turn,
>     give it the solution from my parallel solve. Does this make sense?
> 
> 
> Not yet. Two issues there. (1) the logic by default is to loop over all 
> blocks and call the solveRelaxed for each value of whichBlock. So, if 
> you solved all in parallel, you'd get too many. You, could, of course, 
> just solve the "first one" for all and then skip the rest. But, that is 
> an ugly hack. (2) The argument convexDual is the dual associated with 
> the convexity constraint for `whichBlock`. To do what you want, you 
> really need all the duals for the convexity constraint. Again, you could 
> "get this" by grabbing the full dual vector from the master LP and 
> parsing it yourself - but that gets tricky when you add in cut and 
> branch constraints to the master -- the accounting is tricky.



But for each block, convexDual affects the value of the reduced cost, 
but it has no effect on which column I choose. The convexDual does not 
affect the subproblem solution, only the solution value. Therefore, in 
the first call to solveRelaxed (whichBlock = 1) I can use redCostX for 
all the variables and simultaneously find the best column for each 
subproblem. Then when the other subproblems are called (whichBlock >1) I 
simply take the column from the first call (do not solve again) and 
return it. The convexDual did not affect that solution. Hope I  am 
making sense here.

Actually the reason I am interested in this is two fold. First, in the 
generic case I want to setup a parallel solve in OS. Second, in my 
specific application, I actually have some coupling constraints across 
the blocks that do not put into the core constraints, but I have a 
pseudo-polynomial algorithm for solving the resulting subproblem. Hard 
to explain by email.


-- 
Kipp Martin
Professor of Operations Research
and Computing Technology
Booth School of Business
University of Chicago
5807 South Woodlawn Avenue
Chicago, IL 60637
773-702-7456
kmartin at chicagobooth.edu
http://www.chicagobooth.edu/faculty/bio.aspx?person_id=12825325568
http://projects.coin-or.org/OS