CVXOPT Backend

AUTHORS:

  • Ingolfur Edvardsson (2014-05) : initial implementation

class sage.numerical.backends.cvxopt_backend.CVXOPTBackend

Bases: sage.numerical.backends.generic_backend.GenericBackend

MIP Backend that uses the CVXOPT solver.

There is no support for integer variables.

EXAMPLES:

sage: p = MixedIntegerLinearProgram(solver="CVXOPT")        # optional - cvxopt
add_col(indices, coeffs)

Add a column.

INPUT:

  • indices (list of integers) – this list contains the indices of the constraints in which the variable’s coefficient is nonzero

  • coeffs (list of real values) – associates a coefficient to the variable in each of the constraints in which it appears. Namely, the ith entry of coeffs corresponds to the coefficient of the variable in the constraint represented by the ith entry in indices.

Note

indices and coeffs are expected to be of the same length.

EXAMPLES:

sage: from sage.numerical.backends.generic_backend import get_solver
sage: p = get_solver(solver = "CVXOPT")                 # optional - cvxopt
sage: p.ncols()                                         # optional - cvxopt
0
sage: p.nrows()                                         # optional - cvxopt
0
sage: p.add_linear_constraints(5, 0, None)              # optional - cvxopt
sage: p.add_col(range(5), range(5))                     # optional - cvxopt
sage: p.nrows()                                         # optional - cvxopt
5
add_linear_constraint(coefficients, lower_bound, upper_bound, name=None)

Add a linear constraint.

INPUT:

  • coefficients an iterable with (c,v) pairs where c is a variable index (integer) and v is a value (real value).

  • lower_bound - a lower bound, either a real value or None

  • upper_bound - an upper bound, either a real value or None

  • name - an optional name for this row (default: None)

EXAMPLES:

sage: from sage.numerical.backends.generic_backend import get_solver
sage: p = get_solver(solver = "CVXOPT")                 # optional - cvxopt
sage: p.add_variables(5)                                # optional - cvxopt
4
sage: p.add_linear_constraint(zip(range(5), range(5)), 2.0, 2.0)                # optional - cvxopt
sage: p.row(0)                                          # optional - cvxopt
([1, 2, 3, 4], [1, 2, 3, 4])
sage: p.row_bounds(0)                                   # optional - cvxopt
(2.00000000000000, 2.00000000000000)
sage: p.add_linear_constraint(zip(range(5), range(5)), 1.0, 1.0, name='foo')    # optional - cvxopt
sage: p.row_name(-1)                                    # optional - cvxopt
'foo'
add_variable(lower_bound=0.0, upper_bound=None, binary=False, continuous=True, integer=False, obj=None, name=None)

Add a variable.

This amounts to adding a new column to the matrix. By default, the variable is both positive and real. Variable types are always continuous, and thus the parameters binary, integer, and continuous have no effect.

INPUT:

  • lower_bound - the lower bound of the variable (default: 0)

  • upper_bound - the upper bound of the variable (default: None)

  • binary - True if the variable is binary (default: False).

  • continuous - True if the variable is continuous (default: True).

  • integer - True if the variable is integer (default: False).

  • obj - (optional) coefficient of this variable in the objective function (default: 0.0)

  • name - an optional name for the newly added variable (default: None).

OUTPUT: The index of the newly created variable

EXAMPLES:

sage: from sage.numerical.backends.generic_backend import get_solver
sage: p = get_solver(solver = "CVXOPT")                 # optional - cvxopt
sage: p.ncols()                                         # optional - cvxopt
0
sage: p.add_variable()                                  # optional - cvxopt
0
sage: p.ncols()                                         # optional - cvxopt
1
sage: p.add_variable()                                  # optional - cvxopt
1
sage: p.add_variable(lower_bound=-2.0)                  # optional - cvxopt
2
sage: p.add_variable(continuous=True)                   # optional - cvxopt
3
sage: p.add_variable(name='x',obj=1.0)                  # optional - cvxopt
4
sage: p.col_name(3)                                     # optional - cvxopt
'x_3'
sage: p.col_name(4)                                     # optional - cvxopt
'x'
sage: p.objective_coefficient(4)                        # optional - cvxopt
1.00000000000000
col_bounds(index)

Return the bounds of a specific variable.

INPUT:

  • index (integer) – the variable’s id.

OUTPUT:

A pair (lower_bound, upper_bound). Each of them can be set to None if the variable is not bounded in the corresponding direction, and is a real value otherwise.

EXAMPLES:

