[Scip] Transformed constraints

Fri May 14 15:26:51 MEST 2010

Hi,

> I would like to another question, is it possible to solve quadratic
> problems with SCIP? Or do I have to reformulate it in a linear way?

Yes, you can try to do that.
With SCIP 1.2.0, only the ZIMPL reader supports the creation of
quadratic constraints, so you would need to model your problem with
ZIMPL (or use the C-interface).

Stefan

> 
> And finally, a little of off topic question, do you know of any
> standalone solver for multiobjective integer programming? I would like
> to solve another problem in a multiobjective way?
> 
> Best regards to you all, keep the good work up.
> -------------------------------------------------
> Julio Rojas
> jcredberry at gmail.com
> 
> 
> 
> On Fri, May 14, 2010 at 12:17 PM, Timo Berthold <berthold at zib.de> wrote:
>> Hi Julio.
>>
>>> -1<= 2*y12 - x1 - x2 <= 0
>>> [logicor] <both_x1x2_a>: logicor(<t_y12>, <t_x1_neg>, <t_x2_neg>)
>>>
>>> I guess that logicor stands for "logic or", but my constraint is more
>>> of a "logic and" in the sense that if y12 is in the solution then both
>>> x1 and x2 are also part of the solution. Why an "or"?
>>
>> Well, in optimization as well as in real life, logic sometimes depends on the
>> point of view. ;-)
>> Maybe you noticed, that you x_1 and x_2 appear with the suffix _neg, which
>> stands for negated. For a binary variable, the negation is defined as x_neg =
>> 1-x. Hence, x_neg is "true", if x is "false" and vice versa.
>>
>> logicor(<t_y12>, <t_x1_neg>, <t_x2_neg>) now says that y_12 is true, or x1 or
>> x2 is false, which is a (tighter) reformulation of
>> -1<= 2*y12 - x1 - x2
>>
>>
>>> On the setppc constraint:
>>> [setppc] <both_x5x6_b_clq_0_0>: +<t_y56> +<t_x6_neg> <= 1;
>>
>> This comes from the clique partitioning of knapsack constraint. For a small
>> example, see, e.g., http://scip.zib.de/doc/html/FAQ.html#Q16
>>
>> a knapsack is a constraint of the form \sum_{i} a_i x_ i \leq b, with a_i and
>> b being positive integers and x_i binary variables.
>> I guess that the right part of your constraint gets upgraded to a knapsack in
>> the following way:
>> 2*y12 - x1 - x2 <= 0
>> <=> 2*y12 -(1-x1_neg) -(1-x2_neg) <= 0
>> <=> 2*y12 +x1_neg+x2_neg <= 2
>> which gives *exactly* the example linked above (with y12 playing the role of
>> x3).
>>
>> Does all the presolving reformulation cause any hassles to you or are you just
>> keen to understand what is happening?
>> In the first case, we could give you some tips how to avoid them, in the later
>> case I also recommend to have a look at Tobias Phd thesis:
>> http://opus.kobv.de/tuberlin/volltexte/2007/1611/pdf/achterberg_tobias.pdf
>>
>>> Is this derived from the same original constraint as the logicor? Why
>>> both? I actually included the setppc constraint in my model when I was
>>> starting to define it, but I dropped it later on its development as I
>>> thought it was redundant. I guess not :)
>>
>> Just see it as an advantage, that solvers like SCIP or Cplex are often able to
>> detect these information on their own. :-)
>>
>>> Again, thanks in advance.
>>
>> Always welcome.
>>
>> Cheers,
>> Timo
>>
>>> I don't know where I would be in my thesis
>>> if not for you guys and SCIP. I was fed up by my CPLEX friends (PhD in
>>> OR) laughing at me for using lpsolve. ;)
>>>
>>> -------------------------------------------------
>>> Julio Rojas
>>> jcredberry at gmail.com
>>>
>>> On Fri, May 14, 2010 at 2:03 AM,  <michael.winkler at zib.de> wrote:
>>>> Hi Julio,
>>>>
>>>>> [logicor] <both_x1x2_a>: logicor(<t_y12>, <t_x1_neg>, <t_x2_neg>);
>>>>> [setppc] <both_x5x6_b_clq_0_0>: +<t_y56> +<t_x6_neg> <= 1;
>>>>>
>>>>> The second one, I think the presolver took it by decomposing another
>>>>> constraint in two. But the first one, I don't have a clue of what it
>>>>> means.
>>>>
>>>> Yes, the presolver extracted the second constraint out of another. The
>>>> first one is an upgraded special linear constraint.
>>>>
>>>>> Can somebody care to explain what "logicor" and "setppc" mean?
>>>>
>>>> "setppc" and "logicor" constraints are a special type of linear
>>>> constraints containing only binary variables and as coefficients and
>>>> right hand side and/or left hand side only ones.
>>>>
>>>> "setppc" comprises three subtypes,
>>>>
>>>> set partitioning: sum_i^n x_i = 1
>>>>
>>>> set packing: sum_i^n x_i <= 1
>>>>
>>>> set cover: sum_i^n x_i >= 1
>>>>
>>>> "logicor" constraints looks like set cover constraints, but are handled
>>>> differently inside SCIP.
>>>>
>>>>> Is there a way to directly include this kind of constraints using the
>>>>> standalone solver?
>>>>
>>>> Do you mean that if the standalone solver is able to read these kind of
>>>> constraints in the format above? Then now, SCIP is not able to read this
>>>> format (CIP format) directly, but we are working on it and hopefully it
>>>> will be possible to read this format after our next release. But you can
>>>> easily write these kinds of constraints as (normal) linear constraints
>>>> (e.g. in lp format) and SCIP will recognize and upgrade them to their
>>>> special linear contraint types.
>>>> ( If you are programming with SCIP, you can call
>>>> SCIPcreateConsLogicor/SCIPcreateConsSetpart/SCIPcreateConsSetpack/SCIPcre
>>>> ateConsSetcover to directly create these special types of constraints. See
>>>> more at http://scip.zib.de/doc/html/index.html )
>>>>
>>>> Hope that helps you a little bit, have fun.
>>>>
>>>> Best regards,
>>>>
>>>> Michael
>>>>
>>>>> Dear all, I'm really new to linear optimization in general and binary
>>>>> integer programming in particular. I mostly use very simple models for
>>>>> clustering and bundling problems. In one of them I see that there are
>>>>> some transformed constraints after the presolver passes by:
>>>>>
>>>>> [logicor] <both_x1x2_a>: logicor(<t_y12>, <t_x1_neg>, <t_x2_neg>);
>>>>> [setppc] <both_x5x6_b_clq_0_0>: +<t_y56> +<t_x6_neg> <= 1;
>>>>>
>>>>> The second one, I think the presolver took it by decomposing another
>>>>> constraint in two. But the first one, I don't have a clue of what it
>>>>> means. Can somebody care to explain what "logicor" and "setppc" mean?
>>>>> Is there a way to directly include this kind of constraints using the
>>>>> standalone solver?
>>>>>
>>>>> Thanks in advance for your help. Best regards.
>>>>> -------------------------------------------------
>>>>> Julio Rojas
>>>>> jcredberry at gmail.com
>>>>> _______________________________________________
>>>>> Scip mailing list
>>>>> Scip at zib.de
>>>>> http://listserv.zib.de/mailman/listinfo/scip
>>>
>>> _______________________________________________
>>> Scip mailing list
>>> Scip at zib.de
>>> http://listserv.zib.de/mailman/listinfo/scip
>>>
>>
> 
> _______________________________________________
> Scip mailing list
> Scip at zib.de
> http://listserv.zib.de/mailman/listinfo/scip
> 