InteractiveLP Backend¶

AUTHORS:

Nathann Cohen (2010-10) : generic_backend template
Matthias Koeppe (2016-03) : this backend

class sage.numerical.backends.interactivelp_backend.InteractiveLPBackend[source]¶

Bases: GenericBackend

MIP Backend that works with InteractiveLPProblem.

This backend should be used only for linear programs over general fields, or for educational purposes. For fast computations with floating point arithmetic, use one of the numerical backends. For exact computations with rational numbers, use backend ‘PPL’.

There is no support for integer variables.

EXAMPLES:

Sage

sage: from sage.numerical.backends.generic_backend import get_solver
sage: p = get_solver(solver = "InteractiveLP")

Python

>>> from sage.all import *
>>> from sage.numerical.backends.generic_backend import get_solver
>>> p = get_solver(solver = "InteractiveLP")

Sage Live

from sage.numerical.backends.generic_backend import get_solver
p = get_solver(solver = "InteractiveLP")

add_col(indices, coeffs)[source]¶

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 i-th entry of coeffs corresponds to the coefficient of the variable in the constraint represented by the i-th entry in indices.

Note

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

EXAMPLES:

Sage

sage: from sage.numerical.backends.generic_backend import get_solver
sage: p = get_solver(solver = "InteractiveLP")
sage: p.ncols()
0
sage: p.nrows()
0
sage: p.add_linear_constraints(5, 0, None)
sage: p.add_col(list(range(5)), list(range(5)))
sage: p.nrows()
5

Python

>>> from sage.all import *
>>> from sage.numerical.backends.generic_backend import get_solver
>>> p = get_solver(solver = "InteractiveLP")
>>> p.ncols()
0
>>> p.nrows()
0
>>> p.add_linear_constraints(Integer(5), Integer(0), None)
>>> p.add_col(list(range(Integer(5))), list(range(Integer(5))))
>>> p.nrows()
5

Sage Live

from sage.numerical.backends.generic_backend import get_solver
p = get_solver(solver = "InteractiveLP")
p.ncols()
p.nrows()
p.add_linear_constraints(5, 0, None)
p.add_col(list(range(5)), list(range(5)))
p.nrows()

add_linear_constraint(coefficients, lower_bound, upper_bound, name=None)[source]¶

Add a linear constraint.

INPUT:

coefficients – an iterable of pairs (i, v). In each pair, i is a variable index (integer) and v is a value (element of base_ring()).
lower_bound – element of base_ring() or None; the lower bound
upper_bound – element of base_ring() or None; the upper bound
name – string or None; optional name for this row

EXAMPLES:

Sage

sage: from sage.numerical.backends.generic_backend import get_solver
sage: p = get_solver(solver = "InteractiveLP")
sage: p.add_variables(5)
4
sage: p.add_linear_constraint( zip(range(5), range(5)), 2, 2)
sage: p.row(0)
([1, 2, 3, 4], [1, 2, 3, 4])
sage: p.row_bounds(0)
(2, 2)
sage: p.add_linear_constraint( zip(range(5), range(5)), 1, 1, name='foo')
sage: p.row_name(1)
'foo'

Python

>>> from sage.all import *
>>> from sage.numerical.backends.generic_backend import get_solver
>>> p = get_solver(solver = "InteractiveLP")
>>> p.add_variables(Integer(5))
4
>>> p.add_linear_constraint( zip(range(Integer(5)), range(Integer(5))), Integer(2), Integer(2))
>>> p.row(Integer(0))
([1, 2, 3, 4], [1, 2, 3, 4])
>>> p.row_bounds(Integer(0))
(2, 2)
>>> p.add_linear_constraint( zip(range(Integer(5)), range(Integer(5))), Integer(1), Integer(1), name='foo')
>>> p.row_name(Integer(1))
'foo'

Sage Live

from sage.numerical.backends.generic_backend import get_solver
p = get_solver(solver = "InteractiveLP")
p.add_variables(5)
p.add_linear_constraint( zip(range(5), range(5)), 2, 2)
p.row(0)
p.row_bounds(0)
p.add_linear_constraint( zip(range(5), range(5)), 1, 1, name='foo')
p.row_name(1)

add_variable(lower_bound=0, upper_bound=None, binary=False, continuous=True, integer=False, obj=None, name=None, coefficients=None)[source]¶

Add a variable.

This amounts to adding a new column to the matrix. By default, the variable is both nonnegative and real.

In this backend, variables are always continuous (real). If integer variables are requested via the parameters binary and integer, an error will be raised.

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 integral (default: False)
obj – (optional) coefficient of this variable in the objective function (default: 0)
name – an optional name for the newly added variable (default: None)
coefficients – (optional) an iterable of pairs (i, v). In each pair, i is a variable index (integer) and v is a value (element of base_ring()).

OUTPUT: the index of the newly created variable

EXAMPLES:

Sage

sage: from sage.numerical.backends.generic_backend import get_solver
sage: p = get_solver(solver = "InteractiveLP")
sage: p.ncols()
0
sage: p.add_variable()
0
sage: p.ncols()
1
sage: p.add_variable(continuous=True, integer=True)
Traceback (most recent call last):
...
ValueError: ...
sage: p.add_variable(name='x',obj=1)
1
sage: p.col_name(1)
'x'
sage: p.objective_coefficient(1)
1

Python

>>> from sage.all import *
>>> from sage.numerical.backends.generic_backend import get_solver
>>> p = get_solver(solver = "InteractiveLP")
>>> p.ncols()
0
>>> p.add_variable()
0
>>> p.ncols()
1
>>> p.add_variable(continuous=True, integer=True)
Traceback (most recent call last):
...
ValueError: ...
>>> p.add_variable(name='x',obj=Integer(1))
1
>>> p.col_name(Integer(1))
'x'
>>> p.objective_coefficient(Integer(1))
1