sage: from sage.numerical.backends.generic_backend import get_solver
sage: p = get_solver(solver = "CVXOPT")                 # optional - cvxopt
sage: p.add_variable()                                  # optional - cvxopt
0
sage: p.col_bounds(0)                                   # optional - cvxopt
(0.0, None)
sage: p.variable_upper_bound(0, 5)                      # optional - cvxopt
sage: p.col_bounds(0)                                   # optional - cvxopt
(0.0, 5)
col_name(index)

Return the index th col name

INPUT:

  • index (integer) – the col’s id

  • name (char *) – its name. When set to NULL (default), the method returns the current name.

EXAMPLES:

sage: from sage.numerical.backends.generic_backend import get_solver
sage: p = get_solver(solver = "CVXOPT")                 # optional - cvxopt
sage: p.add_variable(name="I am a variable")            # optional - cvxopt
0
sage: p.col_name(0)                                     # optional - cvxopt
'I am a variable'
get_objective_value()

Return the value of the objective function.

Note

Behaviour is undefined unless solve has been called before.

EXAMPLES:

sage: from sage.numerical.backends.generic_backend import get_solver
sage: p = get_solver(solver = "cvxopt")                 # optional - cvxopt
sage: p.add_variables(2)                                # optional - cvxopt
1
sage: p.add_linear_constraint([(0,1), (1,2)], None, 3)  # optional - cvxopt
sage: p.set_objective([2, 5])                           # optional - cvxopt
sage: p.solve()                                         # optional - cvxopt
0
sage: N(p.get_objective_value(),4)                      # optional - cvxopt
7.5
sage: N(p.get_variable_value(0),4)                      # optional - cvxopt
3.6e-7
sage: N(p.get_variable_value(1),4)                      # optional - cvxopt
1.5
get_variable_value(variable)

Return the value of a variable given by the solver.

Note

Behaviour is undefined unless solve has been called before.

EXAMPLES:

sage: from sage.numerical.backends.generic_backend import get_solver
sage: p = get_solver(solver = "CVXOPT")                 # optional - cvxopt
sage: p.add_variables(2)                                # optional - cvxopt
1
sage: p.add_linear_constraint([(0,1), (1, 2)], None, 3) # optional - cvxopt
sage: p.set_objective([2, 5])                           # optional - cvxopt
sage: p.solve()                                         # optional - cvxopt
0
sage: N(p.get_objective_value(),4)                      # optional - cvxopt
7.5
sage: N(p.get_variable_value(0),4)                      # optional - cvxopt
3.6e-7
sage: N(p.get_variable_value(1),4)                      # optional - cvxopt
1.5
is_maximization()

Test whether the problem is a maximization

EXAMPLES:

sage: from sage.numerical.backends.generic_backend import get_solver
sage: p = get_solver(solver = "CVXOPT")                 # optional - cvxopt
sage: p.is_maximization()                               # optional - cvxopt
True
sage: p.set_sense(-1)                                   # optional - cvxopt
sage: p.is_maximization()                               # optional - cvxopt
False
is_variable_binary(index)

Test whether the given variable is of binary type. CVXOPT does not allow integer variables, so this is a bit moot.

INPUT:

  • index (integer) – the variable’s id

EXAMPLES:

sage: from sage.numerical.backends.generic_backend import get_solver
sage: p = get_solver(solver = "CVXOPT")                 # optional - cvxopt
sage: p.ncols()                                         # optional - cvxopt
0
sage: p.add_variable()                                  # optional - cvxopt
0
sage: p.set_variable_type(0,0)                          # optional - cvxopt
Traceback (most recent call last):
...
ValueError: ...
sage: p.is_variable_binary(0)                           # optional - cvxopt
False
is_variable_continuous(index)

Test whether the given variable is of continuous/real type. CVXOPT does not allow integer variables, so this is a bit moot.

INPUT:

  • index (integer) – the variable’s id

EXAMPLES:

sage: from sage.numerical.backends.generic_backend import get_solver
sage: p = get_solver(solver = "CVXOPT")                 # optional - cvxopt
sage: p.ncols()                                         # optional - cvxopt
0
sage: p.add_variable()                                  # optional - cvxopt
0
sage: p.is_variable_continuous(0)                       # optional - cvxopt
True
sage: p.set_variable_type(0,1)                          # optional - cvxopt
Traceback (most recent call last):
...
ValueError: ...
sage: p.is_variable_continuous(0)                       # optional - cvxopt
True
is_variable_integer(index)

Test whether the given variable is of integer type. CVXOPT does not allow integer variables, so this is a bit moot.

