[Scip] Adding new variables for an extended formulation.

Daniel Karch karch at math.tu-berlin.de
Mon Mar 19 10:30:39 MET 2012


Hello everyone,

I am using SCIP for an ILP and have the following problem.

I have inequalities that look like this:

x1 + x2 + x3 + y1 + y2 <= 4,

where all variables are binary, i.e. we can set all but one of them to 1.
I would like to experiment with an extended formulation of my model and use
the following constraints to model the above inequality:

x1 + x2 + x3 <= 2 + Zx,
y1 + y2 <= 1 + Zy,
Zx + Zy <= 1,

i.e. Zx = 1 if and only if x1 + x2 + x3 = 3, and Zy = 1 if and only if y1 +
y2 = 2.

My problem is that the above inequalities are separated via a constraint
handler, i.e. they are not model constraints.
Therefore, the variables Zx and Zy do not exist initially.
What would be the best way to implement this?

At the moment, I do the following:
My constraint handler detects that x1 + x2 + x3 + y1 + y2 > 4 for a given
LP solution and adds the constraints

x1 + x2 + x3 <= 3,
y1 + y2 <= 2,

and then, in the pricing stage, a pricer introduces the variables Zx and
Zy, the constraint Zx + Zy <= 1, and
changes the above two constraints accordingly by introducing the new
variables and adjusting the right hand sides.
Unfortunately, this does not work as desired. The same cut is found again
later, meaning that it is not separated.
I suspect that it must have to do with the fact that the inequalities

x1 + x2 + x3 <= 3,
 y1 + y2 <= 2

are trivially satisfied when they are added to the model, but I am not
sure.
By the way, the inequalities are separated as SCIP_ROWs via SCIPaddCut,
with the forcecut flag set to TRUE.

If anyone has an idea why this does not work, or has an alternative
approach that I could pursue,
I would appreciate to hear it. :-)

Best regards,

  Daniel
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://listserv.zib.de/mailman/private/scip/attachments/20120319/ac65e3d6/attachment.html


More information about the Scip mailing list