[Coin-discuss] Generating both cuts and vars

Heesu Hwang hxh9528 at omega.uta.edu
Wed Jun 28 02:36:01 EDT 2006


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.





More information about the Coin-discuss mailing list