[Scip] Adding new variables for an extended formulation.

[Stefan Heinz]

Hi Daniel,

we never tried something like that such that we can only give an suggestion.

In the moment when your constraint is violated you should create the 2
variables Zx and Zy and the 3 inequalities as linear constraints right
away. If it does not work to create both at the same time, still use
linear constraints instead of rows and make them modifiable.

There are several reasons for creating constraints instead of rows. One is
that someone (in that case the linear constraint handler) has to lock the
two new variables and these constraints have to be checked for any
feasible solution. Which brings us to the question: What do you do when a
solution does not come from the LP?

Best
Timo and Stefan



> 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
> _______________________________________________
> Scip mailing list
> Scip at zib.de
> http://listserv.zib.de/mailman/listinfo/scip
>