Convert nonlinear constraint to linear constraints for mixed-integer linear programming in MATLAB

Question

The constraint looks something like this

$$b_1 x_1 + b_2 x_2 = 100$$

where $b_1, b_2 \in \{0,1\}$ and $x_1, x_2 \in \mathbb R$ have lower and upper bounds. Also, $b_1 + b_2 = 1$.

Answer 1

If I understand your question correctly, the problematic constraint is, essentially, the disjunction

$$x_1 = 100 \lor x_2 = 100$$

Let the other equality constraints be of the form $\rm A x = b$. Hence,

$$\begin{array}{rl} \mathrm A \mathrm x = \mathrm b \land \left( x_1 = 100 \lor x_2 = 100 \right) &\equiv \left( \mathrm A \mathrm x = \mathrm b \land x_1 = 100 \right) \lor \left( \mathrm A \mathrm x = \mathrm b \land x_2 = 100 \right)\\ &\equiv \left( \begin{bmatrix} \mathrm A\\ \mathrm e_1^\top\end{bmatrix} \mathrm x = \begin{bmatrix} \mathrm b\\ 100\end{bmatrix} \right) \lor \left( \begin{bmatrix} \mathrm A\\ \mathrm e_2^\top\end{bmatrix} \mathrm x = \begin{bmatrix} \mathrm b\\ 100\end{bmatrix} \right)\end{array}$$

which defines the union of two hyperplanes. I assume there are also non-negativity constraints.

You can optimize a linear objective over each (convex) feasible region and then take the minimum or maximum of each optimal value. In other words, solve two linear programs.