Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Integer variables in GP #1590

Closed
adishavit opened this issue Dec 23, 2021 · 10 comments
Closed

Integer variables in GP #1590

adishavit opened this issue Dec 23, 2021 · 10 comments
Labels
enhancement help wanted We would appreciate contributions for this issue! A CVXPY member will provide guidance.

Comments

@adishavit
Copy link
Contributor

Is it possible to solve a mixed integer geometric program?
Currently, one can set just one attribute: either integer=True of pos=True. The latter is mandatory for GP problems.
Is there a way of somehow using integer variables in GPs despite this (other than using the as Real and rounding)?

@phschiele
Copy link
Collaborator

@adishavit This is currently not supported. See #1446 for details.
You can try setting only integer=True and add a constraint of the form x>=0.
As mentioned in#1446, you could add a nonneg wrap if you need the sign for DCP reasons.

@SteveDiamond
Copy link
Collaborator

@phschiele this is the first situation I've seen where the limitation of one attribute per variable is a real impediment. I'm starting to think that maybe multiple attributes should be allowed. Something to discuss in the discord.

@adishavit this is a very interesting use case! If you have too much trouble making a pos wrap feel free to DM me.

@rileyjmurray rileyjmurray added enhancement help wanted We would appreciate contributions for this issue! A CVXPY member will provide guidance. labels Jan 15, 2022
@rileyjmurray
Copy link
Collaborator

rileyjmurray commented Mar 19, 2022

I remember a discussion on the GPKit repo about this kind of functionality. Here's a summary of the situation and a suggested plan of attack if someone wants to volunteer for this.

Constraining a variable to take on specific values in mixed-integer convex programming

Here's a function that takes a scalar expression expr and returns constraints that ensure expr.value is in vec:

def exprval_in_vec(expr, vec):
    assert expr.is_affine()
    assert expr.size == 1
    vec = np.sort(vec)
    d = np.diff(vec)
    z = Variable(shape=(d.size,), boolean=True)
    cons = [z[i+1] <= z[i] for i in range(d.size)]
    cons.append(expr == vec[0] + d @ z)
    return cons

The initial constraints in cons together with 0/1 constraints on z ensure that z is always a vector of the form [1,...,1,0,...,0] -- i.e. consecutive ones, then consecutive zeros. The constraint expr == vec[0] + d @ z ensures that expr takes a value in vec.

Using varval_in_vec for mixed-integer geometric programming

In our context, we'll have a vector of positive integers a, and we'll want to constrain a posynomial variable x to take on a value a[i] for some i. From the perspective of the mixed-integer convex programming formulation, we need to enforce constraints on expr where expr = log(x). Of course, x takes on a desired value as long as expr takes on a value in vec = np.log(a).

We can only use this reformulation as we're converting a DGP problem to a DCP problem. Existing code for those conversions is in dgp2dcp/ and especially in the subfolder dgp2dcp/atom_canonicalizers. Note that although the subfolder is called "atom_canonicalizers" it also canonicalizes Constraint objects (e.g., here).

Suggested implementation route

I think the way forward here is to define a new Constraint class called FiniteSet, which will basically encapsulate a call to varval_in_vec. Existing Constraint classes are defined in this folder. Implementing the class in full generality would take a lot of work, since it applies to DCP and DGP problems. I'd be open to merging a pull request that starts by only supporting DCP problems. I also don't think the implementation for DCP problems needs to be perfect in the first pull request, so long as we have time to improve it before the release of CVXPY 1.3.

@aryamanjeendgar
Copy link
Contributor

Hi! I would like to try working on this issue

@rileyjmurray
Copy link
Collaborator

That's great to hear @aryamanJgl! Please feel free to follow up here with questions.

@rileyjmurray
Copy link
Collaborator

To clarify for those who find themselves here: the FiniteSet constraint introduced in #1740 can be used for integer variables in GP, but we haven't provided a simple function for that yet. So this issue should remain open until FiniteSet has a canonicalization pathway for DGP.

@SteveDiamond SteveDiamond mentioned this issue Feb 20, 2023
9 tasks
@phschiele
Copy link
Collaborator

Closed via #2041 which adds DGP canonicalization of FiniteSet as mentioned by @rileyjmurray above.

@github-project-automation github-project-automation bot moved this to Done in CVXPY Apr 1, 2023
@yasirroni
Copy link
Contributor

yasirroni commented Oct 11, 2023

@adishavit This is currently not supported. See #1446 for details. You can try setting only integer=True and add a constraint of the form x>=0. As mentioned in#1446, you could add a nonneg wrap if you need the sign for DCP reasons.

Hey @phschiele, I've read the FiniteSet example but can't get the grasp to implement that to cp.Variable.

Is there any equivalent to this,

v = cp.Variable((n, m), integer=True, pos=True)

without using,

v = cp.Variable((n, m), integer=True)
cons = [v >=0]

with the help of FiniteSet?

@SteveDiamond
Copy link
Collaborator

@adishavit This is currently not supported. See #1446 for details. You can try setting only integer=True and add a constraint of the form x>=0. As mentioned in#1446, you could add a nonneg wrap if you need the sign for DCP reasons.

Hey @phschiele, I've read the FiniteSet example but can't get the grasp to implement that to cp.Variable.

Is there any equivalent to this,

v = cp.Variable((n, m), integer=True, pos=True)

without using,

v = cp.Variable((n, m), integer=True)
cons = [v >=0]

with the help of FiniteSet?

There is not. What is the harm of

v = cp.Variable((n, m), integer=True)
cons = [v >=0]

?

@phschiele
Copy link
Collaborator

@adishavit This is currently not supported. See #1446 for details. You can try setting only integer=True and add a constraint of the form x>=0. As mentioned in#1446, you could add a nonneg wrap if you need the sign for DCP reasons.

Hey @phschiele, I've read the FiniteSet example but can't get the grasp to implement that to cp.Variable.
Is there any equivalent to this,

v = cp.Variable((n, m), integer=True, pos=True)

without using,

v = cp.Variable((n, m), integer=True)
cons = [v >=0]

with the help of FiniteSet?

There is not. What is the harm of

v = cp.Variable((n, m), integer=True)
cons = [v >=0]

?

@yasirroni Is your problem also related to DGP, where you need the variable to be classified as being positive?

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
enhancement help wanted We would appreciate contributions for this issue! A CVXPY member will provide guidance.
Projects
Status: Done
Development

No branches or pull requests

6 participants