[SCIP] pseudoboolean constraints

[Marc Pfetsch]

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