Sage Live

from sage.numerical.backends.generic_backend import get_solver
p = get_solver(solver = "InteractiveLP")
p.ncols()
p.add_variable()
p.ncols()
p.add_variable(continuous=True, integer=True)
p.add_variable(name='x',obj=1)
p.col_name(1)
p.objective_coefficient(1)

base_ring()[source]¶

Return the base ring.

OUTPUT: a ring; the coefficients that the chosen solver supports

EXAMPLES:

Sage

sage: from sage.numerical.backends.generic_backend import get_solver
sage: p = get_solver(solver = "InteractiveLP")
sage: p.base_ring()
Rational Field

Python

>>> from sage.all import *
>>> from sage.numerical.backends.generic_backend import get_solver
>>> p = get_solver(solver = "InteractiveLP")
>>> p.base_ring()
Rational Field

Sage Live

from sage.numerical.backends.generic_backend import get_solver
p = get_solver(solver = "InteractiveLP")
p.base_ring()

col_bounds(index)[source]¶

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

sage: from sage.numerical.backends.generic_backend import get_solver
sage: p = get_solver(solver = "InteractiveLP")
sage: p.add_variable(lower_bound=None)
0
sage: p.col_bounds(0)
(None, None)
sage: p.variable_lower_bound(0, 0)
sage: p.col_bounds(0)
(0, None)

Python

>>> from sage.all import *
>>> from sage.numerical.backends.generic_backend import get_solver
>>> p = get_solver(solver = "InteractiveLP")
>>> p.add_variable(lower_bound=None)
0
>>> p.col_bounds(Integer(0))
(None, None)
>>> p.variable_lower_bound(Integer(0), Integer(0))
>>> p.col_bounds(Integer(0))
(0, None)

Sage Live

from sage.numerical.backends.generic_backend import get_solver
p = get_solver(solver = "InteractiveLP")
p.add_variable(lower_bound=None)
p.col_bounds(0)
p.variable_lower_bound(0, 0)
p.col_bounds(0)

col_name(index)[source]¶

Return the index-th column name.

INPUT:

index – integer; the column id
name – (char *) its name; when set to NULL (default), the method returns the current name

EXAMPLES:

Sage

sage: from sage.numerical.backends.generic_backend import get_solver
sage: p = get_solver(solver = "InteractiveLP")
sage: p.add_variable(name='I_am_a_variable')
0
sage: p.col_name(0)
'I_am_a_variable'

Python

>>> from sage.all import *
>>> from sage.numerical.backends.generic_backend import get_solver
>>> p = get_solver(solver = "InteractiveLP")
>>> p.add_variable(name='I_am_a_variable')
0
>>> p.col_name(Integer(0))
'I_am_a_variable'

Sage Live

from sage.numerical.backends.generic_backend import get_solver
p = get_solver(solver = "InteractiveLP")
p.add_variable(name='I_am_a_variable')
p.col_name(0)

dictionary()[source]¶

Return a dictionary representing the current basis.

EXAMPLES:

Sage

sage: p = MixedIntegerLinearProgram(maximization=True,                                                solver='InteractiveLP')
sage: x = p.new_variable(nonnegative=True)
sage: p.add_constraint(-x[0] + x[1] <= 2)
sage: p.add_constraint(8 * x[0] + 2 * x[1] <= 17)
sage: p.set_objective(11/2 * x[0] - 3 * x[1])
sage: b = p.get_backend()
sage: # Backend-specific commands to instruct solver to use simplex method here
sage: b.solve()
0
sage: d = b.dictionary(); d
LP problem dictionary ...
sage: set(d.basic_variables())
{x1, x3}
sage: d.basic_solution()
(17/8, 0)

Python

>>> from sage.all import *
>>> p = MixedIntegerLinearProgram(maximization=True,                                                solver='InteractiveLP')
>>> x = p.new_variable(nonnegative=True)
>>> p.add_constraint(-x[Integer(0)] + x[Integer(1)] <= Integer(2))
>>> p.add_constraint(Integer(8) * x[Integer(0)] + Integer(2) * x[Integer(1)] <= Integer(17))
>>> p.set_objective(Integer(11)/Integer(2) * x[Integer(0)] - Integer(3) * x[Integer(1)])
>>> b = p.get_backend()
>>> # Backend-specific commands to instruct solver to use simplex method here
>>> b.solve()
0
>>> d = b.dictionary(); d
LP problem dictionary ...
>>> set(d.basic_variables())
{x1, x3}
>>> d.basic_solution()
(17/8, 0)

Sage Live

p = MixedIntegerLinearProgram(maximization=True,                                                solver='InteractiveLP')
x = p.new_variable(nonnegative=True)
p.add_constraint(-x[0] + x[1] <= 2)
p.add_constraint(8 * x[0] + 2 * x[1] <= 17)
p.set_objective(11/2 * x[0] - 3 * x[1])
b = p.get_backend()
# Backend-specific commands to instruct solver to use simplex method here
b.solve()
d = b.dictionary(); d
set(d.basic_variables())
d.basic_solution()

get_objective_value()[source]¶

Return the value of the objective function.

Note

Behavior is undefined unless solve has been called before.

EXAMPLES:

Sage

sage: from sage.numerical.backends.generic_backend import get_solver
sage: p = get_solver(solver = "InteractiveLP")
sage: p.add_variables(2)
1
sage: p.add_linear_constraint([(0,1), (1,2)], None, 3)
sage: p.set_objective([2, 5])
sage: p.solve()
0
sage: p.get_objective_value()
15/2
sage: p.get_variable_value(0)
0
sage: p.get_variable_value(1)
3/2

Python

