17
$\begingroup$

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.

Improve this question
$\endgroup$
3
  • 4
    $\begingroup$ 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) $\endgroup$
    – David M.
    Jun 15, 2019 at 2:28
  • 4
    $\begingroup$ 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 www3.eng.cam.ac.uk/~dr241/Papers/… . $\endgroup$
    – Mark L. Stone
    Jun 15, 2019 at 10:02
  • $\begingroup$ Expressing Combinatorial Optimization Problems by Systems of Polynomial Equations and the Nullstellensatz (2007) $\endgroup$
    – Rodrigo de Azevedo
    Jun 15, 2019 at 14:22

2 Answers 2

Reset to default
5
$\begingroup$

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.

Improve this answer
$\endgroup$
1
3
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.