GLPK Backend¶
AUTHORS:
- Nathann Cohen (2010-10): initial implementation
- John Perry (2012-01): glp_simplex preprocessing
- John Perry and Raniere Gaia Silva (2012-03): solver parameters
- Christian Kuper (2012-10): Additions for sensitivity analysis
-
class
sage.numerical.backends.glpk_backend.
GLPKBackend
¶ Bases:
sage.numerical.backends.generic_backend.GenericBackend
MIP Backend that uses the GLPK solver.
TESTS:
General backend testsuite:
sage: p = MixedIntegerLinearProgram(solver="GLPK") sage: TestSuite(p.get_backend()).run(skip="_test_pickling")
-
add_col
(indices, coeffs)¶ Add a column.
INPUT:
indices
(list of integers) – this list constains 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 ith entry ofcoeffs
corresponds to the coefficient of the variable in the constraint represented by the ith entry inindices
.
Note
indices
andcoeffs
are expected to be of the same length.EXAMPLE:
sage: from sage.numerical.backends.generic_backend import get_solver sage: p = get_solver(solver = "GLPK") sage: p.ncols() 0 sage: p.nrows() 0 sage: p.add_linear_constraints(5, 0, None) sage: p.add_col(range(5), range(5)) sage: p.nrows() 5
-
add_linear_constraint
(coefficients, lower_bound, upper_bound, name=None)¶ Add a linear constraint.
INPUT:
coefficients
an iterable with(c,v)
pairs wherec
is a variable index (integer) andv
is a value (real value).lower_bound
- a lower bound, either a real value orNone
upper_bound
- an upper bound, either a real value orNone
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 = "GLPK") sage: p.add_variables(5) 4 sage: p.add_linear_constraint(list(zip(range(5), range(5))), 2.0, 2.0) sage: p.row(0) ([4, 3, 2, 1], [4.0, 3.0, 2.0, 1.0]) sage: p.row_bounds(0) (2.0, 2.0) sage: p.add_linear_constraint(list(zip(range(5), range(5))), 1.0, 1.0, name='foo') sage: p.row_name(1) 'foo'
TESTS:
This used to crash Sage, but was fixed in trac ticket #19525:
sage: p = MixedIntegerLinearProgram(solver="glpk") sage: q = MixedIntegerLinearProgram(solver="glpk") sage: q.add_constraint(p.new_variable()[0] <= 1) Traceback (most recent call last): ... GLPKError: glp_set_mat_row: i = 1; len = 1; invalid row length Error detected in file glpapi01.c at line ...
-
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
)
EXAMPLE:
sage: from sage.numerical.backends.generic_backend import get_solver sage: p = get_solver(solver = "GLPK") sage: p.add_variables(5) 4 sage: p.add_linear_constraints(5, None, 2) sage: p.row(4) ([], []) sage: p.row_bounds(4) (None, 2.0) sage: p.add_linear_constraints(2, None, 2, names=['foo','bar'])
-
add_variable
(lower_bound=0.0, upper_bound=None, binary=False, continuous=False, integer=False, obj=0.0, name=None)¶ Add a variable.
This amounts to adding a new column to the matrix. By default, the variable is both positive, real and the coefficient in the objective function is 0.0.
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
EXAMPLE:
sage: from sage.numerical.backends.generic_backend import get_solver sage: p = get_solver(solver = "GLPK") sage: p.ncols() 0 sage: p.add_variable() 0 sage: p.ncols() 1 sage: p.add_variable(binary=True) 1 sage: p.add_variable(lower_bound=-2.0, integer=True) 2 sage: p.add_variable(continuous=True, integer=True) Traceback (most recent call last): ... ValueError: ... sage: p.add_variable(name='x', obj=1.0) 3 sage: p.col_name(3) 'x' sage: p.objective_coefficient(3) 1.0
-
add_variables
(number, lower_bound=0.0, upper_bound=None, binary=False, continuous=False, integer=False, obj=0.0, names=None)¶ Add
number
new variables.This amounts to adding new columns to the matrix. By default, the variables are both positive, real and theor coefficient in the objective function is 0.0.
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.
EXAMPLE:
sage: from sage.numerical.backends.generic_backend import get_solver sage: p = get_solver(solver = "GLPK") sage: p.ncols() 0 sage: p.add_variables(5) 4 sage: p.ncols() 5 sage: p.add_variables(2, lower_bound=-2.0, integer=True, obj=42.0, names=['a','b']) 6
TESTS:
Check that arguments are used:
sage: p.col_bounds(5) # tol 1e-8 (-2.0, None) sage: p.is_variable_integer(5) True sage: p.col_name(5) 'a' sage: p.objective_coefficient(5) 42.0
-
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.EXAMPLE:
sage: g = graphs.CubeGraph(9) sage: p = MixedIntegerLinearProgram(solver="GLPK") sage: p.solver_parameter("mip_gap_tolerance",100) sage: b = p.new_variable(binary=True) sage: p.set_objective(p.sum(b[v] for v in g)) sage: for v in g: ....: p.add_constraint(b[v]+p.sum(b[u] for u in g.neighbors(v)) <= 1) sage: p.add_constraint(b[v] == 1) # Force an easy non-0 solution sage: p.solve() # rel tol 100 1.0 sage: backend = p.get_backend() sage: backend.best_known_objective_bound() # random 48.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.EXAMPLE:
sage: from sage.numerical.backends.generic_backend import get_solver sage: p = get_solver(solver = "GLPK") sage: p.add_variable() 0 sage: p.col_bounds(0) (0.0, None) sage: p.variable_upper_bound(0, 5) sage: p.col_bounds(0) (0.0, 5.0)
-
col_name
(index)¶ Return the
index
th col nameINPUT:
index
(integer) – the col’s id
EXAMPLE:
sage: from sage.numerical.backends.generic_backend import get_solver sage: p = get_solver(solver = "GLPK") sage: p.add_variable(name='I am a variable') 0 sage: p.col_name(0) 'I am a variable'
-
eval_tab_col
(k)¶ Computes a column of the current simplex tableau.
A (column) corresponds to some non-basic variable specified by the parameter
k
as follows:- if \(0 \leq k \leq m-1\), the non-basic variable is \(k\)-th auxiliary variable,
- if \(m \leq k \leq m+n-1\), the non-basic variable is \((k-m)\)-th structual variable,
where \(m\) is the number of rows and \(n\) is the number of columns in the specified problem object.
Note
The basis factorization must exist. Otherwise a
MIPSolverException
will be raised.INPUT:
k
(integer) – the id of the non-basic variable.
OUTPUT:
A pair
(indices, coeffs)
whereindices
lists the entries whose coefficient is nonzero, and to whichcoeffs
associates their coefficient in the computed column of the current simplex tableau.Note
Elements in
indices
have the same sense as index \(k\). All these variables are basic by definition.EXAMPLE:
sage: from sage.numerical.backends.generic_backend import get_solver sage: lp = get_solver(solver = "GLPK") sage: lp.add_variables(3) 2 sage: lp.add_linear_constraint(list(zip([0, 1, 2], [8, 6, 1])), None, 48) sage: lp.add_linear_constraint(list(zip([0, 1, 2], [4, 2, 1.5])), None, 20) sage: lp.add_linear_constraint(list(zip([0, 1, 2], [2, 1.5, 0.5])), None, 8) sage: lp.set_objective([60, 30, 20]) sage: import sage.numerical.backends.glpk_backend as backend sage: lp.solver_parameter(backend.glp_simplex_or_intopt, backend.glp_simplex_only) sage: lp.eval_tab_col(1) Traceback (most recent call last): ... MIPSolverException: ... sage: lp.solve() 0 sage: lp.eval_tab_col(1) ([0, 5, 3], [-2.0, 2.0, -0.5]) sage: lp.eval_tab_col(2) ([0, 5, 3], [8.0, -4.0, 1.5]) sage: lp.eval_tab_col(4) ([0, 5, 3], [-2.0, 2.0, -1.25]) sage: lp.eval_tab_col(0) Traceback (most recent call last): ... MIPSolverException: ... sage: lp.eval_tab_col(-1) Traceback (most recent call last): ... ValueError: ...
-
eval_tab_row
(k)¶ Computes a row of the current simplex tableau.
A row corresponds to some basic variable specified by the parameter
k
as follows:- if \(0 \leq k \leq m-1\), the basic variable is \(k\)-th auxiliary variable,
- if \(m \leq k \leq m+n-1\), the basic variable is \((k-m)\)-th structual variable,
where \(m\) is the number of rows and \(n\) is the number of columns in the specified problem object.
Note
The basis factorization must exist. Otherwise, a
MIPSolverException
will be raised.INPUT:
k
(integer) – the id of the basic variable.
OUTPUT:
A pair
(indices, coeffs)
whereindices
lists the entries whose coefficient is nonzero, and to whichcoeffs
associates their coefficient in the computed row of the current simplex tableau.Note
Elements in
indices
have the same sense as indexk
. All these variables are non-basic by definition.EXAMPLE:
sage: from sage.numerical.backends.generic_backend import get_solver sage: lp = get_solver(solver = "GLPK") sage: lp.add_variables(3) 2 sage: lp.add_linear_constraint(list(zip([0, 1, 2], [8, 6, 1])), None, 48) sage: lp.add_linear_constraint(list(zip([0, 1, 2], [4, 2, 1.5])), None, 20) sage: lp.add_linear_constraint(list(zip([0, 1, 2], [2, 1.5, 0.5])), None, 8) sage: lp.set_objective([60, 30, 20]) sage: import sage.numerical.backends.glpk_backend as backend sage: lp.solver_parameter(backend.glp_simplex_or_intopt, backend.glp_simplex_only) sage: lp.eval_tab_row(0) Traceback (most recent call last): ... MIPSolverException: ... sage: lp.solve() 0 sage: lp.eval_tab_row(0) ([1, 2, 4], [-2.0, 8.0, -2.0]) sage: lp.eval_tab_row(3) ([1, 2, 4], [-0.5, 1.5, -1.25]) sage: lp.eval_tab_row(5) ([1, 2, 4], [2.0, -4.0, 2.0]) sage: lp.eval_tab_row(1) Traceback (most recent call last): ... MIPSolverException: ... sage: lp.eval_tab_row(-1) Traceback (most recent call last): ... ValueError: ...
-
get_col_dual
(variable)¶ Returns the dual value (reduced cost) of a variable
The dual value is the reduced cost of a variable. The reduced cost is the amount by which the objective coefficient of a non basic variable has to change to become a basic variable.
INPUT:
variable
– The number of the variable
Note
Behaviour is undefined unless
solve
has been called before. If the simplex algorithm has not been used for solving just a 0.0 will be returned.EXAMPLE:
sage: from sage.numerical.backends.generic_backend import get_solver sage: p = get_solver(solver = "GLPK") sage: p.add_variables(3) 2 sage: p.add_linear_constraint(list(zip([0, 1, 2], [8, 6, 1])), None, 48) sage: p.add_linear_constraint(list(zip([0, 1, 2], [4, 2, 1.5])), None, 20) sage: p.add_linear_constraint(list(zip([0, 1, 2], [2, 1.5, 0.5])), None, 8) sage: p.set_objective([60, 30, 20]) sage: import sage.numerical.backends.glpk_backend as backend sage: p.solver_parameter(backend.glp_simplex_or_intopt, backend.glp_simplex_only) sage: p.solve() 0 sage: p.get_col_dual(1) -5.0
-
get_col_stat
(j)¶ Retrieve the status of a variable.
INPUT:
j
– The index of the variable
OUTPUT:
Returns current status assigned to the structural variable associated with j-th column:
- GLP_BS = 1 basic variable
- GLP_NL = 2 non-basic variable on lower bound
- GLP_NU = 3 non-basic variable on upper bound
- GLP_NF = 4 non-basic free (unbounded) variable
- GLP_NS = 5 non-basic fixed variable
EXAMPLE:
sage: from sage.numerical.backends.generic_backend import get_solver sage: lp = get_solver(solver = "GLPK") sage: lp.add_variables(3) 2 sage: lp.add_linear_constraint(list(zip([0, 1, 2], [8, 6, 1])), None, 48) sage: lp.add_linear_constraint(list(zip([0, 1, 2], [4, 2, 1.5])), None, 20) sage: lp.add_linear_constraint(list(zip([0, 1, 2], [2, 1.5, 0.5])), None, 8) sage: lp.set_objective([60, 30, 20]) sage: import sage.numerical.backends.glpk_backend as backend sage: lp.solver_parameter(backend.glp_simplex_or_intopt, backend.glp_simplex_only) sage: lp.solve() 0 sage: lp.get_col_stat(0) 1 sage: lp.get_col_stat(1) 2 sage: lp.get_col_stat(-1) Exception ValueError: ... 0
-
get_objective_value
()¶ Returns the value of the objective function.
Note
Behaviour is undefined unless
solve
has been called before.EXAMPLE:
sage: from sage.numerical.backends.generic_backend import get_solver sage: p = get_solver(solver = "GLPK") 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() 7.5 sage: p.get_variable_value(0) # abs tol 1e-15 0.0 sage: p.get_variable_value(1) 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.EXAMPLE:
sage: g = graphs.CubeGraph(9) sage: p = MixedIntegerLinearProgram(solver="GLPK") sage: p.solver_parameter("mip_gap_tolerance",100) sage: b = p.new_variable(binary=True) sage: p.set_objective(p.sum(b[v] for v in g)) sage: for v in g: ....: p.add_constraint(b[v]+p.sum(b[u] for u in g.neighbors(v)) <= 1) sage: p.add_constraint(b[v] == 1) # Force an easy non-0 solution sage: p.solve() # rel tol 100 1.0 sage: backend = p.get_backend() sage: backend.get_relative_objective_gap() # random 46.99999999999999
TESTS:
Just make sure that the variable has been defined, and is not just undefined:
sage: backend.get_relative_objective_gap() > 1 True
-
get_row_dual
(variable)¶ Returns the dual value of a constraint.
The dual value of the ith row is also the value of the ith variable of the dual problem.
The dual value of a constraint is the shadow price of the constraint. The shadow price is the amount by which the objective value will change if the constraints bounds change by one unit under the precondition that the basis remains the same.
INPUT:
variable
– The number of the constraint
Note
Behaviour is undefined unless
solve
has been called before. If the simplex algorithm has not been used for solving 0.0 will be returned.EXAMPLE:
sage: from sage.numerical.backends.generic_backend import get_solver sage: lp = get_solver(solver = "GLPK") sage: lp.add_variables(3) 2 sage: lp.add_linear_constraint(list(zip([0, 1, 2], [8, 6, 1])), None, 48) sage: lp.add_linear_constraint(list(zip([0, 1, 2], [4, 2, 1.5])), None, 20) sage: lp.add_linear_constraint(list(zip([0, 1, 2], [2, 1.5, 0.5])), None, 8) sage: lp.set_objective([60, 30, 20]) sage: import sage.numerical.backends.glpk_backend as backend sage: lp.solver_parameter(backend.glp_simplex_or_intopt, backend.glp_simplex_only) sage: lp.solve() 0 sage: lp.get_row_dual(0) # tolerance 0.00001 0.0 sage: lp.get_row_dual(1) # tolerance 0.00001 10.0
-
get_row_prim
(i)¶ Returns the value of the auxiliary variable associated with i-th row.
Note
Behaviour is undefined unless
solve
has been called before.EXAMPLE:
sage: from sage.numerical.backends.generic_backend import get_solver sage: lp = get_solver(solver = "GLPK") sage: lp.add_variables(3) 2 sage: lp.add_linear_constraint(list(zip([0, 1, 2], [8, 6, 1])), None, 48) sage: lp.add_linear_constraint(list(zip([0, 1, 2], [4, 2, 1.5])), None, 20) sage: lp.add_linear_constraint(list(zip([0, 1, 2], [2, 1.5, 0.5])), None, 8) sage: lp.set_objective([60, 30, 20]) sage: import sage.numerical.backends.glpk_backend as backend sage: lp.solver_parameter(backend.glp_simplex_or_intopt, backend.glp_simplex_only) sage: lp.solve() 0 sage: lp.get_objective_value() 280.0 sage: lp.get_row_prim(0) 24.0 sage: lp.get_row_prim(1) 20.0 sage: lp.get_row_prim(2) 8.0
-
get_row_stat
(i)¶ Retrieve the status of a constraint.
INPUT:
i
– The index of the constraint
OUTPUT:
Returns current status assigned to the auxiliary variable associated with i-th row:
- GLP_BS = 1 basic variable
- GLP_NL = 2 non-basic variable on lower bound
- GLP_NU = 3 non-basic variable on upper bound
- GLP_NF = 4 non-basic free (unbounded) variable
- GLP_NS = 5 non-basic fixed variable
EXAMPLE:
sage: from sage.numerical.backends.generic_backend import get_solver sage: lp = get_solver(solver = "GLPK") sage: lp.add_variables(3) 2 sage: lp.add_linear_constraint(list(zip([0, 1, 2], [8, 6, 1])), None, 48) sage: lp.add_linear_constraint(list(zip([0, 1, 2], [4, 2, 1.5])), None, 20) sage: lp.add_linear_constraint(list(zip([0, 1, 2], [2, 1.5, 0.5])), None, 8) sage: lp.set_objective([60, 30, 20]) sage: import sage.numerical.backends.glpk_backend as backend sage: lp.solver_parameter(backend.glp_simplex_or_intopt, backend.glp_simplex_only) sage: lp.solve() 0 sage: lp.get_row_stat(0) 1 sage: lp.get_row_stat(1) 3 sage: lp.get_row_stat(-1) Exception ValueError: ... 0
-
get_variable_value
(variable)¶ Returns the value of a variable given by the solver.
Note
Behaviour is undefined unless
solve
has been called before.EXAMPLE:
sage: from sage.numerical.backends.generic_backend import get_solver sage: p = get_solver(solver = "GLPK") 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() 7.5 sage: p.get_variable_value(0) # abs tol 1e-15 0.0 sage: p.get_variable_value(1) 1.5
-
is_maximization
()¶ Test whether the problem is a maximization
EXAMPLE:
sage: from sage.numerical.backends.generic_backend import get_solver sage: p = get_solver(solver = "GLPK") sage: p.is_maximization() True sage: p.set_sense(-1) sage: p.is_maximization() 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
EXAMPLE:
sage: p = MixedIntegerLinearProgram(maximization=True, solver="GLPK") 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(5.5 * x[0] - 3 * x[1]) sage: b = p.get_backend() sage: import sage.numerical.backends.glpk_backend as backend sage: b.solver_parameter(backend.glp_simplex_or_intopt, backend.glp_simplex_only) sage: b.solve() 0 sage: b.is_slack_variable_basic(0) True sage: b.is_slack_variable_basic(1) False
-
is_slack_variable_nonbasic_at_lower_bound
(index)¶ Test whether the slack variable of the given row 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
EXAMPLE:
sage: p = MixedIntegerLinearProgram(maximization=True, solver="GLPK") 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(5.5 * x[0] - 3 * x[1]) sage: b = p.get_backend() sage: import sage.numerical.backends.glpk_backend as backend sage: b.solver_parameter(backend.glp_simplex_or_intopt, backend.glp_simplex_only) 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
-
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
EXAMPLE:
sage: p = MixedIntegerLinearProgram(maximization=True, solver="GLPK") 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(5.5 * x[0] - 3 * x[1]) sage: b = p.get_backend() sage: import sage.numerical.backends.glpk_backend as backend sage: b.solver_parameter(backend.glp_simplex_or_intopt, backend.glp_simplex_only) sage: b.solve() 0 sage: b.is_variable_basic(0) True sage: b.is_variable_basic(1) False
-
is_variable_binary
(index)¶ Test whether the given variable is of binary type.
INPUT:
index
(integer) – the variable’s id
EXAMPLE:
sage: from sage.numerical.backends.generic_backend import get_solver sage: p = get_solver(solver = "GLPK") sage: p.ncols() 0 sage: p.add_variable() 0 sage: p.set_variable_type(0,0) sage: p.is_variable_binary(0) True
-
is_variable_continuous
(index)¶ Test whether the given variable is of continuous/real type.
INPUT:
index
(integer) – the variable’s id
EXAMPLE:
sage: from sage.numerical.backends.generic_backend import get_solver sage: p = get_solver(solver = "GLPK") sage: p.ncols() 0 sage: p.add_variable() 0 sage: p.is_variable_continuous(0) True sage: p.set_variable_type(0,1) sage: p.is_variable_continuous(0) False
-
is_variable_integer
(index)¶ Test whether the given variable is of integer type.
INPUT:
index
(integer) – the variable’s id
EXAMPLE:
sage: from sage.numerical.backends.generic_backend import get_solver sage: p = get_solver(solver = "GLPK") sage: p.ncols() 0 sage: p.add_variable() 0 sage: p.set_variable_type(0,1) sage: p.is_variable_integer(0) 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
EXAMPLE:
sage: p = MixedIntegerLinearProgram(maximization=True, solver="GLPK") 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(5.5 * x[0] - 3 * x[1]) sage: b = p.get_backend() sage: import sage.numerical.backends.glpk_backend as backend sage: b.solver_parameter(backend.glp_simplex_or_intopt, backend.glp_simplex_only) sage: b.solve() 0 sage: b.is_variable_nonbasic_at_lower_bound(0) False sage: b.is_variable_nonbasic_at_lower_bound(1) True
-
ncols
()¶ Return the number of columns/variables.
EXAMPLE:
sage: from sage.numerical.backends.generic_backend import get_solver sage: p = get_solver(solver = "GLPK") sage: p.ncols() 0 sage: p.add_variables(2) 1 sage: p.ncols() 2
-
nrows
()¶ Return the number of rows/constraints.
EXAMPLE:
sage: from sage.numerical.backends.generic_backend import get_solver sage: p = get_solver(solver = "GLPK") sage: p.nrows() 0 sage: p.add_linear_constraints(2, 2, None) sage: p.nrows() 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 orNone
for reading (default:None
)
EXAMPLE:
sage: from sage.numerical.backends.generic_backend import get_solver sage: p = get_solver(solver = "GLPK") sage: p.add_variable() 0 sage: p.objective_coefficient(0) 0.0 sage: p.objective_coefficient(0,2) sage: p.objective_coefficient(0) 2.0
-
print_ranges
(filename='NULL')¶ Print results of a sensitivity analysis
If no filename is given as an input the results of the sensitivity analysis are displayed on the screen. If a filename is given they are written to a file.
INPUT:
filename
– (optional) name of the file
OUTPUT:
Zero if the operations was successful otherwise nonzero.
Note
This method is only effective if an optimal solution has been found for the lp using the simplex algorithm. In all other cases an error message is printed.
EXAMPLE:
sage: from sage.numerical.backends.generic_backend import get_solver sage: p = get_solver(solver = "GLPK") sage: p.add_variables(2) 1 sage: p.add_linear_constraint(list(zip([0, 1], [1, 2])), None, 3) sage: p.set_objective([2, 5]) sage: import sage.numerical.backends.glpk_backend as backend sage: p.solver_parameter(backend.glp_simplex_or_intopt, backend.glp_simplex_only) sage: p.print_ranges() glp_print_ranges: optimal basic solution required 1 sage: p.solve() 0 sage: p.print_ranges() Write sensitivity analysis report to... GLPK ... - SENSITIVITY ANALYSIS REPORT Page 1 <BLANKLINE> Problem: Objective: 7.5 (MAXimum) <BLANKLINE> No. Row name St Activity Slack Lower bound Activity Obj coef Obj value at Limiting Marginal Upper bound range range break point variable ------ ------------ -- ------------- ------------- ------------- ------------- ------------- ------------- ------------ 1 NU 3.00000 . -Inf . -2.50000 . 2.50000 3.00000 +Inf +Inf +Inf <BLANKLINE> GLPK ... - SENSITIVITY ANALYSIS REPORT Page 2 <BLANKLINE> Problem: Objective: 7.5 (MAXimum) <BLANKLINE> No. Column name St Activity Obj coef Lower bound Activity Obj coef Obj value at Limiting Marginal Upper bound range range break point variable ------ ------------ -- ------------- ------------- ------------- ------------- ------------- ------------- ------------ 1 NL . 2.00000 . -Inf -Inf +Inf -.50000 +Inf 3.00000 2.50000 6.00000 <BLANKLINE> 2 BS 1.50000 5.00000 . -Inf 4.00000 6.00000 . +Inf 1.50000 +Inf +Inf <BLANKLINE> End of report <BLANKLINE> 0
-
problem_name
(name='NULL')¶ Return or define the problem’s name
INPUT:
name
(char *
) – the problem’s name. When set toNULL
(default), the method returns the problem’s name.
EXAMPLE:
sage: from sage.numerical.backends.generic_backend import get_solver sage: p = get_solver(solver = "GLPK") sage: p.problem_name("There once was a french fry") sage: print(p.problem_name()) There once was a french fry
-
remove_constraint
(i)¶ Remove a constraint from self.
INPUT:
i
– index of the constraint to remove
EXAMPLE:
sage: p = MixedIntegerLinearProgram(solver='GLPK') sage: x, y = p['x'], p['y'] sage: p.add_constraint(2*x + 3*y <= 6) sage: p.add_constraint(3*x + 2*y <= 6) sage: p.add_constraint(x >= 0) sage: p.set_objective(x + y + 7) sage: p.set_integer(x); p.set_integer(y) sage: p.solve() 9.0 sage: p.remove_constraint(0) sage: p.solve() 10.0
Removing fancy constraints does not make Sage crash:
sage: MixedIntegerLinearProgram(solver = "GLPK").remove_constraint(-2) Traceback (most recent call last): ... ValueError: The constraint's index i must satisfy 0 <= i < number_of_constraints
-
remove_constraints
(constraints)¶ Remove several constraints.
INPUT:
constraints
– an iterable containing the indices of the rows to remove.
EXAMPLE:
sage: p = MixedIntegerLinearProgram(solver='GLPK') sage: x, y = p['x'], p['y'] sage: p.add_constraint(2*x + 3*y <= 6) sage: p.add_constraint(3*x + 2*y <= 6) sage: p.add_constraint(x >= 0) sage: p.set_objective(x + y + 7) sage: p.set_integer(x); p.set_integer(y) sage: p.solve() 9.0 sage: p.remove_constraints([0]) sage: p.solve() 10.0 sage: p.get_values([x,y]) [0.0, 3.0]
TESTS:
Removing fancy constraints does not make Sage crash:
sage: MixedIntegerLinearProgram(solver= "GLPK").remove_constraints([0, -2]) Traceback (most recent call last): ... ValueError: The constraint's index i must satisfy 0 <= i < number_of_constraints
-
row
(index)¶ 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.EXAMPLE:
sage: from sage.numerical.backends.generic_backend import get_solver sage: p = get_solver(solver = "GLPK") sage: p.add_variables(5) 4 sage: p.add_linear_constraint(list(zip(range(5), range(5))), 2, 2) sage: p.row(0) ([4, 3, 2, 1], [4.0, 3.0, 2.0, 1.0]) sage: p.row_bounds(0) (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.EXAMPLE:
sage: from sage.numerical.backends.generic_backend import get_solver sage: p = get_solver(solver = "GLPK") sage: p.add_variables(5) 4 sage: p.add_linear_constraint(list(zip(range(5), range(5))), 2, 2) sage: p.row(0) ([4, 3, 2, 1], [4.0, 3.0, 2.0, 1.0]) sage: p.row_bounds(0) (2.0, 2.0)
-
row_name
(index)¶ Return the
index
th row nameINPUT:
index
(integer) – the row’s id
EXAMPLE:
sage: from sage.numerical.backends.generic_backend import get_solver sage: p = get_solver(solver = "GLPK") sage: p.add_linear_constraints(1, 2, None, names=['Empty constraint 1']) sage: p.row_name(0) 'Empty constraint 1'
-
set_col_stat
(j, stat)¶ Set the status of a variable.
INPUT:
j
– The index of the constraintstat
– The status to set to
EXAMPLE:
sage: from sage.numerical.backends.generic_backend import get_solver sage: lp = get_solver(solver = "GLPK") sage: lp.add_variables(3) 2 sage: lp.add_linear_constraint(list(zip([0, 1, 2], [8, 6, 1])), None, 48) sage: lp.add_linear_constraint(list(zip([0, 1, 2], [4, 2, 1.5])), None, 20) sage: lp.add_linear_constraint(list(zip([0, 1, 2], [2, 1.5, 0.5])), None, 8) sage: lp.set_objective([60, 30, 20]) sage: import sage.numerical.backends.glpk_backend as backend sage: lp.solver_parameter(backend.glp_simplex_or_intopt, backend.glp_simplex_only) sage: lp.solve() 0 sage: lp.get_col_stat(0) 1 sage: lp.set_col_stat(0, 2) sage: lp.get_col_stat(0) 2
-
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)
EXAMPLE:
sage: from sage.numerical.backends.generic_backend import get_solver sage: p = get_solver(solver = "GLPK") 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.0, 1.0, 2.0, 1.0, 3.0]
-
set_row_stat
(i, stat)¶ Set the status of a constraint.
INPUT:
i
– The index of the constraintstat
– The status to set to
EXAMPLE:
sage: from sage.numerical.backends.generic_backend import get_solver sage: lp = get_solver(solver = "GLPK") sage: lp.add_variables(3) 2 sage: lp.add_linear_constraint(list(zip([0, 1, 2], [8, 6, 1])), None, 48) sage: lp.add_linear_constraint(list(zip([0, 1, 2], [4, 2, 1.5])), None, 20) sage: lp.add_linear_constraint(list(zip([0, 1, 2], [2, 1.5, 0.5])), None, 8) sage: lp.set_objective([60, 30, 20]) sage: import sage.numerical.backends.glpk_backend as backend sage: lp.solver_parameter(backend.glp_simplex_or_intopt, backend.glp_simplex_only) sage: lp.solve() 0 sage: lp.get_row_stat(0) 1 sage: lp.set_row_stat(0, 3) sage: lp.get_row_stat(0) 3
-
set_sense
(sense)¶ Set the direction (maximization/minimization).
INPUT:
sense
(integer) :- +1 => Maximization
- -1 => Minimization
EXAMPLE:
sage: from sage.numerical.backends.generic_backend import get_solver sage: p = get_solver(solver = "GLPK") sage: p.is_maximization() True sage: p.set_sense(-1) sage: p.is_maximization() 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 Real
EXAMPLE:
sage: from sage.numerical.backends.generic_backend import get_solver sage: p = get_solver(solver = "GLPK") sage: p.ncols() 0 sage: p.add_variable() 0 sage: p.set_variable_type(0,1) sage: p.is_variable_integer(0) True
-
set_verbosity
(level)¶ Set the verbosity level
INPUT:
level
(integer) – From 0 (no verbosity) to 3.
EXAMPLE:
sage: from sage.numerical.backends.generic_backend import get_solver sage: p = get_solver(solver = "GLPK") sage: p.set_verbosity(2)
-
solve
()¶ Solve the problem.
Sage uses GLPK’s implementation of the branch-and-cut algorithm (
glp_intopt
) to solve the mixed-integer linear program. This algorithm can be requested explicitly by setting the solver parameter “simplex_or_intopt” to “intopt_only”. (If all variables are continuous, the algorithm reduces to solving the linear program by the simplex method.)EXAMPLE:
sage: lp = MixedIntegerLinearProgram(solver = 'GLPK', maximization = False) sage: x, y = lp[0], lp[1] sage: lp.add_constraint(-2*x + y <= 1) sage: lp.add_constraint(x - y <= 1) sage: lp.add_constraint(x + y >= 2) sage: lp.set_objective(x + y) sage: lp.set_integer(x) sage: lp.set_integer(y) sage: lp.solve() 2.0 sage: lp.get_values([x, y]) [1.0, 1.0]
Note
This method raises
MIPSolverException
exceptions when the solution can not be computed for any reason (none exists, or the LP solver was not able to find it, etc...)EXAMPLE:
sage: from sage.numerical.backends.generic_backend import get_solver sage: p = get_solver(solver = "GLPK") sage: p.add_linear_constraints(5, 0, None) sage: p.add_col(range(5), range(5)) sage: p.solve() 0 sage: p.objective_coefficient(0,1) sage: p.solve() Traceback (most recent call last): ... MIPSolverException: ...
Warning
Sage uses GLPK’s
glp_intopt
to find solutions. This routine sometimes FAILS CATASTROPHICALLY when given a system it cannot solve. (trac ticket #12309.) Here, “catastrophic” can mean either “infinite loop” or segmentation fault. Upstream considers this behavior “essentially innate” to their design, and suggests preprocessing it withglp_simplex
first. Thus, if you suspect that your system is infeasible, set thepreprocessing
option first.EXAMPLE:
sage: lp = MixedIntegerLinearProgram(solver = "GLPK") sage: v = lp.new_variable(nonnegative=True) sage: lp.add_constraint(v[1] +v[2] -2.0 *v[3], max=-1.0) sage: lp.add_constraint(v[0] -4.0/3 *v[1] +1.0/3 *v[2], max=-1.0/3) sage: lp.add_constraint(v[0] +0.5 *v[1] -0.5 *v[2] +0.25 *v[3], max=-0.25) sage: lp.solve() 0.0 sage: lp.add_constraint(v[0] +4.0 *v[1] -v[2] +v[3], max=-1.0) sage: lp.solve() Traceback (most recent call last): ... GLPKError: Assertion failed: ... sage: lp.solver_parameter("simplex_or_intopt", "simplex_then_intopt") sage: lp.solve() Traceback (most recent call last): ... MIPSolverException: GLPK: Problem has no feasible solution
If we switch to “simplex_only”, the integrality constraints are ignored, and we get an optimal solution to the continuous relaxation.
EXAMPLE:
sage: lp = MixedIntegerLinearProgram(solver = 'GLPK', maximization = False) sage: x, y = lp[0], lp[1] sage: lp.add_constraint(-2*x + y <= 1) sage: lp.add_constraint(x - y <= 1) sage: lp.add_constraint(x + y >= 2) sage: lp.set_objective(x + y) sage: lp.set_integer(x) sage: lp.set_integer(y) sage: lp.solver_parameter("simplex_or_intopt", "simplex_only") # use simplex only sage: lp.solve() 2.0 sage: lp.get_values([x, y]) [1.5, 0.5]
If one solves a linear program and wishes to access dual information (\(get_col_dual\) etc.) or tableau data (\(get_row_stat\) etc.), one needs to switch to “simplex_only” before solving.
GLPK also has an exact rational simplex solver. The only access to data is via double-precision floats, however. It reconstructs rationals from doubles and also provides results as doubles.
EXAMPLE:
sage: lp.solver_parameter("simplex_or_intopt", "exact_simplex_only") # use exact simplex only sage: lp.solve() glp_exact: 3 rows, 2 columns, 6 non-zeros GNU MP bignum library is being used ... OPTIMAL SOLUTION FOUND 2.0 sage: lp.get_values([x, y]) [1.5, 0.5]
If you need the rational solution, you need to retrieve the basis information via
get_col_stat
andget_row_stat
and calculate the corresponding basic solution. Below we only test that the basis information is indeed available. Calculating the corresponding basic solution is left as an exercise.EXAMPLE:
sage: lp.get_backend().get_row_stat(0) 1 sage: lp.get_backend().get_col_stat(0) 1
Below we test that integers that can be exactly represented by IEEE 754 double-precision floating point numbers survive the rational reconstruction done by
glp_exact
and the subsequent conversion to double-precision floating point numbers.EXAMPLE:
sage: lp = MixedIntegerLinearProgram(solver = 'GLPK', maximization = True) sage: test = 2^53 - 43 sage: lp.solver_parameter("simplex_or_intopt", "exact_simplex_only") # use exact simplex only sage: x = lp[0] sage: lp.add_constraint(x <= test) sage: lp.set_objective(x) sage: lp.solve() == test # yes, we want an exact comparison here glp_exact: 1 rows, 1 columns, 1 non-zeros GNU MP bignum library is being used ... OPTIMAL SOLUTION FOUND True sage: lp.get_values(x) == test # yes, we want an exact comparison here True
Below we test that GLPK backend can detect unboundedness in “simplex_only” mode (trac ticket #18838).
EXAMPLES:
sage: lp = MixedIntegerLinearProgram(maximization=True, solver = "GLPK") sage: lp.set_objective(lp[0]) sage: lp.solver_parameter("simplex_or_intopt", "simplex_only") sage: lp.solve() Traceback (most recent call last): ... MIPSolverException: GLPK: Problem has unbounded solution sage: lp.set_objective(lp[1]) sage: lp.solver_parameter("primal_v_dual", "GLP_DUAL") sage: lp.solve() Traceback (most recent call last): ... MIPSolverException: GLPK: Problem has unbounded solution sage: lp.solver_parameter("simplex_or_intopt", "simplex_then_intopt") sage: lp.solve() Traceback (most recent call last): ... MIPSolverException: GLPK: The LP (relaxation) problem has no dual feasible solution sage: lp.solver_parameter("simplex_or_intopt", "intopt_only") sage: lp.solve() Traceback (most recent call last): ... MIPSolverException: GLPK: The LP (relaxation) problem has no dual feasible solution sage: lp.set_max(lp[1],5) sage: lp.solve() 5.0
Solving a LP within the acceptable gap. No exception is raised, even if the result is not optimal. To do this, we try to compute the maximum number of disjoint balls (of diameter 1) in a hypercube:
sage: g = graphs.CubeGraph(9) sage: p = MixedIntegerLinearProgram(solver="GLPK") sage: p.solver_parameter("mip_gap_tolerance",100) sage: b = p.new_variable(binary=True) sage: p.set_objective(p.sum(b[v] for v in g)) sage: for v in g: ....: p.add_constraint(b[v]+p.sum(b[u] for u in g.neighbors(v)) <= 1) sage: p.add_constraint(b[v] == 1) # Force an easy non-0 solution sage: p.solve() # rel tol 100 1
Same, now with a time limit:
sage: p.solver_parameter("mip_gap_tolerance",1) sage: p.solver_parameter("timelimit",3.0) sage: p.solve() # rel tol 100 1
-
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.
You can supply the name of a parameter and its value using either a string or a
glp_
constant (which are defined as Cython variables of this module).In most cases, you can use the same name for a parameter as that given in the GLPK documentation, which is available by downloading GLPK from <http://www.gnu.org/software/glpk/>. The exceptions relate to parameters common to both methods; these require you to append
_simplex
or_intopt
to the name to resolve ambiguity, since the interface allows access to both.We have also provided more meaningful names, to assist readability.
Parameter names are specified in lower case. To use a constant instead of a string, prepend
glp_
to the name. For example, bothglp_gmi_cuts
or"gmi_cuts"
control whether to solve using Gomory cuts.Parameter values are specificed as strings in upper case, or as constants in lower case. For example, both
glp_on
and"GLP_ON"
specify the same thing.Naturally, you can use
True
andFalse
in cases whereglp_on
andglp_off
would be used.A list of parameter names, with their possible values:
General-purpose parameters:
timelimit
specify the time limit IN SECONDS. This affects both simplex and intopt. timelimit_simplex
andtimelimit_intopt
specify the time limit IN MILLISECONDS. (This is glpk’s default.) simplex_or_intopt
specifiy which of simplex
,exact
andintopt
routines in GLPK to use. This is controlled by settingsimplex_or_intopt
toglp_simplex_only
,glp_exact_simplex_only
,glp_intopt_only
andglp_simplex_then_intopt
, respectively. The latter is useful to deal with a problem in GLPK where problems with no solution hang when using integer optimization; if you specifyglp_simplex_then_intopt
, sage will try simplex first, then perform integer optimization only if a solution of the LP relaxation exists.verbosity_intopt
andverbosity_simplex
one of GLP_MSG_OFF
,GLP_MSG_ERR
,GLP_MSG_ON
, orGLP_MSG_ALL
. The default isGLP_MSG_OFF
.output_frequency_intopt
andoutput_frequency_simplex
the output frequency, in milliseconds. Default is 5000. output_delay_intopt
andoutput_delay_simplex
the output delay, in milliseconds, regarding the use of the simplex method on the LP relaxation. Default is 10000. intopt-specific parameters:
branching
GLP_BR_FFV
first fractional variableGLP_BR_LFV
last fractional variableGLP_BR_MFV
most fractional variableGLP_BR_DTH
Driebeck-Tomlin heuristic (default)GLP_BR_PCH
hybrid pseudocost heuristic
backtracking
GLP_BT_DFS
depth first searchGLP_BT_BFS
breadth first searchGLP_BT_BLB
best local bound (default)GLP_BT_BPH
best projection heuristic
preprocessing
GLP_PP_NONE
GLP_PP_ROOT
preprocessing only at root levelGLP_PP_ALL
(default)
feasibility_pump
GLP_ON
orGLP_OFF
(default)gomory_cuts
GLP_ON
orGLP_OFF
(default)mixed_int_rounding_cuts
GLP_ON
orGLP_OFF
(default)mixed_cover_cuts
GLP_ON
orGLP_OFF
(default)clique_cuts
GLP_ON
orGLP_OFF
(default)absolute_tolerance
(double) used to check if optimal solution to LP relaxation is integer feasible. GLPK manual advises, “do not change... without detailed understanding of its purpose.” relative_tolerance
(double) used to check if objective value in LP relaxation is not better than best known integer solution. GLPK manual advises, “do not change... without detailed understanding of its purpose.” mip_gap_tolerance
(double) relative mip gap tolerance. Default is 0.0. presolve_intopt
GLP_ON
(default) orGLP_OFF
.binarize
GLP_ON
orGLP_OFF
(default)simplex-specific parameters:
primal_v_dual
GLP_PRIMAL
(default)GLP_DUAL
GLP_DUALP
pricing
GLP_PT_STD
standard (textbook)GLP_PT_PSE
projected steepest edge (default)
ratio_test
GLP_RT_STD
standard (textbook)GLP_RT_HAR
Harris’ two-pass ratio test (default)
tolerance_primal
(double) tolerance used to check if basic solution is primal feasible. GLPK manual advises, “do not change... without detailed understanding of its purpose.” tolerance_dual
(double) tolerance used to check if basic solution is dual feasible. GLPK manual advises, “do not change... without detailed understanding of its purpose.” tolerance_pivot
(double) tolerance used to choose pivot. GLPK manual advises, “do not change... without detailed understanding of its purpose.” obj_lower_limit
(double) lower limit of the objective function. The default is -DBL_MAX
.obj_upper_limit
(double) upper limit of the objective function. The default is DBL_MAX
.iteration_limit
(int) iteration limit of the simplex algorithm. The default is INT_MAX
.presolve_simplex
GLP_ON
orGLP_OFF
(default).Note
The coverage for GLPK’s control parameters for simplex and integer optimization is nearly complete. The only thing lacking is a wrapper for callback routines.
To date, no attempt has been made to expose the interior point methods.
EXAMPLE:
sage: from sage.numerical.backends.generic_backend import get_solver sage: p = get_solver(solver = "GLPK") sage: p.solver_parameter("timelimit", 60) sage: p.solver_parameter("timelimit") 60.0
- Don’t forget the difference between
timelimit
andtimelimit_intopt
sage: p.solver_parameter("timelimit_intopt") 60000
If you don’t care for an integer answer, you can ask for an LP relaxation instead. The default solver performs integer optimization, but you can switch to the standard simplex algorithm through the
glp_simplex_or_intopt
parameter.EXAMPLE:
sage: lp = MixedIntegerLinearProgram(solver = 'GLPK', maximization = False) sage: x, y = lp[0], lp[1] sage: lp.add_constraint(-2*x + y <= 1) sage: lp.add_constraint(x - y <= 1) sage: lp.add_constraint(x + y >= 2) sage: lp.set_integer(x); lp.set_integer(y) sage: lp.set_objective(x + y) sage: lp.solve() 2.0 sage: lp.get_values([x,y]) [1.0, 1.0] sage: import sage.numerical.backends.glpk_backend as backend sage: lp.solver_parameter(backend.glp_simplex_or_intopt, backend.glp_simplex_only) sage: lp.solve() 2.0 sage: lp.get_values([x,y]) [1.5, 0.5]
You can get GLPK to spout all sorts of information at you. The default is to turn this off, but sometimes (debugging) it’s very useful:
sage: lp.solver_parameter(backend.glp_simplex_or_intopt, backend.glp_simplex_then_intopt) sage: lp.solver_parameter(backend.glp_mir_cuts, backend.glp_on) sage: lp.solver_parameter(backend.glp_msg_lev_intopt, backend.glp_msg_all) sage: lp.solver_parameter(backend.glp_mir_cuts) 1
If you actually try to solve
lp
, you will get a lot of detailed information.
-
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.
EXAMPLE:
sage: from sage.numerical.backends.generic_backend import get_solver sage: p = get_solver(solver = "GLPK") sage: p.add_variable() 0 sage: p.col_bounds(0) (0.0, None) sage: p.variable_lower_bound(0, 5) sage: p.col_bounds(0) (5.0, None)
TESTS:
sage: P = MixedIntegerLinearProgram(solver="GLPK") sage: x = P["x"] sage: P.set_min(x, 5) sage: P.set_min(x, 0) sage: P.get_min(x) 0.0
Check that trac ticket #10232 is fixed:
sage: p = get_solver(solver="GLPK") sage: p.variable_lower_bound(2) Traceback (most recent call last): ... GLPKError: ... sage: p.variable_lower_bound(3, 5) Traceback (most recent call last): ... GLPKError: ... sage: p.add_variable() 0 sage: p.variable_lower_bound(0, 'hey!') Traceback (most recent call last): ... TypeError: a float is required
-
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.
EXAMPLE:
sage: from sage.numerical.backends.generic_backend import get_solver sage: p = get_solver(solver = "GLPK") sage: p.add_variable() 0 sage: p.col_bounds(0) (0.0, None) sage: p.variable_upper_bound(0, 5) sage: p.col_bounds(0) (0.0, 5.0)
TESTS:
sage: P = MixedIntegerLinearProgram(solver="GLPK") sage: x = P["x"] sage: P.set_max(x, 0) sage: P.get_max(x) 0.0
Check that trac ticket #10232 is fixed:
sage: p = get_solver(solver="GLPK") sage: p.variable_upper_bound(2) Traceback (most recent call last): ... GLPKError: ... sage: p.variable_upper_bound(3, 5) Traceback (most recent call last): ... GLPKError: ... sage: p.add_variable() 0 sage: p.variable_upper_bound(0, 'hey!') Traceback (most recent call last): ... TypeError: a float is required
-
warm_up
()¶ Warm up the basis using current statuses assigned to rows and cols.
OUTPUT:
Returns the warming up status
- 0 The operation has been successfully performed.
- GLP_EBADB The basis matrix is invalid.
- GLP_ESING The basis matrix is singular within the working precision.
- GLP_ECOND The basis matrix is ill-conditioned.
EXAMPLE:
sage: from sage.numerical.backends.generic_backend import get_solver sage: lp = get_solver(solver = "GLPK") sage: lp.add_variables(3) 2 sage: lp.add_linear_constraint(list(zip([0, 1, 2], [8, 6, 1])), None, 48) sage: lp.add_linear_constraint(list(zip([0, 1, 2], [4, 2, 1.5])), None, 20) sage: lp.add_linear_constraint(list(zip([0, 1, 2], [2, 1.5, 0.5])), None, 8) sage: lp.set_objective([60, 30, 20]) sage: import sage.numerical.backends.glpk_backend as backend sage: lp.solver_parameter(backend.glp_simplex_or_intopt, backend.glp_simplex_only) sage: lp.solve() 0 sage: lp.get_objective_value() 280.0 sage: lp.set_row_stat(0,3) sage: lp.set_col_stat(1,1) sage: lp.warm_up() 0
-
write_lp
(filename)¶ Write the problem to a .lp file
INPUT:
filename
(string)
EXAMPLE:
sage: from sage.numerical.backends.generic_backend import get_solver sage: p = get_solver(solver = "GLPK") 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.write_lp(os.path.join(SAGE_TMP, "lp_problem.lp")) Writing problem data to ... 9 lines were written
-
write_mps
(filename, modern)¶ Write the problem to a .mps file
INPUT:
filename
(string)
EXAMPLE:
sage: from sage.numerical.backends.generic_backend import get_solver sage: p = get_solver(solver = "GLPK") 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.write_mps(os.path.join(SAGE_TMP, "lp_problem.mps"), 2) Writing problem data to... 17 records were written
-