INPUT:

  • index (integer) – the variable’s id

EXAMPLES:

sage: from sage.numerical.backends.generic_backend import get_solver
sage: p = get_solver(solver = "CVXOPT")                 # optional - cvxopt
sage: p.ncols()                                         # optional - cvxopt
0
sage: p.add_variable()                                  # optional - cvxopt
0
sage: p.set_variable_type(0,-1)                         # optional - cvxopt
sage: p.set_variable_type(0,1)                          # optional - cvxopt
Traceback (most recent call last):
...
ValueError: ...
sage: p.is_variable_integer(0)                          # optional - cvxopt
False
ncols()

Return the number of columns/variables.

EXAMPLES:

sage: from sage.numerical.backends.generic_backend import get_solver
sage: p = get_solver(solver = "CVXOPT")                 # optional - cvxopt
sage: p.ncols()                                         # optional - cvxopt
0
sage: p.add_variables(2)                                # optional - cvxopt
1
sage: p.ncols()                                         # optional - cvxopt
2
nrows()

Return the number of rows/constraints.

EXAMPLES:

sage: from sage.numerical.backends.generic_backend import get_solver
sage: p = get_solver(solver = "CVXOPT")                 # optional - cvxopt
sage: p.nrows()                                         # optional - cvxopt
0
sage: p.add_variables(5)                                # optional - cvxopt
4
sage: p.add_linear_constraints(2, 2.0, None)            # optional - cvxopt
sage: p.nrows()                                         # optional - cvxopt
2
objective_coefficient(variable, coeff=None)

Set or get the coefficient of a variable in the objective function

INPUT:

  • variable (integer) – the variable’s id

  • coeff (double) – its coefficient

EXAMPLES:

sage: from sage.numerical.backends.generic_backend import get_solver
sage: p = get_solver(solver = "CVXOPT")                 # optional - cvxopt
sage: p.add_variable()                                  # optional - cvxopt
0
sage: p.objective_coefficient(0)                        # optional - cvxopt
0.0
sage: p.objective_coefficient(0,2)                      # optional - cvxopt
sage: p.objective_coefficient(0)                        # optional - cvxopt
2.0
problem_name(name=None)

Return or define the problem’s name

INPUT:

  • name (str) – the problem’s name. When set to None (default), the method returns the problem’s name.

EXAMPLES:

sage: from sage.numerical.backends.generic_backend import get_solver
sage: p = get_solver(solver = "CVXOPT")                 # optional - cvxopt
sage: p.problem_name()                                  # optional - cvxopt
''
sage: p.problem_name("There once was a french fry")     # optional - cvxopt
sage: print(p.problem_name())                           # optional - cvxopt
There once was a french fry
row(i)

Return a row

INPUT:

  • index (integer) – the constraint’s id.

OUTPUT:

A pair (indices, coeffs) where indices lists the entries whose coefficient is nonzero, and to which coeffs associates their coefficient on the model of the add_linear_constraint method.

EXAMPLES:

sage: from sage.numerical.backends.generic_backend import get_solver
sage: p = get_solver(solver = "CVXOPT")                 # optional - cvxopt
sage: p.add_variables(5)                                # optional - cvxopt
4
sage: p.add_linear_constraint(list(zip(range(5), range(5))), 2, 2)  # optional - cvxopt
sage: p.row(0)                                          # optional - cvxopt
([1, 2, 3, 4], [1, 2, 3, 4])
sage: p.row_bounds(0)                                   # optional - cvxopt
(2, 2)
row_bounds(index)

Return the bounds of a specific constraint.

INPUT:

  • index (integer) – the constraint’s id.

OUTPUT:

A pair (lower_bound, upper_bound). Each of them can be set to None if the constraint is not bounded in the corresponding direction, and is a real value otherwise.

EXAMPLES:

sage: from sage.numerical.backends.generic_backend import get_solver
sage: p = get_solver(solver = "CVXOPT")                 # optional - cvxopt
sage: p.add_variables(5)                                # optional - cvxopt
4
sage: p.add_linear_constraint(list(zip(range(5), range(5))), 2, 2)  # optional - cvxopt
sage: p.row(0)                                          # optional - cvxopt
([1, 2, 3, 4], [1, 2, 3, 4])
sage: p.row_bounds(0)                                   # optional - cvxopt
(2, 2)
row_name(index)

Return the index th row name

INPUT:

  • index (integer) – the row’s id

EXAMPLES:

