Can we use continuous variables instead of binary variables in this NLP problem?

The following problem is defined with binary variables $$a_{i1}, a_{i2}, a_{i3}, k_1$$ and $$k_2$$. Is it possible to avoid binary variables and to only work with continuous variables? How would we ought to adjust the constraints then?

Variables

$$a_{i1}, a_{i2}, a_{i3} \in \{0, 1\}$$ and initialized to $$0$$,

$$0 \le x_1, x_2, x_3 \lt 1$$,

$$b_1, b_2 \in [0, 1]$$

$$k_{i1}, k_{i2} \in \{0, 1\}$$ and initialized to $$0$$,

$$z_i$$

Constants

$$M = 10$$.

Objective function

$$\min_{x_1, x_2, x_3, b_1, b_2} f(D_i, P_i, z_i)$$

Constraints

• $$z_i = a_{i1}x_1 + a_{i2}x_2 +a_{i3}x_3$$
• $$b_1-c_i \le a_{i1}M$$
• $$c_i -b_2 \le a_{i3}M$$
• $$a_{i1}+a_{i2}+a_{i3} = 1$$
• $$c_i-b_1 \le Mk_{i1}$$
• $$b_2 - c_i \le Mk_{i2}$$
• $$k_{i1}+ k_{i2} - 1 \le a_{i2}$$
• $$\sum_{i=1}^n D_iz_i = \beta \sum_{i=1}^n D_i$$
• Yes, binaries can be replaced by NLP by continuous variables, but it's not necessarily a good idea, and usually is a bad idea. Binary variable b can be declared continuous by adding the constraint $b(b-1) = 0$. Continuous yes, well behaved, probably not. Sort of a not good way of writing a complementarity constraint. General integer variables, for example, integer x in range of 0 to 3 can be replaced by continuous x with constraint $x(x-1)(x-2)(x-3) = 0$. Again, not usually a good idea. There might be lots of local minima. Dec 2, 2022 at 17:38
• @MarkL.Stone interesting! Thanks! Dec 2, 2022 at 17:38
• Please confirm whether you really want $k_1$ and $k_2$ and not instead $k_{i1}$ and $k_{i2}$. What you have now forces $k_1=1$ if $c_i > b_1$ for at least one $i$, and $k_2=1$ if $c_i < b_2$ for at least one (possibly different) $i$. Dec 2, 2022 at 17:55
• I mean that your function $f$ is not a black-box oracle (a simulator, or another optimization problem for example) Dec 2, 2022 at 21:28
• Dec 3, 2022 at 15:26

Yes, binaries can be replaced by NLP using continuous variables. But it's not necessarily a good idea, and is usually is a bad idea. If it were a good idea, there probably wouldn't be MINLP solvers.

Binary variable $$b$$ can be declared continuous by adding the constraint $$b(b−1)=0$$. Continuous yes. Well behaved, probably not. It's basically a non-nice way of writing a complementarity constraint, and inherits the challenges of such constraints.

General integer variables, for example, integer x in range of 0 to 3 can be replaced by continuous x with constraint $$x(x−1)(x−2)(x−3) = 0$$. Again, not usually a good idea.

The reformulation of binary or integer to continuous as above, results in a non-convex optimization problem. The original problem formulation having binary or integer variables, would not be convex, but its continuous relaxation might be. The reformulated problem is not convex.

For binary or general integer variable, there might be at lease one local minimum associated with every integer value (which would be 2 in the case of binary). If there are multiple binary or integer variables, there may be at least one local minimum for every integer combination (if all binary, then $$2^n$$ such combinations, where n is number of binaries).

You can relax integrality of $$a_{i2}.$$ Due to the "big M" constraints, I do not believe you can relax integrality of the other binary variables. It's a bit hard to be sure, since you did not indicate what the $$c_i$$ are and whether $$f()$$ is increasing, decreasing or not montonic in its arguments.

• I'm working with a solver that doesn't work with binary variables and make them continuous directly. Can we add a constraint to enforce these continuous variables to be either 1 or zero? Dec 2, 2022 at 17:32
• No, you cannot, at least not while staying within the confines of linear (or convex quadratic) constraints.
– prubin
Dec 2, 2022 at 19:06