>>> from sage.all import *
>>> from sage.numerical.backends.generic_backend import get_solver
>>> p = get_solver(solver = "InteractiveLP")
>>> p.add_variables(Integer(2))
1
>>> p.add_linear_constraint([(Integer(0),Integer(1)), (Integer(1),Integer(2))], None, Integer(3))
>>> p.set_objective([Integer(2), Integer(5)])
>>> p.solve()
0
>>> p.get_objective_value()
15/2
>>> p.get_variable_value(Integer(0))
0
>>> p.get_variable_value(Integer(1))
3/2

Sage Live

from sage.numerical.backends.generic_backend import get_solver
p = get_solver(solver = "InteractiveLP")
p.add_variables(2)
p.add_linear_constraint([(0,1), (1,2)], None, 3)
p.set_objective([2, 5])
p.solve()
p.get_objective_value()
p.get_variable_value(0)
p.get_variable_value(1)

get_variable_value(variable)[source]¶

Return the value of a variable given by the solver.

Note

Behavior is undefined unless solve has been called before.

EXAMPLES:

Sage

sage: from sage.numerical.backends.generic_backend import get_solver
sage: p = get_solver(solver = "InteractiveLP")
sage: p.add_variables(2)
1
sage: p.add_linear_constraint([(0,1), (1, 2)], None, 3)
sage: p.set_objective([2, 5])
sage: p.solve()
0
sage: p.get_objective_value()
15/2
sage: p.get_variable_value(0)
0
sage: p.get_variable_value(1)
3/2

Python

>>> from sage.all import *
>>> from sage.numerical.backends.generic_backend import get_solver
>>> p = get_solver(solver = "InteractiveLP")
>>> p.add_variables(Integer(2))
1
>>> p.add_linear_constraint([(Integer(0),Integer(1)), (Integer(1), Integer(2))], None, Integer(3))
>>> p.set_objective([Integer(2), Integer(5)])
>>> p.solve()
0
>>> p.get_objective_value()
15/2
>>> p.get_variable_value(Integer(0))
0
>>> p.get_variable_value(Integer(1))
3/2

Sage Live

from sage.numerical.backends.generic_backend import get_solver
p = get_solver(solver = "InteractiveLP")
p.add_variables(2)
p.add_linear_constraint([(0,1), (1, 2)], None, 3)
p.set_objective([2, 5])
p.solve()
p.get_objective_value()
p.get_variable_value(0)
p.get_variable_value(1)

interactive_lp_problem()[source]¶

Return the InteractiveLPProblem object associated with this backend.

EXAMPLES:

Sage

sage: p = MixedIntegerLinearProgram(maximization=True,                                                solver='InteractiveLP')
sage: x = p.new_variable(nonnegative=True)
sage: p.add_constraint(-x[0] + x[1] <= 2)
sage: p.add_constraint(8 * x[0] + 2 * x[1] <= 17)
sage: p.set_objective(11/2 * x[0] - 3 * x[1])
sage: b = p.get_backend()
sage: b.interactive_lp_problem()
LP problem ...

Python

>>> from sage.all import *
>>> p = MixedIntegerLinearProgram(maximization=True,                                                solver='InteractiveLP')
>>> x = p.new_variable(nonnegative=True)
>>> p.add_constraint(-x[Integer(0)] + x[Integer(1)] <= Integer(2))
>>> p.add_constraint(Integer(8) * x[Integer(0)] + Integer(2) * x[Integer(1)] <= Integer(17))
>>> p.set_objective(Integer(11)/Integer(2) * x[Integer(0)] - Integer(3) * x[Integer(1)])
>>> b = p.get_backend()
>>> b.interactive_lp_problem()
LP problem ...

Sage Live

p = MixedIntegerLinearProgram(maximization=True,                                                solver='InteractiveLP')
x = p.new_variable(nonnegative=True)
p.add_constraint(-x[0] + x[1] <= 2)
p.add_constraint(8 * x[0] + 2 * x[1] <= 17)
p.set_objective(11/2 * x[0] - 3 * x[1])
b = p.get_backend()
b.interactive_lp_problem()

is_maximization()[source]¶

Test whether the problem is a maximization

EXAMPLES:

Sage

sage: from sage.numerical.backends.generic_backend import get_solver
sage: p = get_solver(solver = "InteractiveLP")
sage: p.is_maximization()
True
sage: p.set_sense(-1)
sage: p.is_maximization()
False

Python

>>> from sage.all import *
>>> from sage.numerical.backends.generic_backend import get_solver
>>> p = get_solver(solver = "InteractiveLP")
>>> p.is_maximization()
True
>>> p.set_sense(-Integer(1))
>>> p.is_maximization()
False

Sage Live

from sage.numerical.backends.generic_backend import get_solver
p = get_solver(solver = "InteractiveLP")
p.is_maximization()
p.set_sense(-1)
p.is_maximization()

is_slack_variable_basic(index)[source]¶

Test whether the slack variable of the given row is basic.

This assumes that the problem has been solved with the simplex method and a basis is available. Otherwise an exception will be raised.

INPUT:

index – integer; the variable’s id

EXAMPLES:

Sage

sage: p = MixedIntegerLinearProgram(maximization=True,                                                solver='InteractiveLP')
sage: x = p.new_variable(nonnegative=True)
sage: p.add_constraint(-x[0] + x[1] <= 2)
sage: p.add_constraint(8 * x[0] + 2 * x[1] <= 17)
sage: p.set_objective(11/2 * x[0] - 3 * x[1])
sage: b = p.get_backend()
sage: # Backend-specific commands to instruct solver to use simplex method here
sage: b.solve()
0
sage: b.is_slack_variable_basic(0)
True
sage: b.is_slack_variable_basic(1)
False

Python

