Can we replace a binary variable with a continuous variable using a quadratic equality constraint?

Question

Is it possible to replace a binary variable $x$ with a continuous variable that satisfies the quadratic equality constraint $x^2 - x=0$?

The function $f(x) = x^2 -x$ is not a convex function. Can this constraint still be helpful in using binary variables in constrained optimization problems?

It will be helpful if you give literature references to problems having binary variables solved using this method.

The paper on max cut by Goemans and Williamson use the constraint $x^2=1$ to enforce $x\in{-1,1}$, which they relax to derive a strong SDP-based relaxation (essentially launching the use of SDP relaxations for combinatorial problems, I think) — David M., Jun 15 '19 at 02:28
Correction to your statement. $f(x) = x^2 -x$ IS a convex function, but$ f(x) = 0$ is NOT a convex CONSTRAINT. Also note that $f(x) \le 0$ is a convex constraint, which ties into the above comment by @David M .That can also be helpful when trying to handle complementarity constraints arising in MPECs using SQP. See for example http://www3.eng.cam.ac.uk/~dr241/Papers/Fletcher-Leyffer-Ralph-Scholtes.pdf . — Mark L. Stone, Jun 15 '19 at 10:02
Expressing Combinatorial Optimization Problems by Systems of Polynomial Equations and the Nullstellensatz (2007) — Rodrigo de Azevedo, Jun 15 '19 at 14:22

score 5 · Accepted Answer · answered Jun 21 '19 at 13:47

A similar idea has been used in the paper A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems by Sherali and Adams (1990).

From the abstract (emphasis mine):

In this paper a reformulation technique is presented that takes a given linear zero-one programming problem, converts it into a zero-one polynomial programming problem, and then relinearizes it into an extended linear program. It is shown that the strength of the resulting reformulation depends on the degree of the terms used to produce the polynomial program at the intermediate step of this method. In fact, as this degree varies from one up to the number of variables in the problem, a hierarchy of sharper representations is obtained with the final relaxation representing the convex hull of feasible solutions. (...)

That is, equalities like the one you propose can be used to derive stronger linear programming relaxations, up to the convex hull for zero-one programming problems.

The authors of the above paper also mention applications in generating strong or facetial valid inequalities.

Similar ideas have also shown up in other hierarchies (e.g. Lasserre's). This paper provides a good comparison of the different hierarchies which have exploited this idea: https://pubsonline.informs.org/doi/abs/10.1287/moor.28.3.470.16391 — Ryan Cory-Wright, Jun 21 '19 at 18:25

score 3 · Answer 2 · answered Aug 25 '19 at 16:54

Yes it is very possible, we experimented with this when designing Octeract Engine. However, it turns out that in practice NLP solvers have a lot of trouble finding feasible solutions once the model has more than a few binaries. Even when they do find feasible solutions, these tend not to be very numerically stable most of the time.

Can we replace a binary variable with a continuous variable using a quadratic equality constraint?

2 Answers2