Binary Variables

[adishavit]

Is there a way to define (or simulate) binary variables?
Can I add a constraint that x^2=x?
Does x always have to be strictly positive? Is there an approximation?
Can the "positive constants" be 0?

My motivating usage is that at least one of two constraints over variables must hold (whichever is best for the objective). I can work the "binary" variables into the constraints and require that their sum >= 1.

Here is another example:

[1ozturkbe]

That is a great question. If you actually try to solve the very simple problem min(x), s.t. x^2=x, you would find that x is not lower bounded. The reason is that constraints are satisfied usually to an epsilon value, and that allows for x to go to e^(- big number), i.e. as close to zero as we allow.

As for part two, x has to be strictly positive in a GP (where the domain in logspace is the reals). But in cases where we 'need' zero, we usually approximate 0 with a very small lower bound, eg. 1e-30 as in the case with gpkit.constraints.bounded. You can definitely substitute 0, but that may have different effects depending on which variables have a zero sub.

[1ozturkbe]

Unfortunately, what you describe in your example is a token case of mixed integer programming, which is one of the additions we are hoping to have in the future per #414. As far as I know, we do not have any good GP relaxations of mixed integer problems that actually give integer solutions.

[1ozturkbe]

In the meanwhile (while MIGP does not exist),the problem you describe is a mixed integer LP, which is efficiently solvable. If you definitely need it to be GP because you have other constraints, if the number of binary variables is small, what I'd suggest is trying to run every possible combination of constraints (removing the need for a big-M formulation altogether). This would also turn every constraint into a posynomial inequality, making solving them easy!

[1ozturkbe]

Actually, on that note, the constraint x**2 == x actually works to effectively simulate binary variables, as long as x is bounded from below. @bqpd this is very noteworthy.

[1ozturkbe]

@adishavit sorry about the brain dump, but you could actually try writing out a small problem and seeing if the fact that we cannot have real zero (and having tons of signomials) causes problems.

[1ozturkbe]

@adishavit I got excited about the prospect that the binary vars trick might work, and just rigged up a basic knapsack problem.

from gpkit import Variable, VectorVariable, Model
from gpkit import SignomialsEnabled
from gpkit.constraints.bounded import Bounded
import numpy as np

weights = np.array([10, 20, 30])
values = np.array([60, 100, 120])
capacity = 50
n = len(weights)

z = VectorVariable(n, 'z', '-', 'binary variable')
value = Variable('v', '-', 'value')
with SignomialsEnabled():
    constraints = [value <= sum(values*z)]
constraints += [sum(weights*z) <= capacity]
constraints += [z[i]**2 == z[i] for i in range(n)]
m = Model(1/value, Bounded(constraints))
sol = m.localsolve()

Unfortunately it doesn't work (even at really low reltol). Perhaps there is a different formulation?

[bqpd]