>>> from sage.all import *
>>> p = MixedIntegerLinearProgram(maximization=True,                                                solver='InteractiveLP')
>>> x = p.new_variable(nonnegative=True)
>>> p.add_constraint(-x[Integer(0)] + x[Integer(1)] <= Integer(2))
>>> p.add_constraint(Integer(8) * x[Integer(0)] + Integer(2) * x[Integer(1)] <= Integer(17))
>>> p.set_objective(Integer(11)/Integer(2) * x[Integer(0)] - Integer(3) * x[Integer(1)])
>>> b = p.get_backend()
>>> # Backend-specific commands to instruct solver to use simplex method here
>>> b.solve()
0
>>> b.is_slack_variable_basic(Integer(0))
True
>>> b.is_slack_variable_basic(Integer(1))
False

Sage Live

p = MixedIntegerLinearProgram(maximization=True,                                                solver='InteractiveLP')
x = p.new_variable(nonnegative=True)
p.add_constraint(-x[0] + x[1] <= 2)
p.add_constraint(8 * x[0] + 2 * x[1] <= 17)
p.set_objective(11/2 * x[0] - 3 * x[1])
b = p.get_backend()
# Backend-specific commands to instruct solver to use simplex method here
b.solve()
b.is_slack_variable_basic(0)
b.is_slack_variable_basic(1)

is_slack_variable_nonbasic_at_lower_bound(index)[source]¶

Test whether the given variable is nonbasic at lower bound.

This assumes that the problem has been solved with the simplex method and a basis is available. Otherwise an exception will be raised.

INPUT:

index – integer; the variable’s id

EXAMPLES:

Sage

sage: p = MixedIntegerLinearProgram(maximization=True,                                                solver='InteractiveLP')
sage: x = p.new_variable(nonnegative=True)
sage: p.add_constraint(-x[0] + x[1] <= 2)
sage: p.add_constraint(8 * x[0] + 2 * x[1] <= 17)
sage: p.set_objective(11/2 * x[0] - 3 * x[1])
sage: b = p.get_backend()
sage: # Backend-specific commands to instruct solver to use simplex method here
sage: b.solve()
0
sage: b.is_slack_variable_nonbasic_at_lower_bound(0)
False
sage: b.is_slack_variable_nonbasic_at_lower_bound(1)
True

Python

>>> from sage.all import *
>>> p = MixedIntegerLinearProgram(maximization=True,                                                solver='InteractiveLP')
>>> x = p.new_variable(nonnegative=True)
>>> p.add_constraint(-x[Integer(0)] + x[Integer(1)] <= Integer(2))
>>> p.add_constraint(Integer(8) * x[Integer(0)] + Integer(2) * x[Integer(1)] <= Integer(17))
>>> p.set_objective(Integer(11)/Integer(2) * x[Integer(0)] - Integer(3) * x[Integer(1)])
>>> b = p.get_backend()
>>> # Backend-specific commands to instruct solver to use simplex method here
>>> b.solve()
0
>>> b.is_slack_variable_nonbasic_at_lower_bound(Integer(0))
False
>>> b.is_slack_variable_nonbasic_at_lower_bound(Integer(1))
True

Sage Live

p = MixedIntegerLinearProgram(maximization=True,                                                solver='InteractiveLP')
x = p.new_variable(nonnegative=True)
p.add_constraint(-x[0] + x[1] <= 2)
p.add_constraint(8 * x[0] + 2 * x[1] <= 17)
p.set_objective(11/2 * x[0] - 3 * x[1])
b = p.get_backend()
# Backend-specific commands to instruct solver to use simplex method here
b.solve()
b.is_slack_variable_nonbasic_at_lower_bound(0)
b.is_slack_variable_nonbasic_at_lower_bound(1)

is_variable_basic(index)[source]¶

Test whether the given variable is basic.

This assumes that the problem has been solved with the simplex method and a basis is available. Otherwise an exception will be raised.

INPUT:

index – integer; the variable’s id

EXAMPLES:

Sage

sage: p = MixedIntegerLinearProgram(maximization=True,                                                solver='InteractiveLP')
sage: x = p.new_variable(nonnegative=True)
sage: p.add_constraint(-x[0] + x[1] <= 2)
sage: p.add_constraint(8 * x[0] + 2 * x[1] <= 17)
sage: p.set_objective(11/2 * x[0] - 3 * x[1])
sage: b = p.get_backend()
sage: # Backend-specific commands to instruct solver to use simplex method here
sage: b.solve()
0
sage: b.is_variable_basic(0)
True
sage: b.is_variable_basic(1)
False

Python

>>> from sage.all import *
>>> p = MixedIntegerLinearProgram(maximization=True,                                                solver='InteractiveLP')
>>> x = p.new_variable(nonnegative=True)
>>> p.add_constraint(-x[Integer(0)] + x[Integer(1)] <= Integer(2))
>>> p.add_constraint(Integer(8) * x[Integer(0)] + Integer(2) * x[Integer(1)] <= Integer(17))
>>> p.set_objective(Integer(11)/Integer(2) * x[Integer(0)] - Integer(3) * x[Integer(1)])
>>> b = p.get_backend()
>>> # Backend-specific commands to instruct solver to use simplex method here
>>> b.solve()
0
>>> b.is_variable_basic(Integer(0))
True
>>> b.is_variable_basic(Integer(1))
False

Sage Live

p = MixedIntegerLinearProgram(maximization=True,                                                solver='InteractiveLP')
x = p.new_variable(nonnegative=True)
p.add_constraint(-x[0] + x[1] <= 2)
p.add_constraint(8 * x[0] + 2 * x[1] <= 17)
p.set_objective(11/2 * x[0] - 3 * x[1])
b = p.get_backend()
# Backend-specific commands to instruct solver to use simplex method here
b.solve()
b.is_variable_basic(0)
b.is_variable_basic(1)

is_variable_binary(index)[source]¶

Test whether the given variable is of binary type.

INPUT:

index – integer; the variable’s id

EXAMPLES:

Sage

