# binmodel

binmodel converts polynomial expressions involving binary and continuous variables to linear expressions by introducing additional variables and constraints.

### Syntax

```
[plin1,...,plinN,F] = binmodel(p1,...,pN,Domain)
```

### Examples

The following example solves a quadratic program with binary variables using a mixed integer linear programming solver, by first converting the quadratic function to a linear expression

```
x = binvar(5,1);
Q = randn(5);
p = x'*Q*x;
[plinear,F] = binmodel(p)
optimize(F,plinear)
```

Of course, for this to work, you need a mixed integer linear programming solver (or in the worst-case, BNB together with a linear programming solver).

Products between continuous and binary variables are also supported, but for the big-M modelling to work, you have to specify bounds on the continuous variables

```
x = binvar(5,1);
y = sdpvar(5,1);
Q = randn(5);
p = x'*Q*y;
[plinear,F] = binmodel(p,[-2 <= y <= 2]);
optimize(F,plinear)
```

### Comment

The derivation of the linear model is based on simple logic and big-M modelling. A product of two binary variables **x** and **y** is replaced with a new binary variable **z** and the constraints

```
[z <= x, z <= y, z>= x+y-1];
```

This idea can be generalized to arbitrary polynomials in binary variables. A product between a binary variable **x** and a continuous variable **w**, with known lower and upper bounds **L** and **U**, is replaced by a new continuous variable **v** and the constraints

```
[ L*x <= v <= x*U, L*(1-x) <= w-v <= U*(1-x)]
optimize(F,plinear)
```

This can be generalized to expressions having arbitrarily polynomial w.r.t the binary variable.

## Leave a Comment