Solving binary integer programming problems with Gurobi

[Pratik Fegade]

Hi,

I have an optimization problem with exclusively binary variables, a non-linear objective function and linear constraints. The non-linearity in the objective function is due to ANDs of the binary variables, and I can linearize it by adding additional variables myself. For example,

Say we want to linearize the term a AND b, where a and b are both binary. We replace the term with a new binary variable c and add the following constraints.

        Boolean representation           Numerical representation

1.     c --> a                                      a - c >= 1

2.     c --> b                                      b - c >= 1

3.     a AND b --> c                          a + b - c <= 1

I have two questions.

1. Does Gurobi provide some convenience methods to do such linearization?

2. Does this seem like a problem that Gurobi would perform well on? I am concerned as it is an exclusively binary integer programming problem.

Thanks,

Pratik Fegade

[Tobias Achterberg]

Your linearization is not quite correct. It should be

(1a) a - c >= 0
(1b) b - c >= 0
(2) a + b - c <= 1


You can use general constraints to model this. Gurobi supports, among others, the AND
constraint for binary variables, see
http://www.gurobi.com/documentation/8.0/refman/constraints.html

See also the "genconstr" example, for example in Python:
http://www.gurobi.com/documentation/8.0/examples/genconstr_py.html

In your case, you would for example do:

m = Model("mymodel")
a = m.addVar(vtype=GRB.BINARY, name="a")
b = m.addVar(vtype=GRB.BINARY, name="b")
c = m.addVar(vtype=GRB.BINARY, name="c")
m.addConstr(c == and_(a,b))


If you only need the auxiliary variables (in your case, c) to model the objective
function, then, in your linearization, you only need either constraints (1a) and (1b) or
constraint (2), depending on the sign of the objective coefficient. For example, if you
want to minimize c, then you only need (2) because if one of a or b is zero, then there is
no reason for c to be one. It will automatically be pushed down to zero due to the
objective function. This trick is already automatically included when you use the AND
constraint of Gurobi. It will detect that (1a) and (1b) are not needed and only use (2)
for its internal linearization.


Gurobi usually performs pretty well on pure binary problems. But there are
counter-examples. For example, SAT problems are also just binary problems, but because
there the solution to set all variables to 0.5 will always satisfy all constraints in the
MIP formulation, the LP relaxation is pretty useless and thus, you will most of the time
be much faster by using a SAT solver instead. But if you have a meaningful objective
function or more complex constraints (like knapsack constraints) then Gurobi should
usually be a very good choice.


Regards,

Tobias

[Pratik Fegade]

Hi Tobias,

Thanks for pointing me to general constraints. They would help a lot!

Regards,

Pratik Fegade

--

---
You received this message because you are subscribed to a topic in the Google Groups "Gurobi Optimization" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/gurobi/0Pb5YUUsqMs/unsubscribe.
To unsubscribe from this group and all its topics, send an email to gurobi+un...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.