sage: from sage.numerical.backends.generic_backend import get_solver
sage: p = get_solver(solver = "InteractiveLP")
sage: p.ncols()
0
sage: p.add_variable()
0
sage: p.is_variable_binary(0)
False

Python

>>> from sage.all import *
>>> from sage.numerical.backends.generic_backend import get_solver
>>> p = get_solver(solver = "InteractiveLP")
>>> p.ncols()
0
>>> p.add_variable()
0
>>> p.is_variable_binary(Integer(0))
False

Sage Live

from sage.numerical.backends.generic_backend import get_solver
p = get_solver(solver = "InteractiveLP")
p.ncols()
p.add_variable()
p.is_variable_binary(0)

is_variable_continuous(index)[source]¶

Test whether the given variable is of continuous/real type.

INPUT:

index – integer; the variable’s id

EXAMPLES:

Sage

sage: from sage.numerical.backends.generic_backend import get_solver
sage: p = get_solver(solver = "InteractiveLP")
sage: p.ncols()
0
sage: p.add_variable()
0
sage: p.is_variable_continuous(0)
True

Python

>>> from sage.all import *
>>> from sage.numerical.backends.generic_backend import get_solver
>>> p = get_solver(solver = "InteractiveLP")
>>> p.ncols()
0
>>> p.add_variable()
0
>>> p.is_variable_continuous(Integer(0))
True

Sage Live

from sage.numerical.backends.generic_backend import get_solver
p = get_solver(solver = "InteractiveLP")
p.ncols()
p.add_variable()
p.is_variable_continuous(0)

is_variable_integer(index)[source]¶

Test whether the given variable is of integer type.

INPUT:

index – integer; the variable’s id

EXAMPLES:

Sage

sage: from sage.numerical.backends.generic_backend import get_solver
sage: p = get_solver(solver = "InteractiveLP")
sage: p.ncols()
0
sage: p.add_variable()
0
sage: p.is_variable_integer(0)
False

Python

>>> from sage.all import *
>>> from sage.numerical.backends.generic_backend import get_solver
>>> p = get_solver(solver = "InteractiveLP")
>>> p.ncols()
0
>>> p.add_variable()
0
>>> p.is_variable_integer(Integer(0))
False

Sage Live

from sage.numerical.backends.generic_backend import get_solver
p = get_solver(solver = "InteractiveLP")
p.ncols()
p.add_variable()
p.is_variable_integer(0)

is_variable_nonbasic_at_lower_bound(index)[source]¶

Test whether the given variable is nonbasic at lower bound.

This assumes that the problem has been solved with the simplex method and a basis is available. Otherwise an exception will be raised.

INPUT:

index – integer; the variable’s id

EXAMPLES:

Sage

sage: p = MixedIntegerLinearProgram(maximization=True,                                                solver='InteractiveLP')
sage: x = p.new_variable(nonnegative=True)
sage: p.add_constraint(-x[0] + x[1] <= 2)
sage: p.add_constraint(8 * x[0] + 2 * x[1] <= 17)
sage: p.set_objective(11/2 * x[0] - 3 * x[1])
sage: b = p.get_backend()
sage: # Backend-specific commands to instruct solver to use simplex method here
sage: b.solve()
0
sage: b.is_variable_nonbasic_at_lower_bound(0)
False
sage: b.is_variable_nonbasic_at_lower_bound(1)
True

Python

>>> from sage.all import *
>>> p = MixedIntegerLinearProgram(maximization=True,                                                solver='InteractiveLP')
>>> x = p.new_variable(nonnegative=True)
>>> p.add_constraint(-x[Integer(0)] + x[Integer(1)] <= Integer(2))
>>> p.add_constraint(Integer(8) * x[Integer(0)] + Integer(2) * x[Integer(1)] <= Integer(17))
>>> p.set_objective(Integer(11)/Integer(2) * x[Integer(0)] - Integer(3) * x[Integer(1)])
>>> b = p.get_backend()
>>> # Backend-specific commands to instruct solver to use simplex method here
>>> b.solve()
0
>>> b.is_variable_nonbasic_at_lower_bound(Integer(0))
False
>>> b.is_variable_nonbasic_at_lower_bound(Integer(1))
True

Sage Live

p = MixedIntegerLinearProgram(maximization=True,                                                solver='InteractiveLP')
x = p.new_variable(nonnegative=True)
p.add_constraint(-x[0] + x[1] <= 2)
p.add_constraint(8 * x[0] + 2 * x[1] <= 17)
p.set_objective(11/2 * x[0] - 3 * x[1])
b = p.get_backend()
# Backend-specific commands to instruct solver to use simplex method here
b.solve()
b.is_variable_nonbasic_at_lower_bound(0)
b.is_variable_nonbasic_at_lower_bound(1)

ncols()[source]¶

Return the number of columns/variables.

EXAMPLES:

Sage

sage: from sage.numerical.backends.generic_backend import get_solver
sage: p = get_solver(solver = "InteractiveLP")
sage: p.ncols()
0
sage: p.add_variables(2)
1
sage: p.ncols()
2

Python

>>> from sage.all import *
>>> from sage.numerical.backends.generic_backend import get_solver
>>> p = get_solver(solver = "InteractiveLP")
>>> p.ncols()
0
>>> p.add_variables(Integer(2))
1
>>> p.ncols()
2

Sage Live

from sage.numerical.backends.generic_backend import get_solver
p = get_solver(solver = "InteractiveLP")
p.ncols()
p.add_variables(2)
p.ncols()

nrows()[source]¶

Return the number of rows/constraints.

EXAMPLES:

Sage

sage: from sage.numerical.backends.generic_backend import get_solver
sage: p = get_solver(solver = "InteractiveLP")
sage: p.nrows()
0
sage: p.add_linear_constraints(2, 0, None)
sage: p.nrows()
2

Python