sage: from sage.numerical.backends.generic_backend import get_solver
sage: p = get_solver(solver = "CVXOPT")                 # optional - cvxopt
sage: p.add_linear_constraints(1, 2, None, names=["Empty constraint 1"])  # optional - cvxopt
sage: p.row_name(0)                                     # optional - cvxopt
'Empty constraint 1'
set_objective(coeff, d=0.0)

Set the objective function.

INPUT:

  • coeff – a list of real values, whose ith element is the coefficient of the ith variable in the objective function.

  • d (double) – the constant term in the linear function (set to \(0\) by default)

EXAMPLES:

sage: from sage.numerical.backends.generic_backend import get_solver    # optional - cvxopt
sage: p = get_solver(solver = "CVXOPT")                 # optional - cvxopt
sage: p.add_variables(5)                                # optional - cvxopt
4
sage: p.set_objective([1, 1, 2, 1, 3])                  # optional - cvxopt
sage: [p.objective_coefficient(x) for x in range(5)]    # optional - cvxopt
[1, 1, 2, 1, 3]
set_sense(sense)

Set the direction (maximization/minimization).

INPUT:

  • sense (integer) :

    • +1 => Maximization

    • -1 => Minimization

EXAMPLES:

sage: from sage.numerical.backends.generic_backend import get_solver
sage: p = get_solver(solver = "CVXOPT")                 # optional - cvxopt
sage: p.is_maximization()                               # optional - cvxopt
True
sage: p.set_sense(-1)                                   # optional - cvxopt
sage: p.is_maximization()                               # optional - cvxopt
False
set_variable_type(variable, vtype)

Set the type of a variable.

EXAMPLES:

sage: from sage.numerical.backends.generic_backend import get_solver
sage: p = get_solver(solver = "cvxopt")                 # optional - cvxopt
sage: p.add_variables(5)                                # optional - cvxopt
4
sage: p.set_variable_type(3, -1)                        # optional - cvxopt
sage: p.set_variable_type(3, -2)                        # optional - cvxopt
Traceback (most recent call last):
...
ValueError: ...
set_verbosity(level)

Does not apply for the cvxopt solver

solve()

Solve the problem.

Note

This method raises MIPSolverException exceptions when the solution cannot be computed for any reason (none exists, or the LP solver was not able to find it, etc…)

EXAMPLES:

sage: p = MixedIntegerLinearProgram(solver = "cvxopt", maximization=False)  # optional - cvxopt
sage: x=p.new_variable(nonnegative=True)                # optional - cvxopt
sage: p.set_objective(-4*x[0] - 5*x[1])                 # optional - cvxopt
sage: p.add_constraint(2*x[0] + x[1] <= 3)              # optional - cvxopt
sage: p.add_constraint(2*x[1] + x[0] <= 3)              # optional - cvxopt
sage: N(p.solve(), digits=2)                            # optional - cvxopt
-9.0
sage: p = MixedIntegerLinearProgram(solver = "cvxopt", maximization=False)  # optional - cvxopt
sage: x=p.new_variable(nonnegative=True)                # optional - cvxopt
sage: p.set_objective(x[0] + 2*x[1])                    # optional - cvxopt
sage: p.add_constraint(-5*x[0] + x[1]  <=   7)          # optional - cvxopt
sage: p.add_constraint(-5*x[0] + x[1]  >=   7)          # optional - cvxopt
sage: p.add_constraint(x[0] + x[1] >= 26  )             # optional - cvxopt
sage: p.add_constraint( x[0] >= 3)                      # optional - cvxopt
sage: p.add_constraint( x[1] >= 4)                      # optional - cvxopt
sage: N(p.solve(),digits=4)                             # optional - cvxopt
48.83
sage: p = MixedIntegerLinearProgram(solver = "cvxopt")  # optional - cvxopt
sage: x=p.new_variable(nonnegative=True)                # optional - cvxopt
sage: p.set_objective(x[0] + x[1] + 3*x[2])             # optional - cvxopt
sage: p.solver_parameter("show_progress",True)          # optional - cvxopt
sage: p.add_constraint(x[0] + 2*x[1] <= 4)              # optional - cvxopt
sage: p.add_constraint(5*x[2] - x[1] <= 8)              # optional - cvxopt
sage: N(p.solve(), digits=2)                            # optional - cvxopt
         pcost       dcost       gap    pres   dres   k/t
     ...
    8.8
