[SCIP] pseudoboolean constraints

[James Cussens]

Thanks for you help Marc. I replaced the pseudoboolean constraints by an equivalent set of and constraints and linear constraints, and all is well.

James

James Cussens
Room MVB 3.26
Dept of Computer Science, University of Bristol
Phone: +44 (0)117 455 8723
https://jcussens.github.io/
Funded PhDs available in Bristol in the following areas: Data Science<http://www.bristol.ac.uk/cdt/compass/>, Interactive AI<http://www.bristol.ac.uk/cdt/interactive-ai/>, Cyber Security<http://www.bristol.ac.uk/cdt/cyber-security/> or Digital Health<http://www.bristol.ac.uk/cdt/digital-health/>.
________________________________
From: Scip <scip-bounces at zib.de> on behalf of Marc Pfetsch <pfetsch at mathematik.tu-darmstadt.de>
Sent: 25 July 2023 12:26
To: scip at zib.de <scip at zib.de>
Subject: Re: [SCIP] pseudoboolean constraints



Hi James,

the pseudoboolean constraints had been added to take part in the
Pseudo-Boolean Competitions, see, e.g.,
http://www.cril.univ-artois.fr/PB16/ . They essentially only exist to
create other constraints and only some presolving is implemented.

One Problem studied in the competitions includes soft constraints, i.e.,
the constraint does not necessarily have to be satisfied, but one wants
to maximize the number of satisfied constraints. This is modeled using
indicator variables, i.e., binary variables that determine whether the
constraint is satisfied. If the constraints are linear this will create
an indicator constraint (cons_indicator.h/c). For your particular
problem it is probably easier if you create the corresponding
constraints yourself instead of using Pseudo-Boolean constraints.

In your problem, the variables x_i and y_i are probably binary, so this
product is expressed by an AND constraint (the product is 1 if and only
if both variables are 1).

To solve your problem with separation, I suggest to set up the
constraints directly and not use Pseudo-Boolean constraints.

I hope that this answers you questions.

Best

Marc



On 25/07/2023 11:21, James Cussens wrote:
> Hi all,
>
> I would appreciate a bit more information on pseudoboolean constraints.
> In particular, I don't understand these arguments in
> SCIPcreateConsBasicPseudoboolean :
>
> indvar         indicator variable if it's a soft constraint, or NULL
> weight         weight of the soft constraint, if it is one
> issoftcons     is this a soft constraint
> intvar         a artificial variable which was added only for the objective
> function, if this variable is not NULL this constraint (without this
> integer variable) describes the objective function
>
> I'm just relying on the doxygen documentation, perhaps this is explained
> in more detail elsewhere. It may be that setting them to non-NULL values
> might help me.
>
> For context, the pseudoboolean constraints I'm using are like this:
>
> z <= \sum_{i=1}^{n} [ x_i + y_i - 2*x_i*y_i ]
>
> and only check and propagate are set to TRUE when they are created. On
> another matter, I see that 'and' variables are created for the x_i*y_i
> products. I've noticed that the associated and constraint is being
> separated even though it is being created from a constraint where
> initial and separate are set to FALSE which does not seem right to me. I
> certainly don't want the and relaxations in my LP since they don't help
> with the dual bound. I guess one way round this is to explicitly create
> non-separable and constraints myself and use
> SCIPcreateConsPseudobooleanWithConss
>
> James
>
> James Cussens
> Room MVB 3.26
> Dept of Computer Science, University of Bristol
> Phone: +44 (0)117 455 8723
> https://jcussens.github.io/ <https://jcussens.github.io/>
> Funded PhDs available in Bristol in the following areas: Data Science
> <http://www.bristol.ac.uk/cdt/compass/>, Interactive AI
> <http://www.bristol.ac.uk/cdt/interactive-ai/>, Cyber Security
> <http://www.bristol.ac.uk/cdt/cyber-security/> or Digital Health
> <http://www.bristol.ac.uk/cdt/digital-health/>.
>
> _______________________________________________
> Scip mailing list
> Scip at zib.de
> https://listserv.zib.de/mailman/listinfo/scip
_______________________________________________
Scip mailing list
Scip at zib.de
https://listserv.zib.de/mailman/listinfo/scip
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://listserv.zib.de/pipermail/scip/attachments/20230727/f20f8b77/attachment.html>