>>> from sage.all import *
>>> from sage.numerical.backends.generic_backend import get_solver
>>> p = get_solver(solver = "InteractiveLP")
>>> p.nrows()
0
>>> p.add_linear_constraints(Integer(2), Integer(0), None)
>>> p.nrows()
2

Sage Live

from sage.numerical.backends.generic_backend import get_solver
p = get_solver(solver = "InteractiveLP")
p.nrows()
p.add_linear_constraints(2, 0, None)
p.nrows()

objective_coefficient(variable, coeff=None)[source]¶

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

sage: from sage.numerical.backends.generic_backend import get_solver
sage: p = get_solver(solver = "InteractiveLP")
sage: p.add_variable()
0
sage: p.objective_coefficient(0)
0
sage: p.objective_coefficient(0,2)
sage: p.objective_coefficient(0)
2

Python

>>> from sage.all import *
>>> from sage.numerical.backends.generic_backend import get_solver
>>> p = get_solver(solver = "InteractiveLP")
>>> p.add_variable()
0
>>> p.objective_coefficient(Integer(0))
0
>>> p.objective_coefficient(Integer(0),Integer(2))
>>> p.objective_coefficient(Integer(0))
2

Sage Live

from sage.numerical.backends.generic_backend import get_solver
p = get_solver(solver = "InteractiveLP")
p.add_variable()
p.objective_coefficient(0)
p.objective_coefficient(0,2)
p.objective_coefficient(0)

objective_constant_term(d=None)[source]¶

Set or get the constant term in the objective function.

INPUT:

d – double; its coefficient. If None (default), return the current value.

EXAMPLES:

Sage

sage: from sage.numerical.backends.generic_backend import get_solver
sage: p = get_solver(solver = "InteractiveLP")
sage: p.objective_constant_term()
0
sage: p.objective_constant_term(42)
sage: p.objective_constant_term()
42

Python

>>> from sage.all import *
>>> from sage.numerical.backends.generic_backend import get_solver
>>> p = get_solver(solver = "InteractiveLP")
>>> p.objective_constant_term()
0
>>> p.objective_constant_term(Integer(42))
>>> p.objective_constant_term()
42

Sage Live

from sage.numerical.backends.generic_backend import get_solver
p = get_solver(solver = "InteractiveLP")
p.objective_constant_term()
p.objective_constant_term(42)
p.objective_constant_term()

problem_name(name=None)[source]¶

Return or define the problem’s name.

INPUT:

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

EXAMPLES:

Sage

sage: from sage.numerical.backends.generic_backend import get_solver
sage: p = get_solver(solver = "InteractiveLP")
sage: p.problem_name("There_once_was_a_french_fry")
sage: print(p.problem_name())
There_once_was_a_french_fry

Python

>>> from sage.all import *
>>> from sage.numerical.backends.generic_backend import get_solver
>>> p = get_solver(solver = "InteractiveLP")
>>> p.problem_name("There_once_was_a_french_fry")
>>> print(p.problem_name())
There_once_was_a_french_fry

Sage Live

from sage.numerical.backends.generic_backend import get_solver
p = get_solver(solver = "InteractiveLP")
p.problem_name("There_once_was_a_french_fry")
print(p.problem_name())

remove_constraint(i)[source]¶

Remove a constraint.

INPUT:

i – index of the constraint to remove

EXAMPLES:

Sage

sage: p = MixedIntegerLinearProgram(solver='InteractiveLP')
sage: v = p.new_variable(nonnegative=True)
sage: x,y = v[0], v[1]
sage: p.add_constraint(2*x + 3*y, max = 6)
sage: p.add_constraint(3*x + 2*y, max = 6)
sage: p.set_objective(x + y + 7)
sage: p.solve()
47/5
sage: p.remove_constraint(0)
sage: p.solve()
10
sage: p.get_values([x,y])
[0, 3]

Python

>>> from sage.all import *
>>> p = MixedIntegerLinearProgram(solver='InteractiveLP')
>>> v = p.new_variable(nonnegative=True)
>>> x,y = v[Integer(0)], v[Integer(1)]
>>> p.add_constraint(Integer(2)*x + Integer(3)*y, max = Integer(6))
>>> p.add_constraint(Integer(3)*x + Integer(2)*y, max = Integer(6))
>>> p.set_objective(x + y + Integer(7))
>>> p.solve()
47/5
>>> p.remove_constraint(Integer(0))
>>> p.solve()
10
>>> p.get_values([x,y])
[0, 3]

Sage Live

p = MixedIntegerLinearProgram(solver='InteractiveLP')
v = p.new_variable(nonnegative=True)
x,y = v[0], v[1]
p.add_constraint(2*x + 3*y, max = 6)
p.add_constraint(3*x + 2*y, max = 6)
p.set_objective(x + y + 7)
p.solve()
p.remove_constraint(0)
p.solve()
p.get_values([x,y])

row(i)[source]¶

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

sage: from sage.numerical.backends.generic_backend import get_solver
sage: p = get_solver(solver = "InteractiveLP")
sage: p.add_variables(5)
4
sage: p.add_linear_constraint(zip(range(5), range(5)), 0, None)
sage: p.row(0)
([1, 2, 3, 4], [1, 2, 3, 4])

Python

>>> from sage.all import *
>>> from sage.numerical.backends.generic_backend import get_solver
>>> p = get_solver(solver = "InteractiveLP")
>>> p.add_variables(Integer(5))
4
>>> p.add_linear_constraint(zip(range(Integer(5)), range(Integer(5))), Integer(0), None)
>>> p.row(Integer(0))
([1, 2, 3, 4], [1, 2, 3, 4])

Sage Live

from sage.numerical.backends.generic_backend import get_solver
p = get_solver(solver = "InteractiveLP")
p.add_variables(5)
p.add_linear_constraint(zip(range(5), range(5)), 0, None)
p.row(0)