sage: #CVXOPT gives different  values for variables compared to the other solvers.
sage: c = MixedIntegerLinearProgram(solver = "cvxopt")  # optional - cvxopt
sage: p = MixedIntegerLinearProgram(solver = "ppl")     # optional - cvxopt
sage: g = MixedIntegerLinearProgram()                   # optional - cvxopt
sage: xc=c.new_variable(nonnegative=True)               # optional - cvxopt
sage: xp=p.new_variable(nonnegative=True)               # optional - cvxopt
sage: xg=g.new_variable(nonnegative=True)               # optional - cvxopt
sage: c.set_objective(xc[2])                            # optional - cvxopt
sage: p.set_objective(xp[2])                            # optional - cvxopt
sage: g.set_objective(xg[2])                            # optional - cvxopt
sage: #we create a cube for all three solvers
sage: c.add_constraint(xc[0] <= 100)                    # optional - cvxopt
sage: c.add_constraint(xc[1] <= 100)                    # optional - cvxopt
sage: c.add_constraint(xc[2] <= 100)                    # optional - cvxopt
sage: p.add_constraint(xp[0] <= 100)                    # optional - cvxopt
sage: p.add_constraint(xp[1] <= 100)                    # optional - cvxopt
sage: p.add_constraint(xp[2] <= 100)                    # optional - cvxopt
sage: g.add_constraint(xg[0] <= 100)                    # optional - cvxopt
sage: g.add_constraint(xg[1] <= 100)                    # optional - cvxopt
sage: g.add_constraint(xg[2] <= 100)                    # optional - cvxopt
sage: N(c.solve(),digits=4)                             # optional - cvxopt
100.0
sage: N(c.get_values(xc[0]),digits=3)                   # optional - cvxopt
50.0
sage: N(c.get_values(xc[1]),digits=3)                   # optional - cvxopt
50.0
sage: N(c.get_values(xc[2]),digits=4)                   # optional - cvxopt
100.0
sage: N(p.solve(),digits=4)                             # optional - cvxopt
100.0
sage: N(p.get_values(xp[0]),2)                          # optional - cvxopt
0.00
sage: N(p.get_values(xp[1]),2)                          # optional - cvxopt
0.00
sage: N(p.get_values(xp[2]),digits=4)                   # optional - cvxopt
100.0
sage: N(g.solve(),digits=4)                             # optional - cvxopt
100.0
sage: N(g.get_values(xg[0]),2)                          # optional - cvxopt
0.00
sage: N(g.get_values(xg[1]),2)                          # optional - cvxopt
0.00
sage: N(g.get_values(xg[2]),digits=4)                   # optional - cvxopt
100.0
solver_parameter(name, value=None)

Return or define a solver parameter

INPUT:

  • name (string) – the parameter

  • value – the parameter’s value if it is to be defined, or None (default) to obtain its current value.

Note

The list of available parameters is available at solver_parameter().

EXAMPLES:

sage: from sage.numerical.backends.generic_backend import get_solver
sage: p = get_solver(solver="CVXOPT")                   # optional - cvxopt
sage: p.solver_parameter("show_progress")               # optional - cvxopt
False
sage: p.solver_parameter("show_progress", True)         # optional - cvxopt
sage: p.solver_parameter("show_progress")               # optional - cvxopt
True
variable_lower_bound(index, value=None)

Return or define the lower bound on a variable

INPUT:

  • index (integer) – the variable’s id

  • value – real value, or None to mean that the variable has not lower bound. When set to None (default), the method returns the current value.

EXAMPLES:

sage: from sage.numerical.backends.generic_backend import get_solver
sage: p = get_solver(solver = "CVXOPT")                 # optional - cvxopt
sage: p.add_variable()                                  # optional - cvxopt
0
sage: p.col_bounds(0)                                   # optional - cvxopt
(0.0, None)
sage: p.variable_lower_bound(0, 5)                      # optional - cvxopt
sage: p.col_bounds(0)                                   # optional - cvxopt
(5, None)
variable_upper_bound(index, value=None)

Return or define the upper bound on a variable

INPUT:

  • index (integer) – the variable’s id

  • value – real value, or None to mean that the variable has not upper bound. When set to None (default), the method returns the current value.

EXAMPLES:

sage: from sage.numerical.backends.generic_backend import get_solver
sage: p = get_solver(solver = "CVXOPT")                 # optional - cvxopt
sage: p.add_variable()                                  # optional - cvxopt
0
sage: p.col_bounds(0)                                   # optional - cvxopt
(0.0, None)
sage: p.variable_upper_bound(0, 5)                      # optional - cvxopt
sage: p.col_bounds(0)                                   # optional - cvxopt
(0.0, 5)