[Coin-discuss] Thank you, Laci

[Heesu Hwang]

Dear, Laci.

I used a column generation example, which generates columns within
compute_lower_bound().
I have been trying to add cut generation feature on it, but somehow it made me
really confused, just because I couldn't see the exact orders.
Your answer showed clear flows and resolved all the issues that I have been
struggling with.
Now I am loving COIN :-)

Thank you so much.

Heesu.


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
> 

_______________________________________________
Coin-discuss mailing list
Coin-discuss at list.coin-or.org
http://list.coin-or.org/mailman/listinfo/coin-discuss