row_bounds(index)[source]¶

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

sage: from sage.numerical.backends.generic_backend import get_solver
sage: p = get_solver(solver = "InteractiveLP")
sage: p.add_variables(5)
4
sage: p.add_linear_constraint(zip(range(5), range(5)), 2, 2)
sage: p.row_bounds(0)
(2, 2)

Python

>>> from sage.all import *
>>> from sage.numerical.backends.generic_backend import get_solver
>>> p = get_solver(solver = "InteractiveLP")
>>> p.add_variables(Integer(5))
4
>>> p.add_linear_constraint(zip(range(Integer(5)), range(Integer(5))), Integer(2), Integer(2))
>>> p.row_bounds(Integer(0))
(2, 2)

Sage Live

from sage.numerical.backends.generic_backend import get_solver
p = get_solver(solver = "InteractiveLP")
p.add_variables(5)
p.add_linear_constraint(zip(range(5), range(5)), 2, 2)
p.row_bounds(0)

row_name(index)[source]¶

Return the index-th row name.

INPUT:

index – integer; the row’s id

EXAMPLES:

Sage

sage: from sage.numerical.backends.generic_backend import get_solver
sage: p = get_solver(solver = "InteractiveLP")
sage: p.add_linear_constraints(1, 2, None, names=['Empty constraint 1'])
sage: p.row_name(0)
'Empty constraint 1'

Python

>>> from sage.all import *
>>> from sage.numerical.backends.generic_backend import get_solver
>>> p = get_solver(solver = "InteractiveLP")
>>> p.add_linear_constraints(Integer(1), Integer(2), None, names=['Empty constraint 1'])
>>> p.row_name(Integer(0))
'Empty constraint 1'

Sage Live

from sage.numerical.backends.generic_backend import get_solver
p = get_solver(solver = "InteractiveLP")
p.add_linear_constraints(1, 2, None, names=['Empty constraint 1'])
p.row_name(0)

set_objective(coeff, d=0)[source]¶

Set the objective function.

INPUT:

coeff – list of real values, whose i-th element is the coefficient of the i-th variable in the objective function
d – real; the constant term in the linear function (set to \(0\) by default)

EXAMPLES:

Sage

sage: from sage.numerical.backends.generic_backend import get_solver
sage: p = get_solver(solver = "InteractiveLP")
sage: p.add_variables(5)
4
sage: p.set_objective([1, 1, 2, 1, 3])
sage: [p.objective_coefficient(x) for x in range(5)]
[1, 1, 2, 1, 3]

Python

>>> from sage.all import *
>>> from sage.numerical.backends.generic_backend import get_solver
>>> p = get_solver(solver = "InteractiveLP")
>>> p.add_variables(Integer(5))
4
>>> p.set_objective([Integer(1), Integer(1), Integer(2), Integer(1), Integer(3)])
>>> [p.objective_coefficient(x) for x in range(Integer(5))]
[1, 1, 2, 1, 3]

Sage Live

from sage.numerical.backends.generic_backend import get_solver
p = get_solver(solver = "InteractiveLP")
p.add_variables(5)
p.set_objective([1, 1, 2, 1, 3])
[p.objective_coefficient(x) for x in range(5)]

Constants in the objective function are respected:

Sage

sage: p = MixedIntegerLinearProgram(solver='InteractiveLP')
sage: x,y = p[0], p[1]
sage: p.add_constraint(2*x + 3*y, max = 6)
sage: p.add_constraint(3*x + 2*y, max = 6)
sage: p.set_objective(x + y + 7)
sage: p.solve()
47/5

Python

>>> from sage.all import *
>>> p = MixedIntegerLinearProgram(solver='InteractiveLP')
>>> x,y = p[Integer(0)], p[Integer(1)]
>>> p.add_constraint(Integer(2)*x + Integer(3)*y, max = Integer(6))
>>> p.add_constraint(Integer(3)*x + Integer(2)*y, max = Integer(6))
>>> p.set_objective(x + y + Integer(7))
>>> p.solve()
47/5

Sage Live

p = MixedIntegerLinearProgram(solver='InteractiveLP')
x,y = p[0], p[1]
p.add_constraint(2*x + 3*y, max = 6)
p.add_constraint(3*x + 2*y, max = 6)
p.set_objective(x + y + 7)
p.solve()

set_sense(sense)[source]¶

Set the direction (maximization/minimization).

INPUT:

sense – integer:
- +1 => Maximization
- -1 => Minimization

EXAMPLES:

Sage

sage: from sage.numerical.backends.generic_backend import get_solver
sage: p = get_solver(solver = "InteractiveLP")
sage: p.is_maximization()
True
sage: p.set_sense(-1)
sage: p.is_maximization()
False

Python

>>> from sage.all import *
>>> from sage.numerical.backends.generic_backend import get_solver
>>> p = get_solver(solver = "InteractiveLP")
>>> p.is_maximization()
True
>>> p.set_sense(-Integer(1))
>>> p.is_maximization()
False

Sage Live

from sage.numerical.backends.generic_backend import get_solver
p = get_solver(solver = "InteractiveLP")
p.is_maximization()
p.set_sense(-1)
p.is_maximization()

set_variable_type(variable, vtype)[source]¶

Set the type of a variable.

In this backend, variables are always continuous (real). If integer or binary variables are requested via the parameter vtype, an error will be raised.

INPUT:

variable – integer; the variable’s id
vtype – integer:
- 1 Integer
- 0 Binary
- -1
  
  Continuous

EXAMPLES:

Sage

sage: from sage.numerical.backends.generic_backend import get_solver
sage: p = get_solver(solver = "InteractiveLP")
sage: p.ncols()
0
sage: p.add_variable()
0
sage: p.set_variable_type(0,-1)
sage: p.is_variable_continuous(0)
True

Python

