Generic Backend for LP solvers#
This class only lists the methods that should be defined by any
interface with a LP Solver. All these methods immediately raise
NotImplementedError
exceptions when called, and are obviously
meant to be replaced by the solver-specific method. This file can also
be used as a template to create a new interface : one would only need
to replace the occurrences of "Nonexistent_LP_solver"
by the
solver’s name, and replace GenericBackend
by
SolverName(GenericBackend)
so that the new solver extends this
class.
AUTHORS:
Nathann Cohen (2010-10) : initial implementation
Risan (2012-02) : extension for PPL backend
Ingolfur Edvardsson (2014-06): extension for CVXOPT backend
- class sage.numerical.backends.generic_backend.GenericBackend#
Bases:
SageObject
- 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 nonzerocoeffs
(list of real values) – associates a coefficient to the variable in each of the constraints in which it appears. Namely, the i-th entry ofcoeffs
corresponds to the coefficient of the variable in the constraint represented by the i-th entry inindices
.
Note
indices
andcoeffs
are expected to be of the same length.EXAMPLES:
sage: from sage.numerical.backends.generic_backend import get_solver sage: p = get_solver(solver = "Nonexistent_LP_solver") # optional - Nonexistent_LP_solver sage: p.ncols() # optional - Nonexistent_LP_solver 0 sage: p.nrows() # optional - Nonexistent_LP_solver 0 sage: p.add_linear_constraints(5, 0, None) # optional - Nonexistent_LP_solver sage: p.add_col(list(range(5)), list(range(5))) # optional - Nonexistent_LP_solver sage: p.nrows() # optional - Nonexistent_LP_solver 5
- add_linear_constraint(coefficients, lower_bound, upper_bound, name=None)#
Add a linear constraint.
INPUT:
coefficients
– an iterable of pairs(i, v)
. In each pair,i
is a variable index (integer) andv
is a value (element ofbase_ring()
).lower_bound
– element ofbase_ring()
orNone
. The lower bound.upper_bound
– element ofbase_ring()
orNone
. The upper bound.name
– string orNone
. Optional name for this row.
EXAMPLES:
sage: from sage.numerical.backends.generic_backend import get_solver sage: p = get_solver(solver = "Nonexistent_LP_solver") # optional - Nonexistent_LP_solver sage: p.add_variables(5) # optional - Nonexistent_LP_solver 4 sage: p.add_linear_constraint( zip(range(5), range(5)), 2.0, 2.0) # optional - Nonexistent_LP_solver sage: p.row(0) # optional - Nonexistent_LP_solver ([0, 1, 2, 3, 4], [0.0, 1.0, 2.0, 3.0, 4.0]) sage: p.row_bounds(0) # optional - Nonexistent_LP_solver (2.0, 2.0) sage: p.add_linear_constraint( zip(range(5), range(5)), 1.0, 1.0, name='foo') # optional - Nonexistent_LP_solver sage: p.row_name(1) # optional - Nonexistent_LP_solver 'foo'
- add_linear_constraint_vector(degree, coefficients, lower_bound, upper_bound, name=None)#
Add a vector-valued linear constraint.
Note
This is the generic implementation, which will split the vector-valued constraint into components and add these individually. Backends are encouraged to replace it with their own optimized implementation.
INPUT:
degree
– integer. The vector degree, that is, the number of new scalar constraints.coefficients
– an iterable of pairs(i, v)
. In each pair,i
is a variable index (integer) andv
is a vector (real and of lengthdegree
).lower_bound
– either a vector orNone
. The component-wise lower bound.upper_bound
– either a vector orNone
. The component-wise upper bound.name
– string orNone
. An optional name for all new rows.
EXAMPLES:
sage: from sage.numerical.backends.generic_backend import get_solver sage: p = get_solver(solver = "Nonexistent_LP_solver") # optional - Nonexistent_LP_solver sage: coeffs = ([0, vector([1, 2])], [1, vector([2, 3])]) sage: upper = vector([5, 5]) sage: lower = vector([0, 0]) sage: p.add_variables(2) # optional - Nonexistent_LP_solver 1 sage: p.add_linear_constraint_vector(2, coeffs, lower, upper, 'foo') # optional - Nonexistent_LP_solver
- add_linear_constraints(number, lower_bound, upper_bound, names=None)#
Add
'number
linear constraints.INPUT:
number
(integer) – the number of constraints to add.lower_bound
- a lower bound, either a real value orNone
upper_bound
- an upper bound, either a real value orNone
names
- an optional list of names (default:None
)
EXAMPLES:
sage: from sage.numerical.backends.generic_backend import get_solver sage: p = get_solver(solver = "Nonexistent_LP_solver") # optional - Nonexistent_LP_solver sage: p.add_variables(5) # optional - Nonexistent_LP_solver 5 sage: p.add_linear_constraints(5, None, 2) # optional - Nonexistent_LP_solver sage: p.row(4) # optional - Nonexistent_LP_solver ([], []) sage: p.row_bounds(4) # optional - Nonexistent_LP_solver (None, 2.0)
- add_variable(lower_bound=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.
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 binary (default:True
).integer
-True
if the variable is binary (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 = "Nonexistent_LP_solver") # optional - Nonexistent_LP_solver sage: p.ncols() # optional - Nonexistent_LP_solver 0 sage: p.add_variable() # optional - Nonexistent_LP_solver 0 sage: p.ncols() # optional - Nonexistent_LP_solver 1 sage: p.add_variable(binary=True) # optional - Nonexistent_LP_solver 1 sage: p.add_variable(lower_bound=-2.0, integer=True) # optional - Nonexistent_LP_solver 2 sage: p.add_variable(continuous=True, integer=True) # optional - Nonexistent_LP_solver Traceback (most recent call last): ... ValueError: ... sage: p.add_variable(name='x',obj=1.0) # optional - Nonexistent_LP_solver 3 sage: p.col_name(3) # optional - Nonexistent_LP_solver 'x' sage: p.objective_coefficient(3) # optional - Nonexistent_LP_solver 1.0
- add_variables(n, lower_bound=False, upper_bound=None, binary=False, continuous=True, integer=False, obj=None, names=None)#
Add
n
variables.This amounts to adding new columns to the matrix. By default, the variables are both nonnegative and real.
INPUT:
n
- the number of new variables (must be > 0)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 binary (default:True
).integer
-True
if the variable is binary (default:False
).obj
- (optional) coefficient of all variables in the objective function (default: 0.0)names
- optional list of names (default:None
)
OUTPUT: The index of the variable created last.
EXAMPLES:
sage: from sage.numerical.backends.generic_backend import get_solver sage: p = get_solver(solver = "Nonexistent_LP_solver") # optional - Nonexistent_LP_solver sage: p.ncols() # optional - Nonexistent_LP_solver 0 sage: p.add_variables(5) # optional - Nonexistent_LP_solver 4 sage: p.ncols() # optional - Nonexistent_LP_solver 5 sage: p.add_variables(2, lower_bound=-2.0, integer=True, names=['a','b']) # optional - Nonexistent_LP_solver 6
- base_ring()#
- best_known_objective_bound()#
Return the value of the currently best known bound.
This method returns the current best upper (resp. lower) bound on the optimal value of the objective function in a maximization (resp. minimization) problem. It is equal to the output of
get_objective_value()
if the MILP found an optimal solution, but it can differ if it was interrupted manually or after a time limit (cfsolver_parameter()
).Note
Has no meaning unless
solve
has been called before.EXAMPLES:
sage: p = MixedIntegerLinearProgram(solver="Nonexistent_LP_solver") # optional - Nonexistent_LP_solver sage: b = p.new_variable(binary=True) # optional - Nonexistent_LP_solver sage: for u,v in graphs.CycleGraph(5).edges(labels=False): # optional - Nonexistent_LP_solver ....: p.add_constraint(b[u]+b[v]<=1) # optional - Nonexistent_LP_solver sage: p.set_objective(p.sum(b[x] for x in range(5))) # optional - Nonexistent_LP_solver sage: p.solve() # optional - Nonexistent_LP_solver 2.0 sage: pb = p.get_backend() # optional - Nonexistent_LP_solver sage: pb.get_objective_value() # optional - Nonexistent_LP_solver 2.0 sage: pb.best_known_objective_bound() # optional - Nonexistent_LP_solver 2.0
- 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 toNone
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 = "Nonexistent_LP_solver") # optional - Nonexistent_LP_solver sage: p.add_variable() # optional - Nonexistent_LP_solver 0 sage: p.col_bounds(0) # optional - Nonexistent_LP_solver (0.0, None) sage: p.variable_upper_bound(0, 5) # optional - Nonexistent_LP_solver sage: p.col_bounds(0) # optional - Nonexistent_LP_solver (0.0, 5.0)
- col_name(index)#
Return the
index
-th column nameINPUT:
index
(integer) – the column idname
(char *
) – its name. When set toNULL
(default), the method returns the current name.
EXAMPLES:
sage: from sage.numerical.backends.generic_backend import get_solver sage: p = get_solver(solver = "Nonexistent_LP_solver") # optional - Nonexistent_LP_solver sage: p.add_variable(name="I am a variable") # optional - Nonexistent_LP_solver 1 sage: p.col_name(0) # optional - Nonexistent_LP_solver 'I am a variable'
- copy()#
Returns a copy of self.
EXAMPLES:
sage: from sage.numerical.backends.generic_backend import get_solver sage: p = MixedIntegerLinearProgram(solver = "Nonexistent_LP_solver") # optional - Nonexistent_LP_solver sage: b = p.new_variable() # optional - Nonexistent_LP_solver sage: p.add_constraint(b[1] + b[2] <= 6) # optional - Nonexistent_LP_solver sage: p.set_objective(b[1] + b[2]) # optional - Nonexistent_LP_solver sage: copy(p).solve() # optional - Nonexistent_LP_solver 6.0
- get_objective_value()#
Return the value of the objective function.
Note
Behavior is undefined unless
solve
has been called before.EXAMPLES:
sage: from sage.numerical.backends.generic_backend import get_solver sage: p = get_solver(solver = "Nonexistent_LP_solver") # optional - Nonexistent_LP_solver sage: p.add_variables(2) # optional - Nonexistent_LP_solver 1 sage: p.add_linear_constraint([(0,1), (1,2)], None, 3) # optional - Nonexistent_LP_solver sage: p.set_objective([2, 5]) # optional - Nonexistent_LP_solver sage: p.solve() # optional - Nonexistent_LP_solver 0 sage: p.get_objective_value() # optional - Nonexistent_LP_solver 7.5 sage: p.get_variable_value(0) # optional - Nonexistent_LP_solver 0.0 sage: p.get_variable_value(1) # optional - Nonexistent_LP_solver 1.5
- get_relative_objective_gap()#
Return the relative objective gap of the best known solution.
For a minimization problem, this value is computed by \((\texttt{bestinteger} - \texttt{bestobjective}) / (1e-10 + |\texttt{bestobjective}|)\), where
bestinteger
is the value returned byget_objective_value()
andbestobjective
is the value returned bybest_known_objective_bound()
. For a maximization problem, the value is computed by \((\texttt{bestobjective} - \texttt{bestinteger}) / (1e-10 + |\texttt{bestobjective}|)\).Note
Has no meaning unless
solve
has been called before.EXAMPLES:
sage: p = MixedIntegerLinearProgram(solver="Nonexistent_LP_solver") # optional - Nonexistent_LP_solver sage: b = p.new_variable(binary=True) # optional - Nonexistent_LP_solver sage: for u,v in graphs.CycleGraph(5).edges(labels=False): # optional - Nonexistent_LP_solver ....: p.add_constraint(b[u]+b[v]<=1) # optional - Nonexistent_LP_solver sage: p.set_objective(p.sum(b[x] for x in range(5))) # optional - Nonexistent_LP_solver sage: p.solve() # optional - Nonexistent_LP_solver 2.0 sage: pb = p.get_backend() # optional - Nonexistent_LP_solver sage: pb.get_objective_value() # optional - Nonexistent_LP_solver 2.0 sage: pb.get_relative_objective_gap() # optional - Nonexistent_LP_solver 0.0
- get_variable_value(variable)#
Return the value of a variable given by the solver.
Note
Behavior is undefined unless
solve
has been called before.EXAMPLES:
sage: from sage.numerical.backends.generic_backend import get_solver sage: p = get_solver(solver = "Nonexistent_LP_solver") # optional - Nonexistent_LP_solver sage: p.add_variables(2) # optional - Nonexistent_LP_solver 1 sage: p.add_linear_constraint([(0,1), (1, 2)], None, 3) # optional - Nonexistent_LP_solver sage: p.set_objective([2, 5]) # optional - Nonexistent_LP_solver sage: p.solve() # optional - Nonexistent_LP_solver 0 sage: p.get_objective_value() # optional - Nonexistent_LP_solver 7.5 sage: p.get_variable_value(0) # optional - Nonexistent_LP_solver 0.0 sage: p.get_variable_value(1) # optional - Nonexistent_LP_solver 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 = "Nonexistent_LP_solver") # optional - Nonexistent_LP_solver sage: p.is_maximization() # optional - Nonexistent_LP_solver True sage: p.set_sense(-1) # optional - Nonexistent_LP_solver sage: p.is_maximization() # optional - Nonexistent_LP_solver False
- is_slack_variable_basic(index)#
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: p = MixedIntegerLinearProgram(maximization=True, solver="Nonexistent_LP_solver") # optional - Nonexistent_LP_solver sage: x = p.new_variable(nonnegative=True) # optional - Nonexistent_LP_solver sage: p.add_constraint(-x[0] + x[1] <= 2) # optional - Nonexistent_LP_solver sage: p.add_constraint(8 * x[0] + 2 * x[1] <= 17) # optional - Nonexistent_LP_solver sage: p.set_objective(5.5 * x[0] - 3 * x[1]) # optional - Nonexistent_LP_solver sage: b = p.get_backend() # optional - Nonexistent_LP_solver sage: # Backend-specific commands to instruct solver to use simplex method here sage: b.solve() # optional - Nonexistent_LP_solver 0 sage: b.is_slack_variable_basic(0) # optional - Nonexistent_LP_solver True sage: b.is_slack_variable_basic(1) # optional - Nonexistent_LP_solver False
- is_slack_variable_nonbasic_at_lower_bound(index)#
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: p = MixedIntegerLinearProgram(maximization=True, solver="Nonexistent_LP_solver") # optional - Nonexistent_LP_solver sage: x = p.new_variable(nonnegative=True) # optional - Nonexistent_LP_solver sage: p.add_constraint(-x[0] + x[1] <= 2) # optional - Nonexistent_LP_solver sage: p.add_constraint(8 * x[0] + 2 * x[1] <= 17) # optional - Nonexistent_LP_solver sage: p.set_objective(5.5 * x[0] - 3 * x[1]) # optional - Nonexistent_LP_solver sage: b = p.get_backend() # optional - Nonexistent_LP_solver sage: # Backend-specific commands to instruct solver to use simplex method here sage: b.solve() # optional - Nonexistent_LP_solver 0 sage: b.is_slack_variable_nonbasic_at_lower_bound(0) # optional - Nonexistent_LP_solver False sage: b.is_slack_variable_nonbasic_at_lower_bound(1) # optional - Nonexistent_LP_solver True
- is_variable_basic(index)#
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: p = MixedIntegerLinearProgram(maximization=True, solver="Nonexistent_LP_solver") # optional - Nonexistent_LP_solver sage: x = p.new_variable(nonnegative=True) # optional - Nonexistent_LP_solver sage: p.add_constraint(-x[0] + x[1] <= 2) # optional - Nonexistent_LP_solver sage: p.add_constraint(8 * x[0] + 2 * x[1] <= 17) # optional - Nonexistent_LP_solver sage: p.set_objective(5.5 * x[0] - 3 * x[1]) # optional - Nonexistent_LP_solver sage: b = p.get_backend() # optional - Nonexistent_LP_solver sage: # Backend-specific commands to instruct solver to use simplex method here sage: b.solve() # optional - Nonexistent_LP_solver 0 sage: b.is_variable_basic(0) # optional - Nonexistent_LP_solver True sage: b.is_variable_basic(1) # optional - Nonexistent_LP_solver False
- is_variable_binary(index)#
Test whether the given variable is of binary type.
INPUT:
index
(integer) – the variable’s id
EXAMPLES:
sage: from sage.numerical.backends.generic_backend import get_solver sage: p = get_solver(solver = "Nonexistent_LP_solver") # optional - Nonexistent_LP_solver sage: p.ncols() # optional - Nonexistent_LP_solver 0 sage: p.add_variable() # optional - Nonexistent_LP_solver 0 sage: p.set_variable_type(0,0) # optional - Nonexistent_LP_solver sage: p.is_variable_binary(0) # optional - Nonexistent_LP_solver True
- is_variable_continuous(index)#
Test whether the given variable is of continuous/real type.
INPUT:
index
(integer) – the variable’s id
EXAMPLES:
sage: from sage.numerical.backends.generic_backend import get_solver sage: p = get_solver(solver = "Nonexistent_LP_solver") # optional - Nonexistent_LP_solver sage: p.ncols() # optional - Nonexistent_LP_solver 0 sage: p.add_variable() # optional - Nonexistent_LP_solver 0 sage: p.is_variable_continuous(0) # optional - Nonexistent_LP_solver True sage: p.set_variable_type(0,1) # optional - Nonexistent_LP_solver sage: p.is_variable_continuous(0) # optional - Nonexistent_LP_solver False
- is_variable_integer(index)#
Test whether the given variable is of integer type.
INPUT:
index
(integer) – the variable’s id
EXAMPLES:
sage: from sage.numerical.backends.generic_backend import get_solver sage: p = get_solver(solver = "Nonexistent_LP_solver") # optional - Nonexistent_LP_solver sage: p.ncols() # optional - Nonexistent_LP_solver 0 sage: p.add_variable() # optional - Nonexistent_LP_solver 0 sage: p.set_variable_type(0,1) # optional - Nonexistent_LP_solver sage: p.is_variable_integer(0) # optional - Nonexistent_LP_solver True
- is_variable_nonbasic_at_lower_bound(index)#
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: p = MixedIntegerLinearProgram(maximization=True, solver="Nonexistent_LP_solver") # optional - Nonexistent_LP_solver sage: x = p.new_variable(nonnegative=True) # optional - Nonexistent_LP_solver sage: p.add_constraint(-x[0] + x[1] <= 2) # optional - Nonexistent_LP_solver sage: p.add_constraint(8 * x[0] + 2 * x[1] <= 17) # optional - Nonexistent_LP_solver sage: p.set_objective(5.5 * x[0] - 3 * x[1]) # optional - Nonexistent_LP_solver sage: b = p.get_backend() # optional - Nonexistent_LP_solver sage: # Backend-specific commands to instruct solver to use simplex method here sage: b.solve() # optional - Nonexistent_LP_solver 0 sage: b.is_variable_nonbasic_at_lower_bound(0) # optional - Nonexistent_LP_solver False sage: b.is_variable_nonbasic_at_lower_bound(1) # optional - Nonexistent_LP_solver True
- ncols()#
Return the number of columns/variables.
EXAMPLES:
sage: from sage.numerical.backends.generic_backend import get_solver sage: p = get_solver(solver = "Nonexistent_LP_solver") # optional - Nonexistent_LP_solver sage: p.ncols() # optional - Nonexistent_LP_solver 0 sage: p.add_variables(2) # optional - Nonexistent_LP_solver 1 sage: p.ncols() # optional - Nonexistent_LP_solver 2
- nrows()#
Return the number of rows/constraints.
EXAMPLES:
sage: from sage.numerical.backends.generic_backend import get_solver sage: p = get_solver(solver = "Nonexistent_LP_solver") # optional - Nonexistent_LP_solver sage: p.nrows() # optional - Nonexistent_LP_solver 0 sage: p.add_linear_constraints(2, 2.0, None) # optional - Nonexistent_LP_solver sage: p.nrows() # optional - Nonexistent_LP_solver 2
- objective_coefficient(variable, coeff=None)#
Set or get the coefficient of a variable in the objective function
INPUT:
variable
(integer) – the variable’s idcoeff
(double) – its coefficient
EXAMPLES:
sage: from sage.numerical.backends.generic_backend import get_solver sage: p = get_solver(solver = "Nonexistent_LP_solver") # optional - Nonexistent_LP_solver sage: p.add_variable() # optional - Nonexistent_LP_solver 0 sage: p.objective_coefficient(0) # optional - Nonexistent_LP_solver 0.0 sage: p.objective_coefficient(0,2) # optional - Nonexistent_LP_solver sage: p.objective_coefficient(0) # optional - Nonexistent_LP_solver 2.0
- objective_constant_term(d=None)#
Set or get the constant term in the objective function
INPUT:
d
(double) – its coefficient. If \(None\) (default), return the current value.
EXAMPLES:
sage: from sage.numerical.backends.generic_backend import get_solver sage: p = get_solver(solver = "Nonexistent_LP_solver") # optional - Nonexistent_LP_solver sage: p.objective_constant_term() # optional - Nonexistent_LP_solver 0.0 sage: p.objective_constant_term(42) # optional - Nonexistent_LP_solver sage: p.objective_constant_term() # optional - Nonexistent_LP_solver 42.0
- problem_name(name=None)#
Return or define the problem’s name
INPUT:
name
(str
) – the problem’s name. When set toNone
(default), the method returns the problem’s name.
EXAMPLES:
sage: from sage.numerical.backends.generic_backend import get_solver sage: p = get_solver(solver = "Nonexistent_LP_solver") # optional - Nonexistent_LP_solver sage: p.problem_name("There once was a french fry") # optional - Nonexistent_LP_solver sage: print(p.problem_name()) # optional - Nonexistent_LP_solver There once was a french fry
- remove_constraint(i)#
Remove a constraint.
INPUT:
i
– index of the constraint to remove.
EXAMPLES:
sage: p = MixedIntegerLinearProgram(solver="Nonexistent_LP_solver") # optional - Nonexistent_LP_solver sage: v = p.new_variable(nonnegative=True) # optional - Nonexistent_LP_solver sage: x,y = v[0], v[1] # optional - Nonexistent_LP_solver sage: p.add_constraint(2*x + 3*y, max = 6) # optional - Nonexistent_LP_solver sage: p.add_constraint(3*x + 2*y, max = 6) # optional - Nonexistent_LP_solver sage: p.set_objective(x + y + 7) # optional - Nonexistent_LP_solver sage: p.set_integer(x); p.set_integer(y) # optional - Nonexistent_LP_solver sage: p.solve() # optional - Nonexistent_LP_solver 9.0 sage: p.remove_constraint(0) # optional - Nonexistent_LP_solver sage: p.solve() # optional - Nonexistent_LP_solver 10.0 sage: p.get_values([x,y]) # optional - Nonexistent_LP_solver [0.0, 3.0]
- remove_constraints(constraints)#
Remove several constraints.
INPUT:
constraints
– an iterable containing the indices of the rows to remove.
EXAMPLES:
sage: from sage.numerical.backends.generic_backend import get_solver sage: p = get_solver(solver = "Nonexistent_LP_solver") # optional - Nonexistent_LP_solver sage: p.add_variables(2) # optional - Nonexistent_LP_solver 1 sage: p.add_linear_constraint([(0, 2), (1, 3)], None, 6) # optional - Nonexistent_LP_solver sage: p.add_linear_constraint([(0, 3), (1, 2)], None, 6) # optional - Nonexistent_LP_solver sage: p.remove_constraints([0, 1]) # optional - Nonexistent_LP_solver
- row(i)#
Return a row
INPUT:
index
(integer) – the constraint’s id.
OUTPUT:
A pair
(indices, coeffs)
whereindices
lists the entries whose coefficient is nonzero, and to whichcoeffs
associates their coefficient on the model of theadd_linear_constraint
method.EXAMPLES:
sage: from sage.numerical.backends.generic_backend import get_solver sage: p = get_solver(solver = "Nonexistent_LP_solver") # optional - Nonexistent_LP_solver sage: p.add_variables(5) # optional - Nonexistent_LP_solver 4 sage: p.add_linear_constraint(zip(range(5), range(5)), 2, 2) # optional - Nonexistent_LP_solver sage: p.row(0) # optional - Nonexistent_LP_solver ([4, 3, 2, 1], [4.0, 3.0, 2.0, 1.0]) ## FIXME: Why backwards? sage: p.row_bounds(0) # optional - Nonexistent_LP_solver (2.0, 2.0)
- 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 toNone
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 = "Nonexistent_LP_solver") # optional - Nonexistent_LP_solver sage: p.add_variables(5) # optional - Nonexistent_LP_solver 4 sage: p.add_linear_constraint(list(range(5)), list(range(5)), 2, 2) # optional - Nonexistent_LP_solver sage: p.row(0) # optional - Nonexistent_LP_solver ([4, 3, 2, 1], [4.0, 3.0, 2.0, 1.0]) ## FIXME: Why backwards? sage: p.row_bounds(0) # optional - Nonexistent_LP_solver (2.0, 2.0)
- row_name(index)#
Return the
index
th row nameINPUT:
index
(integer) – the row’s id
EXAMPLES:
sage: from sage.numerical.backends.generic_backend import get_solver sage: p = get_solver(solver = "Nonexistent_LP_solver") # optional - Nonexistent_LP_solver sage: p.add_linear_constraints(1, 2, None, names=['Empty constraint 1']) # optional - Nonexistent_LP_solver sage: p.row_name(0) # optional - Nonexistent_LP_solver 'Empty constraint 1'
- set_objective(coeff, d=0.0)#
Set the objective function.
INPUT:
coeff
– a list of real values, whose i-th element is the coefficient of the i-th 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 sage: p = get_solver(solver = "Nonexistent_LP_solver") # optional - Nonexistent_LP_solver sage: p.add_variables(5) # optional - Nonexistent_LP_solver 4 sage: p.set_objective([1, 1, 2, 1, 3]) # optional - Nonexistent_LP_solver sage: [p.objective_coefficient(x) for x in range(5)] # optional - Nonexistent_LP_solver [1.0, 1.0, 2.0, 1.0, 3.0]
Constants in the objective function are respected:
sage: p = MixedIntegerLinearProgram(solver='Nonexistent_LP_solver') # optional - Nonexistent_LP_solver sage: x,y = p[0], p[1] # optional - Nonexistent_LP_solver sage: p.add_constraint(2*x + 3*y, max = 6) # optional - Nonexistent_LP_solver sage: p.add_constraint(3*x + 2*y, max = 6) # optional - Nonexistent_LP_solver sage: p.set_objective(x + y + 7) # optional - Nonexistent_LP_solver sage: p.set_integer(x); p.set_integer(y) # optional - Nonexistent_LP_solver sage: p.solve() # optional - Nonexistent_LP_solver 9.0
- 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 = "Nonexistent_LP_solver") # optional - Nonexistent_LP_solver sage: p.is_maximization() # optional - Nonexistent_LP_solver True sage: p.set_sense(-1) # optional - Nonexistent_LP_solver sage: p.is_maximization() # optional - Nonexistent_LP_solver False
- set_variable_type(variable, vtype)#
Set the type of a variable
INPUT:
variable
(integer) – the variable’s idvtype
(integer) :1 Integer
0 Binary
- -1
Continuous
EXAMPLES:
sage: from sage.numerical.backends.generic_backend import get_solver sage: p = get_solver(solver = "Nonexistent_LP_solver") # optional - Nonexistent_LP_solver sage: p.ncols() # optional - Nonexistent_LP_solver 0 sage: p.add_variable() # optional - Nonexistent_LP_solver 0 sage: p.set_variable_type(0,1) # optional - Nonexistent_LP_solver sage: p.is_variable_integer(0) # optional - Nonexistent_LP_solver True
- set_verbosity(level)#
Set the log (verbosity) level
INPUT:
level
(integer) – From 0 (no verbosity) to 3.
EXAMPLES:
sage: from sage.numerical.backends.generic_backend import get_solver sage: p = get_solver(solver = "Nonexistent_LP_solver") # optional - Nonexistent_LP_solver sage: p.set_verbosity(2) # optional - Nonexistent_LP_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: from sage.numerical.backends.generic_backend import get_solver sage: p = get_solver(solver = "Nonexistent_LP_solver") # optional - Nonexistent_LP_solver sage: p.add_linear_constraints(5, 0, None) # optional - Nonexistent_LP_solver sage: p.add_col(list(range(5)), list(range(5))) # optional - Nonexistent_LP_solver sage: p.solve() # optional - Nonexistent_LP_solver 0 sage: p.objective_coefficient(0,1) # optional - Nonexistent_LP_solver sage: p.solve() # optional - Nonexistent_LP_solver Traceback (most recent call last): ... MIPSolverException: ...
- solver_parameter(name, value=None)#
Return or define a solver parameter
INPUT:
name
(string) – the parametervalue
– the parameter’s value if it is to be defined, orNone
(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 = "Nonexistent_LP_solver") # optional - Nonexistent_LP_solver sage: p.solver_parameter("timelimit") # optional - Nonexistent_LP_solver sage: p.solver_parameter("timelimit", 60) # optional - Nonexistent_LP_solver sage: p.solver_parameter("timelimit") # optional - Nonexistent_LP_solver
- variable_lower_bound(index, value=False)#
Return or define the lower bound on a variable
INPUT:
index
(integer) – the variable’s idvalue
– real value, orNone
to mean that the variable has not lower bound. When set toFalse
(default), the method returns the current value.
EXAMPLES:
sage: from sage.numerical.backends.generic_backend import get_solver sage: p = get_solver(solver = "Nonexistent_LP_solver") # optional - Nonexistent_LP_solver sage: p.add_variable() # optional - Nonexistent_LP_solver 0 sage: p.col_bounds(0) # optional - Nonexistent_LP_solver (0.0, None) sage: p.variable_lower_bound(0, 5) # optional - Nonexistent_LP_solver sage: p.col_bounds(0) # optional - Nonexistent_LP_solver (5.0, None)
- variable_upper_bound(index, value=False)#
Return or define the upper bound on a variable
INPUT:
index
(integer) – the variable’s idvalue
– real value, orNone
to mean that the variable has not upper bound. When set toFalse
(default), the method returns the current value.
EXAMPLES:
sage: from sage.numerical.backends.generic_backend import get_solver sage: p = get_solver(solver = "Nonexistent_LP_solver") # optional - Nonexistent_LP_solver sage: p.add_variable() # optional - Nonexistent_LP_solver 0 sage: p.col_bounds(0) # optional - Nonexistent_LP_solver (0.0, None) sage: p.variable_upper_bound(0, 5) # optional - Nonexistent_LP_solver sage: p.col_bounds(0) # optional - Nonexistent_LP_solver (0.0, 5.0)
- write_lp(name)#
Write the problem to a
.lp
fileINPUT:
filename
(string)
EXAMPLES:
sage: from sage.numerical.backends.generic_backend import get_solver sage: p = get_solver(solver = "Nonexistent_LP_solver") # optional - Nonexistent_LP_solver sage: p.add_variables(2) # optional - Nonexistent_LP_solver 2 sage: p.add_linear_constraint([(0, 1], (1, 2)], None, 3) # optional - Nonexistent_LP_solver sage: p.set_objective([2, 5]) # optional - Nonexistent_LP_solver sage: from tempfile import NamedTemporaryFile # optional - Nonexistent_LP_solver sage: with NamedTemporaryFile(suffix=".lp") as f: # optional - Nonexistent_LP_solver ....: p.write_lp(f.name)
- write_mps(name, modern)#
Write the problem to a
.mps
fileINPUT:
filename
(string)
EXAMPLES:
sage: from sage.numerical.backends.generic_backend import get_solver sage: p = get_solver(solver = "Nonexistent_LP_solver") # optional - Nonexistent_LP_solver sage: p.add_variables(2) # optional - Nonexistent_LP_solver 2 sage: p.add_linear_constraint([(0, 1), (1, 2)], None, 3) # optional - Nonexistent_LP_solver sage: p.set_objective([2, 5]) # optional - Nonexistent_LP_solver sage: from tempfile import NamedTemporaryFile # optional - Nonexistent_LP_solver sage: with NamedTemporaryFile(suffix=".lp") as f: # optional - Nonexistent_LP_solver ....: p.write_lp(f.name)
- zero()#
- sage.numerical.backends.generic_backend.default_mip_solver(solver=None)#
Returns/sets the default MILP solver used by Sage
INPUT:
solver
– one of the following:a string indicating one of the available solvers (see
MixedIntegerLinearProgram
);a callable (typically a subclass of
sage.numerical.backends.generic_backend.GenericBackend
);None
(default), in which case the current default solver is returned; this is either a string or a callable.
OUTPUT:
This function returns the current default solver’s name if
solver = None
(default). Otherwise, it sets the default solver to the one given. If this solver does not exist, or is not available, aValueError
exception is raised.EXAMPLES:
sage: former_solver = default_mip_solver() sage: default_mip_solver("GLPK") sage: default_mip_solver() 'Glpk' sage: default_mip_solver("PPL") sage: default_mip_solver() 'Ppl' sage: default_mip_solver("GUROBI") # random Traceback (most recent call last): ... ValueError: Gurobi is not available. Please refer to the documentation to install it. sage: default_mip_solver("Yeahhhhhhhhhhh") Traceback (most recent call last): ... ValueError: 'solver' should be set to ... sage: default_mip_solver(former_solver)
- sage.numerical.backends.generic_backend.get_solver(constraint_generation=False, solver=None, base_ring=None)#
Return a solver according to the given preferences
INPUT:
solver
– one of the following:a string indicating one of the available solvers (see
MixedIntegerLinearProgram
);None
(default), in which case the default solver is used (seedefault_mip_solver()
);or a callable (such as a class), in which case it is called, and its result is returned.
base_ring
– If notNone
, request a solver that works over this(ordered) field. If
base_ring
is not a field, its fraction field is used.For example, is
base_ring=ZZ
is provided, the solver will work over the rational numbers. This is unrelated to whether variables are constrained to be integers or not.
constraint_generation
– Only used whensolver=None
.When set to
True
, after solving theMixedIntegerLinearProgram
, it is possible to add a constraint, and then solve it again. The effect is that solvers that do not support this feature will not be used. (Coin and SCIP are such solvers.)Defaults to
False
.
See also
default_mip_solver()
– Returns/Sets the default MIP solver.
EXAMPLES:
sage: from sage.numerical.backends.generic_backend import get_solver sage: p = get_solver() sage: p = get_solver(base_ring=RDF) sage: p.base_ring() Real Double Field sage: p = get_solver(base_ring=QQ); p <...sage.numerical.backends.ppl_backend.PPLBackend...> sage: p = get_solver(base_ring=ZZ); p <...sage.numerical.backends.ppl_backend.PPLBackend...> sage: p.base_ring() Rational Field sage: p = get_solver(base_ring=AA); p # optional - sage.rings.number_field <...sage.numerical.backends.interactivelp_backend.InteractiveLPBackend...> sage: p.base_ring() # optional - sage.rings.number_field Algebraic Real Field sage: d = polytopes.dodecahedron() # optional - sage.rings.number_field sage: p = get_solver(base_ring=d.base_ring()); p # optional - sage.rings.number_field <...sage.numerical.backends.interactivelp_backend.InteractiveLPBackend...> sage: p.base_ring() # optional - sage.rings.number_field Number Field in sqrt5 with defining polynomial x^2 - 5 with sqrt5 = 2.236067977499790? sage: p = get_solver(solver='InteractiveLP', base_ring=QQ); p # optional - sage.rings.number_field <...sage.numerical.backends.interactivelp_backend.InteractiveLPBackend...> sage: p.base_ring() # optional - sage.rings.number_field Rational Field
Passing a callable as the ‘solver’:
sage: from sage.numerical.backends.glpk_backend import GLPKBackend sage: p = get_solver(solver=GLPKBackend); p <...sage.numerical.backends.glpk_backend.GLPKBackend...>
Passing a callable that customizes a backend:
sage: def glpk_exact_solver(): ....: from sage.numerical.backends.generic_backend import get_solver ....: b = get_solver(solver="GLPK") ....: b.solver_parameter("simplex_or_intopt", "exact_simplex_only") ....: return b sage: codes.bounds.delsarte_bound_additive_hamming_space(11,3,4,solver=glpk_exact_solver) # long time 8