Python CPLEX API: Conditional iteration on binary variables

Question

I'm working on a graph-theoretical problem. Suppose we want to find a Graph G=(V,E), such that there exists a partition X of V containing at most k equivalence classes. A variable p_S takes value 1 exactly when S is a member of partition X, and zero otherwise. So we have a constraint that the sum over all variables p_S is at most k, for all subsets S of V.

So what I want to do is to iterate over all p_S that have value 1 and define more constraints based on the elements I draw out of S. These constraints would preserve that members of an equivalence class share some mutual property.

Is it possible to access the p_S variables that way and how could I do it?

ALternatively I know I can do without iterating on my binary variables if I'm allowed to use binary variables as coefficients in my constraints. Is that possible?

Thanks in advance!

In general, you will need to linearize it. And yes, if I'm allowed to use binary variables as coefficients in my constraints is the basic concept behind this, but you can't multiply two variables in general, meaning, that you need to linearize those products (binary * binary, binary * int, binary * cont) (by additional variables and constraints). For each of those linearizations, there are different approaches and assumptions which are needed (e.g. a-priori bounds)! As this is very model-dependent (which we don't know), there isn't much more to say. — sascha
– sascha, Commented Apr 22, 2020 at 11:09
Thank you for your reply. I don't understand the concept of linearisation, could you provide an example for the case binary* binary? It doesn't have to relate to my model. — Noc
– Noc, Commented Apr 22, 2020 at 12:55
@sascha These are great examples, thanks! If you make a formal answer out of your replys I will accept it. — Noc
– Noc, Commented Apr 22, 2020 at 14:39
So linearizing a product of binary variables involves formulating constraints which contain a decision variable in the righthand-side. I just realized that in the Python CPLEX API the righthand side must be a real number. So how do I make this work? — Noc
– Noc, Commented Apr 22, 2020 at 15:17

rkersh · Accepted Answer · 2020-04-22 17:04:38Z

1

The CPLEX Python API is index based. To iterate over all binary variables with a solution value set to 1 we need to query the variables types and the solution values and filter accordingly. Here is a simple example:

import sys
import cplex


def main(modelfile):
    # Read in a model file.
    c = cplex.Cplex()
    c.read(modelfile)

    # Solve the model and print the solution and status.
    c.solve()
    print("Solution value:", c.solution.get_objective_value())
    print("Solution status: {0} ({1})".format(
        c.solution.get_status_string(),
        c.solution.get_status()))

    # Display all binary variables that have a solution value of 1.
    types = c.variables.get_types()
    nvars = c.variables.get_num()
    binvars = [idx for idx, typ
               in zip(range(nvars), c.variables.get_types())
               if typ == c.variables.type.binary]
    inttol = c.parameters.mip.tolerances.integrality.get()
    binvars_at_one = [idx for idx, val
                      in zip(binvars, c.solution.get_values(binvars))
                      if abs(val - 1.0) <= inttol]
    print("Binary variables with a solution value equal to one:")
    for varname in c.variables.get_names(binvars_at_one):
        print("  ", varname)


if __name__ == "__main__":
    if len(sys.argv) != 2:
        raise ValueError("usage: {0} <model>".format(sys.argv[0]))
    main(sys.argv[1])

For more, see the documentation for Cplex.variables and Cplex.solution.

edited Apr 22, 2020 at 17:04

answered Apr 22, 2020 at 16:54

rkersh

4,5052 gold badges25 silver badges32 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

Noc Over a year ago

Thank you for your effort. Your answer made me realize that the way I phrased the question made no sense in the first place, because it would requiere to have the solution values before solving the optimization problem to conditionally define more constraints based on them. So I will stick to linearization as sascha pointed out.

rkersh Over a year ago

No problem. However, it is not uncommon for one to solve an original model, add more constraints, and solve again in a loop until some desired state is reached. By default, CPLEX will retain the solution information from the previous solve and use it as starting information for subsequent solves. I assumed you were thinking of doing something like that.

Noc Over a year ago

That's interesting! I didn't know about that. I guess then this is actually the right answer for the question I formulated, so I will accept this.

Alex Fleischer · Accepted Answer · 2020-04-22 15:55:38Z

0

linearization example:

from docplex.mp.model import Model

mdl = Model(name='binaryproduct')

x = mdl.binary_var(name='x')
y = mdl.binary_var(name='y')

z = mdl.binary_var(name='z')
# z==x*y
mdl.add_constraint(x+y<=1+z, 'ct1')
mdl.add_constraint(z<=x, 'ct2')
mdl.add_constraint(z<=y, 'ct3')
#end of z==x*y

mdl.solve()



for v in mdl.iter_binary_vars():
    print(v," = ",v.solution_value)

answered Apr 22, 2020 at 15:55

Alex Fleischer

10.3k2 gold badges14 silver badges15 bronze badges

Collectives™ on Stack Overflow

Python CPLEX API: Conditional iteration on binary variables

2 Answers 2

3 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

3 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related