>>> from sage.all import *
>>> from sage.numerical.backends.generic_backend import get_solver
>>> p = get_solver(solver = "InteractiveLP")
>>> p.ncols()
0
>>> p.add_variable()
0
>>> p.set_variable_type(Integer(0),-Integer(1))
>>> p.is_variable_continuous(Integer(0))
True

Sage Live

from sage.numerical.backends.generic_backend import get_solver
p = get_solver(solver = "InteractiveLP")
p.ncols()
p.add_variable()
p.set_variable_type(0,-1)
p.is_variable_continuous(0)

set_verbosity(level)[source]¶

Set the log (verbosity) level.

INPUT:

level – integer; from 0 (no verbosity) to 3

EXAMPLES:

Sage

sage: from sage.numerical.backends.generic_backend import get_solver
sage: p = get_solver(solver = "InteractiveLP")
sage: p.set_verbosity(2)

Python

>>> from sage.all import *
>>> from sage.numerical.backends.generic_backend import get_solver
>>> p = get_solver(solver = "InteractiveLP")
>>> p.set_verbosity(Integer(2))

Sage Live

from sage.numerical.backends.generic_backend import get_solver
p = get_solver(solver = "InteractiveLP")
p.set_verbosity(2)

solve()[source]¶

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

sage: from sage.numerical.backends.generic_backend import get_solver
sage: p = get_solver(solver = "InteractiveLP")
sage: p.add_linear_constraints(5, 0, None)
sage: p.add_col(list(range(5)), list(range(5)))
sage: p.solve()
0
sage: p.objective_coefficient(0,1)
sage: p.solve()
Traceback (most recent call last):
...
MIPSolverException: ...

Python

>>> from sage.all import *
>>> from sage.numerical.backends.generic_backend import get_solver
>>> p = get_solver(solver = "InteractiveLP")
>>> p.add_linear_constraints(Integer(5), Integer(0), None)
>>> p.add_col(list(range(Integer(5))), list(range(Integer(5))))
>>> p.solve()
0
>>> p.objective_coefficient(Integer(0),Integer(1))
>>> p.solve()
Traceback (most recent call last):
...
MIPSolverException: ...

Sage Live

from sage.numerical.backends.generic_backend import get_solver
p = get_solver(solver = "InteractiveLP")
p.add_linear_constraints(5, 0, None)
p.add_col(list(range(5)), list(range(5)))
p.solve()
p.objective_coefficient(0,1)
p.solve()

variable_lower_bound(index, value=False)[source]¶

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 no lower bound. When set to False (default), the method returns the current value.

EXAMPLES:

Sage

sage: from sage.numerical.backends.generic_backend import get_solver
sage: p = get_solver(solver = "InteractiveLP")
sage: p.add_variable(lower_bound=None)
0
sage: p.col_bounds(0)
(None, None)
sage: p.variable_lower_bound(0) is None
True
sage: p.variable_lower_bound(0, 0)
sage: p.col_bounds(0)
(0, None)
sage: p.variable_lower_bound(0)
0
sage: p.variable_lower_bound(0, None)
sage: p.variable_lower_bound(0) is None
True

Python

>>> from sage.all import *
>>> from sage.numerical.backends.generic_backend import get_solver
>>> p = get_solver(solver = "InteractiveLP")
>>> p.add_variable(lower_bound=None)
0
>>> p.col_bounds(Integer(0))
(None, None)
>>> p.variable_lower_bound(Integer(0)) is None
True
>>> p.variable_lower_bound(Integer(0), Integer(0))
>>> p.col_bounds(Integer(0))
(0, None)
>>> p.variable_lower_bound(Integer(0))
0
>>> p.variable_lower_bound(Integer(0), None)
>>> p.variable_lower_bound(Integer(0)) is None
True

Sage Live

from sage.numerical.backends.generic_backend import get_solver
p = get_solver(solver = "InteractiveLP")
p.add_variable(lower_bound=None)
p.col_bounds(0)
p.variable_lower_bound(0) is None
p.variable_lower_bound(0, 0)
p.col_bounds(0)
p.variable_lower_bound(0)
p.variable_lower_bound(0, None)
p.variable_lower_bound(0) is None

variable_upper_bound(index, value=False)[source]¶

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 False (default), the method returns the current value.

EXAMPLES:

Sage

sage: from sage.numerical.backends.generic_backend import get_solver
sage: p = get_solver(solver = "InteractiveLP")
sage: p.add_variable(lower_bound=None)
0
sage: p.col_bounds(0)
(None, None)
sage: p.variable_upper_bound(0) is None
True
sage: p.variable_upper_bound(0, 0)
sage: p.col_bounds(0)
(None, 0)
sage: p.variable_upper_bound(0)
0
sage: p.variable_upper_bound(0, None)
sage: p.variable_upper_bound(0) is None
True

Python

>>> from sage.all import *
>>> from sage.numerical.backends.generic_backend import get_solver
>>> p = get_solver(solver = "InteractiveLP")
>>> p.add_variable(lower_bound=None)
0
>>> p.col_bounds(Integer(0))
(None, None)
>>> p.variable_upper_bound(Integer(0)) is None
True
>>> p.variable_upper_bound(Integer(0), Integer(0))
>>> p.col_bounds(Integer(0))
(None, 0)
>>> p.variable_upper_bound(Integer(0))
0
>>> p.variable_upper_bound(Integer(0), None)
>>> p.variable_upper_bound(Integer(0)) is None
True

Sage Live

from sage.numerical.backends.generic_backend import get_solver
p = get_solver(solver = "InteractiveLP")
p.add_variable(lower_bound=None)
p.col_bounds(0)
p.variable_upper_bound(0) is None
p.variable_upper_bound(0, 0)
p.col_bounds(0)
p.variable_upper_bound(0)
p.variable_upper_bound(0, None)
p.variable_upper_bound(0) is None