that monomial equality constraint will get simplified by division, an invalid operation for zero. try specifying it as a signomial equality? (though I'm skeptical this will work)

On Sat, Feb 8, 2020, 17:21 Berk Ozturk notifications@github.com wrote:

@adishavit https://github.com/adishavit I got excited about the prospect that the binary vars trick might work, and just rigged up a basic knapsack problem.

from gpkit import Variable, VectorVariable, Modelfrom gpkit import SignomialsEnabledfrom gpkit.constraints.bounded import Boundedimport numpy as np

weights = np.array([10, 20, 30]) values = np.array([60, 100, 120]) capacity = 50 n = len(weights)

z = VectorVariable(n, 'z', '-', 'binary variable') value = Variable('v', '-', 'value')with SignomialsEnabled(): constraints = [value <= sum(valuesz)] constraints += [sum(weightsz) <= capacity] constraints += [z[i]**2 == z[i] for i in range(n)] m = Model(1/value, Bounded(constraints)) sol = m.localsolve()

Unfortunately it doesn't work and I cannot explain why, because it is signomial. Perhaps there is a different formulation?

— You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub https://github.com/convexengineering/gpkit/issues/1457?email_source=notifications&email_token=AALKAGGAQKNKSIZEVQ34QZ3RB4V7FA5CNFSM4KR3TYY2YY3PNVWWK3TUL52HS4DFVREXG43VMVBW63LNMVXHJKTDN5WW2ZLOORPWSZGOELF5BAA#issuecomment-583782528, or unsubscribe https://github.com/notifications/unsubscribe-auth/AALKAGG3LLDLQF4WXP44HZTRB4V7FANCNFSM4KR3TYYQ .

[adishavit]

Thanks @1ozturkbe for your heroic attempts! I have too many constraints to try them all - I get an exponential explosion. I can't use LP since I have other, quadratic, constraints.

@bqpd, I did try somthing like this:

x = Variable("x")
y = Variable("y")

# Constraint
with gpkit.SignomialsEnabled():  
    constraints = [x*x == x, y*y==y, x+y <= 1]

# Objective (to minimize)
objective = x*y

# Formulate the Model
m = Model(objective, constraints)

# Solve the Model
sol = m.solve(verbosity=1)

It does not seem to work with the Sigmials either. ... RuntimeWarning: final status of solver 'cvxopt' was 'unknown', not 'optimal'.

Is there an alternate formulation that might work? Maybe somehow solving for x+1 to avoid a zero solution?

Is there an open source MIQP/MIGP solver that you can recommend?

[1ozturkbe]

@adishavit I can recommend JuMP, which is implemented in Julia. It is easily installed, can solve MISOCP problems, which are more general than MIQP and should work fine for your purposes. Here is the documentation.

[rileyjmurray]

Minimizing x * y isn’t MISOCP compatible as far as I know.

Separately, cvxpy allows MISOCP as well. You just need to select a solver like MOSEK, GUROBI, or CPLEX. (The open source ECOS_BB is also an option, but it is not reliable.)

On Sun, Feb 9, 2020 at 8:10 AM Berk Ozturk notifications@github.com wrote:

@adishavit https://github.com/adishavit I can recommend JuMP, which is implemented in Julia. It is easily installed, can solve MISOCP problems, which are more general than MIQP and should work fine for your purposes. Here http://www.juliaopt.org/JuMP.jl/dev/ is the documentation.

— You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub https://github.com/convexengineering/gpkit/issues/1457?email_source=notifications&email_token=ACRLIFCWDSHS54VSMJOWP5TRCATIJA5CNFSM4KR3TYY2YY3PNVWWK3TUL52HS4DFVREXG43VMVBW63LNMVXHJKTDN5WW2ZLOORPWSZGOELGQUFQ#issuecomment-583862806, or unsubscribe https://github.com/notifications/unsubscribe-auth/ACRLIFH754TJXJ4ZOWLFR43RCATIJANCNFSM4KR3TYYQ .

-- Riley Murray B.S. IEOR, 2016

[1ozturkbe]

@bqpd this is a good opportunity to clarify the simplifications a little bit. I tried the knapsack problem with SigEqs and it made no practical difference. Unlike localsolve, which fails to converge, it actually solves with penalty_ccp_solve, albeit with there being active slacks. Once a signomial equality above is approximated, does the division also occur before the GP solve?

[1ozturkbe]

@rileyjmurray I believe @adishavit's example was a dummy problem, and not the problem he intends to solve. but yes, bilinear constraints are not SOCP. And cvxpy is probably good too, I just have no experience with it.

[1ozturkbe]

but also @adishavit, I do know (had to dig up some old lecture notes) that there are at a minimum linear dual representations of bilinear constraints over integer variables, if that is what you're looking for.

[adishavit]

Thanks for the tips. I'm quite new to this. My variables/constrains are currently not integer, except in the sense of binary either-or selection of alternate constraints (as in the OP) example. They are quite similar to the floor-plan problem in Boyd and Vandenberghe 8.8, except that the relative ordering of the rectangles is unspecified. In addition I still have aspect ratio and min/max area constraints - hence MIQP. I was hopeful that I could squeeze binary variables out of gpkit and it would be perfect for me as it's so easy to use.

[1ozturkbe]

@adishavit sorry to disappoint. But I do think that cvxpy or JuMP are more suited to address these problems, and the syntax is not so different from GPkit! Best of luck, and unless you have further questions I will close this issue.

[adishavit]

Thanks for all your help!