[Coin-discuss] Generating both cuts and vars

[Laszlo Ladanyi]

Hi Heesu,

The key to the solution is that both the new cuts and vars must be
algorithmic. Since you generate them together, I suppose you generate them in
the test_feasibility() method, store them, and return them separately in the
appropriate routines.

At this point (i.e., the LP relaxation is solved,the user ahs generated cuts
and/or variables) BCP calls the cuts_to_rows() and vars_to_cols() methods in
that order. In the first call you'll get the list of the new cuts (or a subset
of them depending on how your parameters are set) and the list of the existing
vars (which is the set of original vars) and you are asked to return the rows
*on the set of the existing variables* corresponding to the new cuts. Here you
need not worry about the new vars, BCP does not (yet!) consider them. Then in
the next call you'll get the list of the new vars and the list of the existing
cuts (which at this point *includes* the new cuts) and you are asked to expand
the vars to cols. Thet's when the (m+1, n+1) position gets filled out.

This means that storing the cut as an explicit cut does not work, since then,
es you described, you run into trouble. Instead, you have to have an
algorithmic cut in which in an interanl data structure you store what would be
the full cut, and when asked to convert the cut to a row you return only that
portion that corresponds to the currently existing vars.

I hope this was clear enough :-)... Let me know if you'd need some further
clarification.

--Laci

On Wed, 28 Jun 2006, Heesu Hwang wrote:

> Hi, all.
> 
> 1. I am having trouble with generating cuts and vars at the same time.
> I want to add cuts and vars as follows.
> My problem is a set packing problem with a quadratic constraint.
> min cx	                      (1)
> s.t Ax <=1                   (2)
>     xQx <= d (constant) (3)
>     x={0,1}                    (4)
> 
> Reformulate my problem using linear constraints (by brief notation),
> min cx
> s.t. Ax <= 1              
>      x_i + x_j - 1<= y  (5) say n variables, then i, j = 1,...,n
>      qy <= d               (6) 
>       x = {0,1}
>      0 <= y <= 1          (7)
> 
> I want to solve a following LP relaxation problem (LPRP) at each node, then add
> both constraints and variables, i.e, (5) and (6).
> (LPRP) min cx 
> s.t. Ax <= 1
>       x>=0
> The number of constraints of (5) is dependent upon the number of variables.
> So at each iteration, if variables are generated, I want to reconstruct
> constraint sets (5) and (6), and y variables.
> The problems are....
> (1) If I want to insert cuts of (5), y variables don't exist and cuts cannot be
> aligned according to x and y variables.
> (2) If I want to insert y variables, objective coefficients for y variables are
> 0s, and COIN seems to delete the variables right away. 
> 
> Could you give me some idea on how I can coordinate both x and y variables?
> 
> 
> 2. COIN allows me to generate cuts first and then vars.
> If I generate cuts, however, I cannot add vars until generated cuts will be
> inserted into the current problem.
> To verify this, I tried to generated them at the same time, but I couldn't.
> Say current problem at a node has n vars and m cuts.
> If I add both a cut and a var, the new problem would have n+1 vars and m+1 cuts.
> But in the new problem matrix, (n+1, m+1) th coefficient cannot be aligned.
> 
> Does anyone know how to overcome this?
> 
> 
> Thanks a lot and cheers.
> 
> 
> Heesu Hwang.
> 
> 
> _______________________________________________
> Coin-discuss mailing list
> Coin-discuss at list.coin-or.org
> http://list.coin-or.org/mailman/listinfo/coin-discuss
>