[Scip] Detecting specific constraint types from linear constraints

[Timo Berthold]

Hi Martin.

I'm not completely sure how to understand your question: Do you want to 
disable certain kinds of upgrades, s.t., e.g., a constraint \sum x <= 1, x 
binary is upgraded to a (more general) knapsack constraint rather than to a 
set packing constraint? If this is the case you can disable upgrading fore 
certain constraints via the parameters:
/set/constraints/linear/upgrade/{knapsack, setppc, logicor, varbound}

Or do you just want to test whether constraints might be upgraded, but without 
performing the upgrade? If yes: why? ;-)
There is no explicit function that gives you this functionality.
It should, however, not be to hard to implement the test on your own.
First, you disable all upgrades as shown above. Then, you just perform the 
test, the SCIP internal upgrading functions do, on your own.
I.e., for all linear constraints, you check whether
 - all variables must be binary
 - all coefficients must be integral
 - exactly one of the sides must be infinite
in case of a knapsack constraint.

This could be done as follows:

SCIP_CONSHDLR* conshdlr;
conshdlr = SCIPfindConshdlr(scip,"linear");
if( conshdlr != NULL )
{
   SCIP_CONS** conss;
   int i;

   conss = SCIPconshdlrGetConss(conshdlr);
   assert(conss != NULL || SCIPconshdlrGetNConss(conshdlr) == 0);
   for( i = 0; i < SCIPconshdlrGetNConss(conshdlr); ++i)
   {
      SCIP_Bool isknapsack;
      SCIP_VAR** vars;
      SCIP_Real* vals;
      int j;

      assert(conss[i] != NULL);
      vars= SCIPgetVarsLinear(scip,conss[i]);
      vals= SCIPgetValsLinear(scip,conss[i]);

      isknapsack = TRUE;
      isknapsack = isknapsack &&  SCIPisInfinity(scip, -
SCIPgetLhsLinear(scip,conss[i])) != SCIPisInfinity(scip, 
SCIPgetRhsLinear(scip,conss[i]));

      for( j = 0; j < SCIPgetNVarsLinear(scip, conss[i]) && isknapsack; ++j)
      {
         assert(vars[j] != NULL);
         assert(!SCIPisInfinity(scip, vals[j]);

         isknapsack = isknapsack && SCIPvarGetType(vars[j]) == 
SCIP_VARTYPE_BINARY && SCIPisIntegral(scip, vals[j]);
      }

      /* call your own methods here */
   }
}

for the case of a knapsack constraint.
I hope this helps you with your question.

All the best,
Timo

PS: I did not test the code snippet above, there might be typos in it. ;)

Am Dienstag 13 April 2010 09:35:32 schrieb Martin Bergner:
> Hello all,
> 
> I want to detect certain types of constraints such as knapsack/set-
> partitioning/packing etc. . Luckily, the presolver already does that.
> However, the presolver in its default settings is too good, e. g.
> knapsack constraints are converted to logicor or clique constraints,
> which is one step to far. I just want to know if I can upgrade the
> constraint to a particular type.
> 
> It is certainly possible to call the linear upgrade method of the
> relevant constraint handler, but this adds the upgraded constraint to
> it. Actually, I don't want to upgrade the constraint, I just want to
> know if I can upgrade it. Is there a better way to do detect a
> specialized constraint other then upgrading the constraint and then
> deleting it again from the handler?
> 
> Regards,
> Martin
> 
> _______________________________________________
> Scip mailing list
> Scip at zib.de
> http://listserv.zib.de/mailman/listinfo/scip
>