Interactive MILP problem classes, MILP tableau classes, and the cutting plane method

class sage_numerical_interactive_mip.interactive_milp_problem.InteractiveMILPProblem(A=None, b=None, c=None, x='x', constraint_type='<=', variable_type='', problem_type='max', base_ring=None, is_primal=True, objective_constant_term=0, relaxation=None, integer_variables=False)

Bases: SageObject

Construct an MILP (Mixed Integer Linear Programming) problem.

This class supports MILP problems with “variables on the left” constraints.

INPUT:

  • A – a matrix of constraint coefficients

  • b – a vector of constraint constant terms

  • c – a vector of objective coefficients

  • x – (default: "x") a vector of decision variables or a string giving the base name

  • constraint_type – (default: "<=") a string specifying constraint type(s): either "<=", ">=", "==", or a list of them

  • variable_type – (default: "") a string specifying variable type(s): either ">=", "<=", "" (the empty string), or a list of them, corresponding, respectively, to non-negative, non-positive, and free variables

  • problem_type – (default: "max") a string specifying the problem type: "max", "min", "-max", or "-min"

  • base_ring – (default: the fraction field of a common ring for all input coefficients) a field to which all input coefficients will be converted

  • is_primal – (default: True) whether this problem is primal or dual: each problem is of course dual to its own dual, this flag is mostly for internal use and affects default variable names only

  • objective_constant_term – (default: 0) a constant term of the objective

  • relaxation – (default: None) an LP problem as the relaxation of the problem

  • integer_variables – (default: False) either a boolean value indicating if all the problem variables are integer or not, or a set of strings giving some problem variables’ names, where those problem variables are integer

EXAMPLES:

We will first construct the following problem directly:

\[\begin{split}\begin{array}{l} \begin{array}{lcrcrcl} \max \mspace{-6mu}&\mspace{-6mu} \mspace{-6mu}&\mspace{-6mu} 10 C \mspace{-6mu}&\mspace{-6mu} + \mspace{-6mu}&\mspace{-6mu} 5 B \mspace{-6mu}&\mspace{-6mu} \mspace{-6mu}&\mspace{-6mu} \\ \mspace{-6mu}&\mspace{-6mu} \mspace{-6mu}&\mspace{-6mu} C \mspace{-6mu}&\mspace{-6mu} + \mspace{-6mu}&\mspace{-6mu} B \mspace{-6mu}&\mspace{-6mu} \leq \mspace{-6mu}&\mspace{-6mu} 1000 \\ \mspace{-6mu}&\mspace{-6mu} \mspace{-6mu}&\mspace{-6mu} 3 C \mspace{-6mu}&\mspace{-6mu} + \mspace{-6mu}&\mspace{-6mu} B \mspace{-6mu}&\mspace{-6mu} \leq \mspace{-6mu}&\mspace{-6mu} 1500 \\ \end{array} \\ & C, B \geq 0 \\ & C, B \in \mathbb{Z} \end{array}\end{split}\]
sage: from sage_numerical_interactive_mip import *
sage: A = ([1, 1], [3, 1])
sage: b = (1000, 1500)
sage: c = (10, 5)
sage: P = InteractiveMILPProblem(A, b, c, ["C", "B"], variable_type=">=",
....:     integer_variables=True)

Same problem, but more explicitly:

sage: P = InteractiveMILPProblem(A, b, c, ["C", "B"], constraint_type="<=",
....:     variable_type=">=", integer_variables=True)

Even more explicitly:

sage: P = InteractiveMILPProblem(A, b, c, ["C", "B"], problem_type="max",
....:     constraint_type=["<=", "<="], variable_type=[">=", ">="],
....:     integer_variables=True)

Similar problem, but specifying which decision variable is integer:

sage: P = InteractiveMILPProblem(A, b, c, ["C", "B"], problem_type="max",
....:     constraint_type=["<=", "<="], variable_type=[">=", ">="],
....:     integer_variables={'C'})

Using the last form you should be able to represent any MILP problem, as long as all like terms are collected and in constraints variables and constants are on different sides.

We will construct the same problem by calling with_relaxation() in InteractiveMILPProblem:

sage: R = InteractiveLPProblem(A, b, c, ["C", "B"], problem_type="max",
....:     constraint_type=["<=", "<="], variable_type=[">=", ">="])
sage: P = InteractiveMILPProblem.with_relaxation(R, {'C'})

See with_relaxation() in InteractiveMILPProblem for more documentation.

A()

Return coefficients of constraints of the relaxation of self, i.e. \(A\).

OUTPUT: a matrix

EXAMPLES:

sage: from sage_numerical_interactive_mip import *
sage: A = ([1, 1], [3, 1])
sage: b = (1000, 1500)
sage: c = (10, 5)
sage: P = InteractiveMILPProblem(A, b, c, ["C", "B"], variable_type=">=")
sage: P.constraint_coefficients()
[1 1]
[3 1]
sage: P.A()
[1 1]
[3 1]
Abcx()

Return \(A\), \(b\), \(c\), and \(x\) of the relaxation of self as a tuple.

OUTPUT: a tuple

EXAMPLES:

sage: from sage_numerical_interactive_mip import *
sage: A = ([1, 1], [3, 1])
sage: b = (1000, 1500)
sage: c = (10, 5)
sage: P = InteractiveMILPProblem(A, b, c, ["C", "B"], variable_type=">=")
sage: P.Abcx()
(
[1 1]
[3 1], (1000, 1500), (10, 5), (C, B)
)
__eq__(other)

Check if two LP problems are equal.

INPUT:

  • other – anything

OUTPUT:

  • True if other is an InteractiveLPProblem with all details the same as self, False otherwise.

TESTS:

sage: from sage_numerical_interactive_mip import *
sage: A = ([1, 1], [3, 1])
sage: b = (1000, 1500)
sage: c = (10, 5)
sage: P = InteractiveMILPProblem(A, b, c, variable_type=">=", integer_variables={"x1"})
sage: P2 = InteractiveMILPProblem(A, b, c, variable_type=">=", integer_variables={"x1"})
sage: P == P2
True
sage: P3 = InteractiveMILPProblem(A, b, c, variable_type=">=")
sage: P == P3
False
sage: R = InteractiveLPProblem(A, b, c, variable_type=">=")
sage: P4 = InteractiveMILPProblem.with_relaxation(relaxation=R, integer_variables={"x1"})
sage: P == P4
True
__hash__ = None
__init__(A=None, b=None, c=None, x='x', constraint_type='<=', variable_type='', problem_type='max', base_ring=None, is_primal=True, objective_constant_term=0, relaxation=None, integer_variables=False)

See InteractiveMILPProblem for documentation.

TESTS:

sage: from sage_numerical_interactive_mip import *
sage: A = ([1, 1], [3, 1])
sage: b = (1000, 1500)
sage: c = (10, 5)
sage: P = InteractiveMILPProblem(A, b, c, ["C", "B"], constraint_type="<=",
....:     variable_type=">=", integer_variables=True)
sage: TestSuite(P).run()
__weakref__

list of weak references to the object

_get_plot_bounding_box(F, b, xmin=None, xmax=None, ymin=None, ymax=None)

Return the min and max for x and y of the bounding box for self.

INPUT:

  • F – the feasible set of self

  • b – the constant terms of self

  • xmin, xmax, ymin, ymax – bounds for the axes, if not given, an attempt will be made to pick reasonable values

OUTPUT: four rational numbers

_latex_()

Return a LaTeX representation of self.

OUTPUT:

  • a string

TESTS:

sage: from sage_numerical_interactive_mip import *
sage: A = ([1, 1, 2], [3, 1, 7], [6, 4, 5])
sage: b = (1000, 1500, 2000)
sage: c = (10, 5, 1)
sage: P = InteractiveMILPProblem(A, b, c, variable_type=">=", integer_variables={'x1'})
sage: print(P._latex_())
\begin{array}{l}
\begin{array}{lcrcrcrcl}
 \max \mspace{-6mu}&\mspace{-6mu}  \mspace{-6mu}&\mspace{-6mu} 10 x_{1} \mspace{-6mu}&\mspace{-6mu} + \mspace{-6mu}&\mspace{-6mu} 5 x_{2} \mspace{-6mu}&\mspace{-6mu} + \mspace{-6mu}&\mspace{-6mu} x_{3} \mspace{-6mu}&\mspace{-6mu}  \mspace{-6mu}&\mspace{-6mu} \\
 \mspace{-6mu}&\mspace{-6mu}  \mspace{-6mu}&\mspace{-6mu} x_{1} \mspace{-6mu}&\mspace{-6mu} + \mspace{-6mu}&\mspace{-6mu} x_{2} \mspace{-6mu}&\mspace{-6mu} + \mspace{-6mu}&\mspace{-6mu} 2 x_{3} \mspace{-6mu}&\mspace{-6mu} \leq \mspace{-6mu}&\mspace{-6mu} 1000 \\
 \mspace{-6mu}&\mspace{-6mu}  \mspace{-6mu}&\mspace{-6mu} 3 x_{1} \mspace{-6mu}&\mspace{-6mu} + \mspace{-6mu}&\mspace{-6mu} x_{2} \mspace{-6mu}&\mspace{-6mu} + \mspace{-6mu}&\mspace{-6mu} 7 x_{3} \mspace{-6mu}&\mspace{-6mu} \leq \mspace{-6mu}&\mspace{-6mu} 1500 \\
 \mspace{-6mu}&\mspace{-6mu}  \mspace{-6mu}&\mspace{-6mu} 6 x_{1} \mspace{-6mu}&\mspace{-6mu} + \mspace{-6mu}&\mspace{-6mu} 4 x_{2} \mspace{-6mu}&\mspace{-6mu} + \mspace{-6mu}&\mspace{-6mu} 5 x_{3} \mspace{-6mu}&\mspace{-6mu} \leq \mspace{-6mu}&\mspace{-6mu} 2000 \\
\end{array} \\
x_{1}, x_{2}, x_{3} \geq 0
 \\x_{1} \in \mathbb{Z} \\x_{2}, x_{3} \in \mathbb{R}\end{array}
_plot_constraint_or_cut(Ai, bi, ri, color, box, x, alpha=0.2, pad=None, ith_cut=None)

Return a plot of the constraint or cut of self.

INPUT:

  • Ai – the coefficients for the constraint or cut

  • bi – the constant for the constraint or cut

  • ri – a string indicating the type for the constraint or cut

  • color – a color

  • box – a bounding box for the plot

  • x – the decision variables of the problem

  • alpha – (default: 0.2) determines how opaque are shadows

  • pad – an integer

  • ith_cut – an integer indicating the order of the cut

OUTPUT: a plot

_repr_()

Return a string representation of self.

OUTPUT: a string

TESTS:

sage: from sage_numerical_interactive_mip import *
sage: A = ([1, 1], [3, 1])
sage: b = (1000, 1500)
sage: c = (10, 5)
sage: P = InteractiveMILPProblem(A, b, c, variable_type=">=", integer_variables={"x1"})
sage: print(P._repr_())
MILP problem (use ... details)
_solution(x)

Return x as a normalized solution of the relaxation of self.

INPUT:

  • x – anything that can be interpreted as a solution of this problem, e.g. a vector or a list of correct length or a single element list with such a vector

OUTPUT: x as a vector

EXAMPLES:

sage: from sage_numerical_interactive_mip import *
sage: A = ([1, 1], [3, 1])
sage: b = (1000, 1500)
sage: c = (10, 5)
sage: P = InteractiveMILPProblem(A, b, c, variable_type=">=")
sage: P._solution([100, 200])
(100, 200)
sage: P._solution([[100, 200]])
(100, 200)
sage: P._solution([1000])
Traceback (most recent call last):
...
TypeError: given input is not a solution for this problem
add_constraint(coefficients, constant_term, constraint_type='<=')

Return a new MILP problem by adding a constraint to``self``.

INPUT:

  • coefficients – coefficients of the new constraint

  • constant_term – a constant term of the new constraint

  • constraint_type – (default: "<=") a string indicating the constraint type of the new constraint

OUTPUT: an MILP problem

EXAMPLES:

sage: from sage_numerical_interactive_mip import *
sage: A = ([1, 1], [3, 1])
sage: b = (1000, 1500)
sage: c = (10, 5)
sage: P = InteractiveMILPProblem(A, b, c)
sage: P1 = P.add_constraint(([2, 4]), 2000, constraint_type="<=")
sage: P1.Abcx()
(
[1 1]
[3 1]
[2 4], (1000, 1500, 2000), (10, 5), (x1, x2)
)
sage: P1.constraint_types()
('<=', '<=', '<=')
sage: P.Abcx()
(
[1 1]
[3 1], (1000, 1500), (10, 5), (x1, x2)
)
sage: P.constraint_types()
('<=', '<=')
sage: P2 = P.add_constraint(([2, 4, 6]), 2000, constraint_type="<=")
Traceback (most recent call last):
...
TypeError: number of columns must be the same, not 2 and 3
sage: P3 = P.add_constraint(([2, 4]), 2000, constraint_type="<")
Traceback (most recent call last):
...
ValueError: unknown constraint type
all_variables()

Return a set of all decision variables of self.

OUTPUT: a set of variables

EXAMPLES:

sage: from sage_numerical_interactive_mip import *
sage: A = ([1, 2, 1], [3, 1, 5])
sage: b = (1000, 1500)
sage: c = (10, 5, 7)
sage: P = InteractiveMILPProblem(A, b, c)
sage: P.all_variables()
{x1, x2, x3}
b()

Return constant terms of constraints of the relaxation of self, i.e. \(b\).

OUTPUT: a vector

EXAMPLES:

sage: from sage_numerical_interactive_mip import *
sage: A = ([1, 1], [3, 1])
sage: b = (1000, 1500)
sage: c = (10, 5)
sage: P = InteractiveMILPProblem(A, b, c, ["C", "B"], variable_type=">=")
sage: P.constant_terms()
(1000, 1500)
sage: P.b()
(1000, 1500)
base_ring()

Return the base ring of the relaxation of self.

Note

The base ring of MILP problems is always a field.

OUTPUT: a ring

EXAMPLES:

sage: from sage_numerical_interactive_mip import *
sage: A = ([1, 1], [3, 1])
sage: b = (1000, 1500)
sage: c = (10, 5)
sage: P = InteractiveMILPProblem(A, b, c, ["C", "B"], variable_type=">=")
sage: P.base_ring()
Rational Field

sage: c = (10, 5.)
sage: P = InteractiveMILPProblem(A, b, c, ["C", "B"], variable_type=">=")
sage: P.base_ring()
Real Field with 53 bits of precision
c()

Return coefficients of the objective of self, i.e. \(c\).

OUTPUT: a vector

EXAMPLES:

sage: from sage_numerical_interactive_mip import *
sage: A = ([1, 1], [3, 1])
sage: b = (1000, 1500)
sage: c = (10, 5)
sage: P = InteractiveMILPProblem(A, b, c, ["C", "B"], variable_type=">=")
sage: P.objective_coefficients()
(10, 5)
sage: P.c()
(10, 5)
constant_terms()

Return constant terms of constraints of the relaxation of self, i.e. \(b\).

OUTPUT: a vector

EXAMPLES:

sage: from sage_numerical_interactive_mip import *
sage: A = ([1, 1], [3, 1])
sage: b = (1000, 1500)
sage: c = (10, 5)
sage: P = InteractiveMILPProblem(A, b, c, ["C", "B"], variable_type=">=")
sage: P.constant_terms()
(1000, 1500)
sage: P.b()
(1000, 1500)
constraint_coefficients()

Return coefficients of constraints of the relaxation of self, i.e. \(A\).

OUTPUT: a matrix

EXAMPLES:

sage: from sage_numerical_interactive_mip import *
sage: A = ([1, 1], [3, 1])
sage: b = (1000, 1500)
sage: c = (10, 5)
sage: P = InteractiveMILPProblem(A, b, c, ["C", "B"], variable_type=">=")
sage: P.constraint_coefficients()
[1 1]
[3 1]
sage: P.A()
[1 1]
[3 1]
constraint_types()

Return a tuple listing the constraint types of all rows.

OUTPUT: a tuple of strings

EXAMPLES:

sage: from sage_numerical_interactive_mip import *
sage: A = ([1, 1], [3, 1])
sage: b = (1000, 1500)
sage: c = (10, 5)
sage: P = InteractiveMILPProblem(A, b, c, ["C", "B"],
....:     variable_type=">=", constraint_type=["<=", "=="])
sage: P.constraint_types()
('<=', '==')
continuous_variables()

Return a set of continuous decision variables of self.

OUTPUT: a set of variables

EXAMPLES:

sage: from sage_numerical_interactive_mip import *
sage: A = ([1, 2, 1], [3, 1, 5])
sage: b = (1000, 1500)
sage: c = (10, 5, 7)
sage: P = InteractiveMILPProblem(A, b, c, integer_variables={'x1'})
sage: P.continuous_variables()
{x2, x3}
decision_variables()

Return decision variables of the relaxation of self, i.e. \(x\).

OUTPUT: a vector

EXAMPLES:

sage: from sage_numerical_interactive_mip import *
sage: A = ([1, 1], [3, 1])
sage: b = (1000, 1500)
sage: c = (10, 5)
sage: P = InteractiveMILPProblem(A, b, c, ["C", "B"], variable_type=">=")
sage: P.decision_variables()
(C, B)
sage: P.x()
(C, B)
feasible_set

File: /home/docs/checkouts/readthedocs.org/user_builds/sage-numerical-interactive-mip/checkouts/latest/sage_numerical_interactive_mip/interactive_milp_problem.py (starting at line 644)

Return the feasible set of the relaxation of self.

OUTPUT: a Polyhedron

EXAMPLES:

sage: from sage_numerical_interactive_mip import *
sage: A = ([1, 1], [3, 1])
sage: b = (1000, 1500)
sage: c = (10, 5)
sage: P = InteractiveMILPProblem(A, b, c, ["C", "B"], variable_type=">=")
sage: P.feasible_set()
A 2-dimensional polyhedron in QQ^2 defined as the convex hull of 4 vertices
sage: A = ([-1, 1], [8, 2])
sage: b = (2, 17)
sage: c = (55/10, 21/10)
sage: P = InteractiveMILPProblem(A, b, c, variable_type=">=",
....:                            integer_variables=True)
sage: P.relaxation().is_bounded()
True
sage: P.feasible_set()
((0, 0), (0, 1), (0, 2), (1, 0), (1, 1), (1, 2), (1, 3), (2, 0))
sage: P = InteractiveMILPProblem(A, b, c, variable_type=">=",
....:                            integer_variables={'x1'})
sage: P.feasible_set()
Traceback (most recent call last):
...
NotImplementedError: this method is not implemented
if therelaxation's feasible set is not bounded and
not all decision variables are integer
sage: b = (-1000, 1500)
sage: P = InteractiveMILPProblem(A, b, c, constraint_type=">=",
....:                            integer_variables=True)
sage: P.relaxation().is_bounded()
False
sage: P.feasible_set()
Traceback (most recent call last):
...
NotImplementedError: this method is not implemented
if therelaxation's feasible set is not bounded and
not all decision variables are integer
integer_variables()

Return the set of integer decision variables of self.

EXAMPLES:

sage: from sage_numerical_interactive_mip import *
sage: A = ([1, 1], [3, 1])
sage: b = (1/10, 15/10)
sage: c = (10, 5)
sage: P = InteractiveMILPProblem(A, b, c, integer_variables={'x1'})
sage: P.integer_variables()
{x1}
sage: P = InteractiveMILPProblem(A, b, c, integer_variables=True)
sage: P.integer_variables()
{x1, x2}
sage: P = InteractiveMILPProblem(A, b, c, integer_variables=False)
sage: P.integer_variables()
set()
is_bounded()

Check if``self`` is bounded.

is_feasible(*x)

Check if self or given solution is feasible.

INPUT:

  • (optional) anything that can be interpreted as a valid solution for the relaxation of this problem, i.e. a sequence of values for all decision variables

OUTPUT:

  • When *x is given, output is True if the relaxation of this problem or given solution is feasible and satisfies the integrality constraints , False otherwise. When *x is not given, raise NotImplementedError

EXAMPLES:

sage: from sage_numerical_interactive_mip import *
sage: A = ([-1, 1], [8, 2])
sage: b = (2, 17)
sage: c = (55/10, 21/10)
sage: P = InteractiveMILPProblem(A, b, c, integer_variables=True)
sage: P.is_feasible(1, 3)
True
sage: P.is_feasible(1, 2/3)
False
sage: P.is_feasible(1, 10/3)
False
sage: P.is_feasible()
Traceback (most recent call last):
...
NotImplementedError: this method is not implemented if a solution is not given
sage: P = InteractiveMILPProblem(A, b, c)
sage: P.is_feasible(1/2, 3/2)
True
sage: P = InteractiveMILPProblem(A, b, c, integer_variables={'x1'})
sage: P.is_feasible(1, 2/3)
True
sage: P.is_feasible(2/3, 1)
False
is_negative()

Return \(True\) when the relaxation problem is of type "-max" or "-min".

EXAMPLES:

sage: from sage_numerical_interactive_mip import *
sage: A = ([1, 1], [3, 1])
sage: b = (1000, 1500)
sage: c = (10, 5)
sage: P = InteractiveMILPProblem(A, b, c, ["C", "B"], variable_type=">=")
sage: P.is_negative()
False
sage: P = InteractiveMILPProblem(A, b, c, ["C", "B"],
....:     variable_type=">=", problem_type="-min")
sage: P.is_negative()
True
m()

Return the number of constraints of the relaxation of self, i.e. \(m\).

OUTPUT: an integer

EXAMPLES:

sage: from sage_numerical_interactive_mip import *
sage: A = ([1, 1], [3, 1])
sage: b = (1000, 1500)
sage: c = (10, 5)
sage: P = InteractiveMILPProblem(A, b, c, ["C", "B"], variable_type=">=")
sage: P.n_constraints()
2
sage: P.m()
2
n()

Return the number of decision variables of the relaxation of self, i.e. \(n\).

OUTPUT: an integer

EXAMPLES:

sage: from sage_numerical_interactive_mip import *
sage: A = ([1, 1], [3, 1])
sage: b = (1000, 1500)
sage: c = (10, 5)
sage: P = InteractiveMILPProblem(A, b, c, ["C", "B"], variable_type=">=")
sage: P.n_variables()
2
sage: P.n()
2
n_constraints()

Return the number of constraints of the relaxation of self, i.e. \(m\).

OUTPUT: an integer

EXAMPLES:

sage: from sage_numerical_interactive_mip import *
sage: A = ([1, 1], [3, 1])
sage: b = (1000, 1500)
sage: c = (10, 5)
sage: P = InteractiveMILPProblem(A, b, c, ["C", "B"], variable_type=">=")
sage: P.n_constraints()
2
sage: P.m()
2
n_variables()

Return the number of decision variables of the relaxation of self, i.e. \(n\).

OUTPUT: an integer

EXAMPLES:

sage: from sage_numerical_interactive_mip import *
sage: A = ([1, 1], [3, 1])
sage: b = (1000, 1500)
sage: c = (10, 5)
sage: P = InteractiveMILPProblem(A, b, c, ["C", "B"], variable_type=">=")
sage: P.n_variables()
2
sage: P.n()
2
objective_coefficients()

Return coefficients of the objective of self, i.e. \(c\).

OUTPUT: a vector

EXAMPLES:

sage: from sage_numerical_interactive_mip import *
sage: A = ([1, 1], [3, 1])
sage: b = (1000, 1500)
sage: c = (10, 5)
sage: P = InteractiveMILPProblem(A, b, c, ["C", "B"], variable_type=">=")
sage: P.objective_coefficients()
(10, 5)
sage: P.c()
(10, 5)
objective_constant_term()

Return the constant term of the objective of self.

OUTPUT: a number

EXAMPLES:

sage: from sage_numerical_interactive_mip import *
sage: A = ([1, 1], [3, 1])
sage: b = (1000, 1500)
sage: c = (10, 5)
sage: P = InteractiveMILPProblem(A, b, c, ["C", "B"], variable_type=">=")
sage: P.objective_constant_term()
0
sage: P.relaxation().optimal_value()
6250
sage: P = InteractiveMILPProblem(A, b, c, ["C", "B"],
....:       variable_type=">=", objective_constant_term=-1250)
sage: P.objective_constant_term()
-1250
sage: P.relaxation().optimal_value()
5000
objective_value(*x)

Return the value of the objective on the given solution of the relaxation of self.

INPUT:

  • anything that can be interpreted as a valid solution for the relaxation this problem, i.e. a sequence of values for all decision variables

OUTPUT:

EXAMPLES:

sage: from sage_numerical_interactive_mip import *
sage: A = ([1, 1], [3, 1])
sage: b = (1000, 1500)
sage: c = (10, 5)
sage: P = InteractiveMILPProblem(A, b, c, variable_type=">=")
sage: P.objective_value(100, 200)
2000
plot(*args, **kwds)

Return a plot for solving self graphically.

INPUT:

  • xmin, xmax, ymin, ymax – bounds for the axes, if not given, an attempt will be made to pick reasonable values

  • alpha – (default: 0.2) determines how opaque are shadows

OUTPUT: a plot

Note

This only works for problems with two decision variables. On the plot the black arrow indicates the direction of growth of the objective. The lines perpendicular to it are level curves of the objective. If there are optimal solutions, the arrow originates in one of them and the corresponding level curve is solid: all points of the feasible set on it are optimal solutions. Otherwise the arrow is placed in the center. If the problem is infeasible or the objective is zero, a plot of the feasible set only is returned.

EXAMPLES:

sage: from sage_numerical_interactive_mip import *
sage: A = ([1, 1], [3, 1])
sage: b = (100, 150)
sage: c = (10, 5)
sage: P = InteractiveMILPProblem(A, b, c,
....:     variable_type=">=", integer_variables={'x1'})
sage: p = P.plot()
sage: p.show()

In this case the plot works better with the following axes ranges:

sage: p = P.plot(0, 1000, 0, 1500)
sage: p.show()

TESTS:

We check that zero objective can be dealt with:

sage: InteractiveMILPProblem(A, b, (0, 0),
....: variable_type=">=", integer_variables={'x1'}).plot()
Graphics object consisting of 57 graphics primitives
plot_feasible_set(xmin=None, xmax=None, ymin=None, ymax=None, alpha=0.2, number_of_cuts=0)

Return a plot of the feasible set of self.

INPUT:

  • xmin, xmax, ymin, ymax – bounds for the axes, if not given, an attempt will be made to pick reasonable values

  • alpha – (default: 0.2) determines how opaque are shadows

OUTPUT: a plot

Note

This only works for a problem with two decision variables. The plot shows boundaries of constraints with a shadow on one side for inequalities. If the feasible_set() is not empty and at least part of it is in the given boundaries, it will be shaded gray and \(F\) will be placed in its middle.

EXAMPLES:

sage: from sage_numerical_interactive_mip import *
sage: A = ([1, 1], [3, 1])
sage: b = (1000, 1500)
sage: c = (10, 5)
sage: P = InteractiveLPProblem(A, b, c, ["C", "B"], variable_type=">=")
sage: P1 = InteractiveMILPProblem.with_relaxation(P, True)
sage: p = P1.plot_feasible_set()                                            # known bug (segfault)
sage: p.show()                                                              # known bug

In this case the plot works better with the following axes ranges:

sage: p = P1.plot_feasible_set(0, 1000, 0, 1500)                            # known bug
sage: p.show()                                                              # known bug
plot_lines(F, integer_variable)

Return the plot of lines (either vertical or horizontal) on an interval.

INPUT:

  • F – the feasible set of self

  • integer_variable – a string of name of a basic integer variable indicating to plot vertical lines or horizontal lines

OUTPUT: a plot

plot_objective_growth_and_solution(FP, c, xmin=None, xmax=None, ymin=None, ymax=None)

Return a plot with the growth of the objective function and the objective solution of the relaxation of self.

Note

For more information, refer to the docstrings of plot() in InteractiveLPProblem.

INPUT:

  • FP – the plot of the feasbiel set of self

  • c – the objective value of self

  • xmin, xmax, ymin, ymax – bounds for the axes, if not given, an attempt will be made to pick reasonable values

OUTPUT: a plot

plot_relaxation(*args, **kwds)

Return a plot for solving the relaxation of self graphically.

INPUT:

  • xmin, xmax, ymin, ymax – bounds for the axes, if not given, an attempt will be made to pick reasonable values

  • alpha – (default: 0.2) determines how opaque are shadows

OUTPUT: a plot

This only works for problems with two decision variables. On the plot the black arrow indicates the direction of growth of the objective. The lines perpendicular to it are level curves of the objective. If there are optimal solutions, the arrow originates in one of them and the corresponding level curve is solid: all points of the feasible set on it are optimal solutions. Otherwise the arrow is placed in the center. If the problem is infeasible or the objective is zero, a plot of the feasible set only is returned.

EXAMPLES:

sage: from sage_numerical_interactive_mip import *
sage: A = ([1, 1], [3, 1])
sage: b = (1000, 1500)
sage: c = (10, 5)
sage: P = InteractiveMILPProblem(A, b, c, ["C", "B"], variable_type=">=")
sage: p = P.plot_relaxation()
sage: p.show()

In this case the plot works better with the following axes ranges:

sage: p = P.plot_relaxation(0, 1000, 0, 1500)
sage: p.show()

TESTS:

We check that zero objective can be dealt with:

sage: InteractiveMILPProblem(A, b, (0, 0), ["C", "B"],
....: variable_type=">=").plot_relaxation()
Graphics object consisting of 8 graphics primitives
plot_variables(F, x, box, colors, pad, alpha)

Return a plot of the decision variables of self

INPUT:

  • F – the feasible set of self

  • x – the decision variables of self

  • colors – gives a list of color

  • pad – a number determined by xmin, xmax, ymin, ymax in :meth::\(plot\)

  • alpha – determines how opaque are shadows

OUTPUT: a plot

problem_type()

Return the problem type of the relaxation of self.

Needs to be used together with is_negative.

OUTPUT: a string, one of "max", "min".

EXAMPLES:

sage: from sage_numerical_interactive_mip import *
sage: A = ([1, 1], [3, 1])
sage: b = (1000, 1500)
sage: c = (10, 5)
sage: P = InteractiveMILPProblem(A, b, c, ["C", "B"], variable_type=">=")
sage: P.problem_type()
'max'
sage: P = InteractiveMILPProblem(A, b, c, ["C", "B"],
....:     variable_type=">=", problem_type="-min")
sage: P.problem_type()
'min'
relaxation()

Return the relaxation problem of self

OUTPUT:

  • an LP problem

EXAMPLES:

sage: from sage_numerical_interactive_mip import *
sage: A = ([1, 1], [3, 1])
sage: b = (1000, 1500)
sage: c = (10, 5)
sage: P = InteractiveMILPProblem(A, b, c)
sage: R = InteractiveLPProblem(A, b, c)
sage: P.relaxation() == R
True
standard_form(transformation=False, **kwds)

Construct the MILP problem in standard form equivalent to self.

INPUT:

  • transformation – (default: False) if True, a map converting solutions of the problem in standard form to the original one will be returned as well

  • you can pass (as keywords only) slack_variables, objective_name to the constructor of InteractiveMILPProblemStandardForm

OUTPUT:

EXAMPLES:

sage: from sage_numerical_interactive_mip import *
sage: A = ([1, 1], [3, 1])
sage: b = (1000, 1500)
sage: c = (10, 5)
sage: P = InteractiveMILPProblem(A, b, c, variable_type=["<=", ""],
....:                            objective_constant_term=42,
....:                            integer_variables=True)
sage: PSF, f = P.standard_form(True)
sage: f
Vector space morphism represented by the matrix:
[-1  0]
[ 0  1]
[ 0 -1]
Domain: Vector space of dimension 3 over Rational Field
Codomain: Vector space of dimension 2 over Rational Field
sage: PSF.relaxation().optimal_solution()
(0, 1000, 0)
sage: P.relaxation().optimal_solution()
(0, 1000)
sage: P.relaxation().is_optimal(PSF.relaxation().optimal_solution())
Traceback (most recent call last):
...
TypeError: given input is not a solution for this problem
sage: P.relaxation().is_optimal(f(PSF.relaxation().optimal_solution()))
True
sage: PSF.relaxation().optimal_value()
5042
sage: P.relaxation().optimal_value()
5042
sage: P.integer_variables()
{x1, x2}
sage: PSF.integer_variables()
{x1_n, x2_p, x2_n, x4, x5}

TESTS:

Above also works for the equivalent minimization problem:

sage: c = (-10, -5)
sage: P = InteractiveMILPProblem(A, b, c, variable_type=["<=", ""],
....:                            objective_constant_term=-42,
....:                            problem_type="min",
....:                            integer_variables=True)
sage: PSF, f = P.standard_form(True)
sage: PSF.relaxation().optimal_solution()
(0, 1000, 0)
sage: P.relaxation().optimal_solution()
(0, 1000)
sage: PSF.relaxation().optimal_value()
-5042
sage: P.relaxation().optimal_value()
-5042

Integer variables are passed to standard form problem:

sage: A = ([1, 1, 5/2], [2, 3/4, 4], [3/5, 1, 6])
sage: b = (1000, 1500, 2000)
sage: c = (10, 5, 3)
sage: P = InteractiveMILPProblem(A, b, c, variable_type=[">=", "<=", ""],
....:                            integer_variables=True)
sage: PSF, f = P.standard_form(True)
sage: P.integer_variables()
{x1, x2, x3}
sage: PSF.integer_variables()
{x1, x2_n, x3_p, x3_n}
variable_types()

Return a tuple listing the variable types of all decision variables of the relaxation of self.

OUTPUT: a tuple of strings

EXAMPLES:

sage: from sage_numerical_interactive_mip import *
sage: A = ([1, 1], [3, 1])
sage: b = (1000, 1500)
sage: c = (10, 5)
sage: P = InteractiveMILPProblem(A, b, c, ["C", "B"], variable_type=[">=", ""])
sage: P.variable_types()
('>=', '')
classmethod with_relaxation(relaxation, integer_variables=False)

Construct a MILP problem by a relaxation and a set of integer variables.

INPUT:

  • relaxation – LP problem

  • integer_variables – (default: False) either a boolean value indicating if all the problem variables are integer or not, or a set of strings giving some problem variables’ names, where those problem variables are integer

OUTPUT: an MILP problem

EXAMPLES:

sage: from sage_numerical_interactive_mip import *
sage: A = ([1, 1, 2], [3, 1, 7], [6, 4, 5])
sage: b = (1000, 1500, 2000)
sage: c = (10, 5, 1)
sage: P = InteractiveLPProblem(A, b, c, variable_type=">=")
sage: P1 = InteractiveMILPProblem.with_relaxation(P, True)
sage: P1
MILP problem (use ... details)
sage: P == P1.relaxation()
True
x()

Return decision variables of the relaxation of self, i.e. \(x\).

OUTPUT: a vector

EXAMPLES:

sage: from sage_numerical_interactive_mip import *
sage: A = ([1, 1], [3, 1])
sage: b = (1000, 1500)
sage: c = (10, 5)
sage: P = InteractiveMILPProblem(A, b, c, ["C", "B"], variable_type=">=")
sage: P.decision_variables()
(C, B)
sage: P.x()
(C, B)
class sage_numerical_interactive_mip.interactive_milp_problem.InteractiveMILPProblemStandardForm(A=None, b=None, c=None, x='x', problem_type='max', slack_variables=None, base_ring=None, is_primal=True, objective_name=None, objective_constant_term=0, relaxation=None, integer_variables=False)

Bases: InteractiveMILPProblem

Construct an MILP (Mixed Integer Linear Programming) problem in standard form.

The used standard form is:

\[\begin{split}\begin{array}{l} \pm \max cx \\ Ax \leq b \\ x \geq 0 \\ \text{some components of $x$ restricted to integer values} \end{array}\end{split}\]

INPUT:

  • A – a matrix of constraint coefficients

  • b – a vector of constraint constant terms

  • c – a vector of objective coefficients

  • x – (default: "x") a vector of decision variables or a string the base name giving

  • problem_type – (default: "max") a string specifying the problem type: either "max" or "-max"

  • slack_variables – (default: depending on style()) a vector of slack variables or a string giving the base name

  • base_ring – (default: the fraction field of a common ring for all input coefficients) a field to which all input coefficients will be converted

  • is_primal – (default: True) whether this problem is primal or dual: each problem is of course dual to its own dual, this flag is mostly for internal use and affects default variable names only

  • objective_name – a string or a symbolic expression for the objective used in dictionaries, default depending on style()

  • objective_constant_term – (default: 0) a constant term of the objective

  • relaxation – (default: None) an LP problem in standard form as the relaxation of the problem

  • integer_variables – (default: False) either a boolean value indicating if all the problem variables are integer or not, or a set of strings giving some problem variables’ names, where those problem variables are integer

EXAMPLES:

We will construct the following problem directly:

sage: from sage_numerical_interactive_mip import *
sage: A = ([1, 1], [3, 1])
sage: b = (1000, 1500)
sage: c = (10, 5)
sage: P = InteractiveMILPProblemStandardForm(A, b, c, integer_variables=True)

Unlike InteractiveMILPProblem, this class does not allow you to adjust types of constraints (they are always "<=") and variables (they are always ">="), and the problem type may only be "max" or "-max". You may give custom names to slack variables, but in most cases defaults should work:

sage: P.decision_variables()
(x1, x2)
sage: P.slack_variables()
(x3, x4)

We will construct the same problem by calling with_relaxation() in InteractiveMILPProblemStandardForm:

sage: R = InteractiveLPProblemStandardForm(A, b, c)
sage: P = InteractiveMILPProblem.with_relaxation(R, True)

See with_relaxation() in InteractiveMILPProblemStandardForm for more documentation.

__init__(A=None, b=None, c=None, x='x', problem_type='max', slack_variables=None, base_ring=None, is_primal=True, objective_name=None, objective_constant_term=0, relaxation=None, integer_variables=False)

See InteractiveMILPProblemStandardForm for documentation.

TESTS:

sage: from sage_numerical_interactive_mip import *
sage: A = ([1, 1], [3, 1])
sage: b = (1000, 1500)
sage: c = (10, 5)
sage: P = InteractiveMILPProblemStandardForm(A, b, c,
....:     integer_variables=True)
sage: TestSuite(P).run()
_make_Gomory_fractional_cut(dictionary, choose_variable, index)

Return the coefficients and constant for a Gomory fractional cut

INPUT:

  • dictionary – a dictionary

  • choose_variable – the basic variable for the chosen cut

  • index – an integer indicating the choose_variable’s index in constant_terms()

OUTPUT:

  • cut_coefficients – a list of coefficients for the cut

  • cut_constant – the constant for the cut

EXAMPLES:

sage: from sage_numerical_interactive_mip import InteractiveMILPProblemStandardForm
sage: A = ([-1, 1], [8, 2])
sage: b = (2, 17)
sage: c = (55/10, 21/10)
sage: P = InteractiveMILPProblemStandardForm(A, b, c,
....: integer_variables=True)
sage: D = P.final_dictionary()
sage: v = D.basic_variables()[0]
sage: P._make_Gomory_fractional_cut(D, v, 0)
([-1/10, -4/5], -3/10)
_make_Gomory_mixed_integer_cut(dictionary, choose_variable, index)

Return the coefficients and constant a Gomory fractional cut

INPUT:

  • dictionary – a dictionary

  • choose_variable – the basic variable of the chosen cut

  • index – an integer indicating the choose_variable’s index in constant_terms()

OUTPUT:

  • cut_coefficients – a list of coefficients for the cut

  • cut_constant – the constant for the cut

EXAMPLES:

sage: from sage_numerical_interactive_mip import *
sage: A = ([-1, 1], [8, 2])
sage: b = (2, 17)
sage: c = (55/10, 21/10)
sage: P = InteractiveMILPProblemStandardForm(A, b, c,
....: integer_variables=True)
sage: D = P.final_dictionary()
sage: v = D.basic_variables()[0]
sage: P._make_Gomory_mixed_integer_cut(D, v, 0)
([-1/3, -2/7], -1)
add_a_cut(dictionary, integer_variables, separator=None, basic_variable=None, slack_variable=None)

Return the dictionary and the set of integer variables by adding a cut.

INPUT:

  • dictionary – a dictionary or a revised dictionary

  • integer_variables – a set of integer variables for the dictionary

  • separator– (default: None) a string indicating the cut generating function separator

  • basic_variable – (default: None) a string specifying the basic variable that will provide the source row for the cut

  • slack_variable – (default: None) a string giving the name of the slack_variable. If the argument is none, the new slack variable will be named as \(x_n\) where n is the next index of variable list.

OUTPUT:

  • a dictionary or a revised dictionary

  • a set of integer variables

EXAMPLES:

sage: from sage_numerical_interactive_mip import *
sage: A = ([-1, 1], [8, 2])
sage: b = (2, 17)
sage: c = (55/10, 21/10)
sage: P = InteractiveMILPProblemStandardForm(A, b, c,
....: integer_variables=True)
sage: D = P.final_dictionary()
sage: D1, I1 = P.add_a_cut(D, P.integer_variables(),
....: separator="gomory_fractional")
sage: D1.leave(D1.basic_variables()[-1])
sage: D1.leaving_coefficients()
(-1/10, -4/5)
sage: D1.constant_terms()
(33/10, 13/10, -3/10)

The new slack variable is integer if we use Gomory fractional cut:

sage: P.integer_variables()
{x1, x2, x3, x4}
sage: I1
{x1, x2, x3, x4, x5}

The new slack variable is continuous if we use Gomory mixed integer cut:

sage: D2, I2 = P.add_a_cut(D, P.integer_variables(),
....: separator="gomory_mixed_integer")
sage: I2
{x1, x2, x3, x4}

Some cases of add_a_cut() refusing making a cut by using Gomory fractional cut:

  1. the basic variable of the source row is not an integer:

    sage: b = (2/10, 17)
sage: P = InteractiveMILPProblemStandardForm(A, b, c,
....:  integer_variables=True)
sage: P.integer_variables()
{x1, x2, x4}
sage: P.add_a_cut(P.final_dictionary(), P.integer_variables(),
....: basic_variable="x3", separator="gomory_fractional")
Traceback (most recent call last):
...
ValueError: chosen variable should be an integer variable

  2. a non-integer variable is among the nonbasic variables with non-zero coefficients on the source row:

    sage: A = ([1, 3, 5], [2, 6, 9], [6, 8, 3])
sage: b = (12/10, 23/10, 31/10)
sage: c = (3, 5, 7)
sage: P = InteractiveMILPProblemStandardForm(A, b, c,
....: integer_variables= {'x1', 'x3'})
sage: D = P.final_dictionary()
sage: D.nonbasic_variables()
(x6, x2, x4)
sage: D.row_coefficients("x3")
(-1/27, 10/27, 2/9)

    If the user chooses \(x_3\) to provide the source row, add_a_cut() will give an error, because the non-integer variable \(x_6\) has a non-zero coefficient \(1/27\) on the source row:

    sage: P.add_a_cut(P.final_dictionary(), P.integer_variables(),
....: basic_variable='x3', separator="gomory_fractional")
Traceback (most recent call last):
...
ValueError: this is not an eligible source row

    In fact, we cannot add a Gomory fractional cut to this dictionary, because the non-integer variable \(x_6\) has non-zero coefficient on each row:

    sage: D.enter(6)
sage: D.entering_coefficients()
(-1/27, -1/27, 5/27)
sage: P.add_a_cut(P.final_dictionary(), P.integer_variables(),
....: separator="gomory_fractional")
Traceback (most recent call last):
...
ValueError: there does not exist an eligible source row

    However, the previous restrictions are not held for Gomory mixed integer cuts:

    sage: D2, I2 = P.add_a_cut(P.final_dictionary(), P.integer_variables(),
....: separator="gomory_mixed_integer")
sage: D2.basic_variables()
(x3, x5, x1, x7)
add_constraint(coefficients, constant_term, slack_variable=None, integer_slack=False)

Return a new MILP problem by adding a constraint to``self``.

INPUT:

  • coefficients – coefficients of the new constraint

  • constant_term – a constant term of the new constraint

  • slack_variable – (default: depends on style()) a vector of the slack variable or a string giving the name

  • integer_slack– (default: False) a boolean value indicating if the new slack variable is integer or not.

OUTPUT: an MILP problem in standard form

EXAMPLES:

sage: from sage_numerical_interactive_mip import *
sage: A = ([1, 1], [3, 1])
sage: b = (1000, 1500)
sage: c = (10, 5)
sage: P = InteractiveMILPProblemStandardForm(A, b, c)
sage: P1 = P.add_constraint(([2, 4]), 2000)
sage: P1.Abcx()
(
[1 1]
[3 1]
[2 4], (1000, 1500, 2000), (10, 5), (x1, x2)
)
sage: P1.slack_variables()
(x3, x4, x5)
sage: P.Abcx()
(
[1 1]
[3 1], (1000, 1500), (10, 5), (x1, x2)
)
sage: P.slack_variables()
(x3, x4)
sage: P = InteractiveMILPProblemStandardForm(A, b, c)
sage: P2 = P.add_constraint(([2, 4]), 2000, slack_variable='c')
sage: P2.slack_variables()
(x3, x4, c)
sage: P3 = P.add_constraint(([2, 4, 6]), 2000)
Traceback (most recent call last):
...
TypeError: number of columns must be the same, not 2 and 3
all_variables()

Return a set of both decision variables and slack variables of self.

OUTPUT: a set of variables

EXAMPLES:

sage: from sage_numerical_interactive_mip import *
sage: A = ([1, 2, 1], [3, 1, 5])
sage: b = (1000, 1500)
sage: c = (10, 5, 7)
sage: P = InteractiveMILPProblemStandardForm(A, b, c)
sage: P.all_variables()
{x1, x2, x3, x4, x5}
coordinate_ring()

Return the coordinate ring of the relaxation of self.

OUTPUT:

  • a polynomial ring over the base_ring() of self in the auxiliary_variable(), decision_variables(), and slack_variables() with “neglex” order

EXAMPLES:

sage: from sage_numerical_interactive_mip import *
sage: A = ([1, 1], [3, 1], [-1, -1])
sage: b = (1000, 1500, -400)
sage: c = (10, 5)
sage: P = InteractiveMILPProblemStandardForm(A, b, c)
sage: P.coordinate_ring()
Multivariate Polynomial Ring in x0, x1, x2, x3, x4, x5
over Rational Field
sage: P.base_ring()
Rational Field
sage: P.decision_variables()
(x1, x2)
sage: P.slack_variables()
(x3, x4, x5)
dictionary(*x_B)

Construct a dictionary for the relaxation of self with given basic variables.

INPUT:

  • basic variables for the dictionary to be constructed

OUTPUT: a dictionary

Note

This is a synonym for self.revised_dictionary(x_B).dictionary(), but basic variables are mandatory.

EXAMPLES:

sage: from sage_numerical_interactive_mip import *
sage: A = ([1, 1], [3, 1])
sage: b = (1000, 1500)
sage: c = (10, 5)
sage: P = InteractiveMILPProblemStandardForm(A, b, c)
sage: D = P.dictionary("x1", "x2")
sage: D.basic_variables()
(x1, x2)
final_dictionary()

Return the final dictionary of the simplex method applied to the relaxation of self.

See run_simplex_method() for the description of possibilities.

OUTPUT: a dictionary

EXAMPLES:

sage: from sage_numerical_interactive_mip import *
sage: A = ([1, 1], [3, 1])
sage: b = (1000, 1500)
sage: c = (10, 5)
sage: P = InteractiveMILPProblemStandardForm(A, b, c)
sage: D = P.final_dictionary()
sage: D.is_optimal()
True

TESTS:

sage: P.final_dictionary() is P.final_dictionary()
False
final_revised_dictionary()

Return the final dictionary of the revised simplex method applied to the relaxation of self.

See run_revised_simplex_method() for the description of possibilities.

OUTPUT: a revised dictionary

EXAMPLES:

sage: from sage_numerical_interactive_mip import *
sage: A = ([1, 1], [3, 1])
sage: b = (1000, 1500)
sage: c = (10, 5)
sage: P = InteractiveMILPProblemStandardForm(A, b, c)
sage: D = P.final_revised_dictionary()
sage: D.is_optimal()
True

TESTS:

sage: P.final_revised_dictionary() is P.final_revised_dictionary()
False
initial_dictionary()

Return the initial dictionary of the relaxation of self.

The initial dictionary “defines” slack_variables() in terms of the decision_variables(), i.e. it has slack variables as basic ones.

OUTPUT:

  • a dictionary

EXAMPLES:

sage: from sage_numerical_interactive_mip import *
sage: A = ([1, 1], [3, 1])
sage: b = (1000, 1500)
sage: c = (10, 5)
sage: P = InteractiveMILPProblemStandardForm(A, b, c)
sage: D = P.initial_dictionary()
inject_variables(scope=None, verbose=True)

Inject variables of self into scope.

INPUT:

  • scope – namespace (default: global)

  • verbose – if True (default), names of injected variables will be printed

EXAMPLES:

sage: from sage_numerical_interactive_mip import *
sage: A = ([1, 1], [3, 1])
sage: b = (1000, 1500)
sage: c = (10, 5)
sage: P = InteractiveMILPProblemStandardForm(A, b, c)
sage: P.inject_variables()
Defining x0, x1, x2, x3, x4
sage: 3*x1 + x2
x2 + 3*x1
integer_variables()

Return the set of integer decision variables of self.

EXAMPLES:

sage: from sage_numerical_interactive_mip import *
sage: A = ([1, 1], [3, 1])
sage: b = (1/10, 15/10)
sage: c = (10, 5)
sage: P = InteractiveMILPProblemStandardForm(A, b, c,
....: integer_variables={'x1'})
sage: P.integer_variables()
{x1}
sage: P = InteractiveMILPProblemStandardForm(A, b, c,
....: integer_variables=True)
sage: P.integer_variables()
{x1, x2}
sage: P = InteractiveMILPProblemStandardForm(A, b, c,
....: integer_variables=False)
sage: P.integer_variables()
set()

Unlike integer_variables() in InteractiveMILPProblem which only knows about the integrality of the decision variables given by the user, integer_variables() in InteractiveMILPProblemStandardForm uses sufficient conditions to determine the integrality of decision variables, i.e. for any row, a decision variable \(x\) is an integer, if the following conditions hold: the slack variable of that row is set by user to be integer; the constant is integer; any decision variables except x has has a coefficient 0; and the coefficient of x is integer:

sage: A1 = ([1, 1, 4], [3, 1, 5], [0, 0, 1])
sage: b1 = (1/10, 15/10, 5)
sage: c1 = (10, 5, 12)
sage: P = InteractiveMILPProblemStandardForm(A1, b1, c1,
....: integer_variables={'x6'})
sage: P.integer_variables()
{x3, x6}

Since InteractiveMILPProblemStandardForm knows about slack variables, we may use the sufficient conditions to know the integrality of slack variables, i.e. the slack variable of a row is an integer if the following conditions hold: all decision variables are integer; the constant of the row is integer; and all coefficients of that row are integer:

sage: A = ([1, 1], [3, 1])
sage: b = (11, 15)
sage: c = (10, 5)
sage: P = InteractiveMILPProblemStandardForm(A, b, c)
sage: P.integer_variables()
set()
sage: P = InteractiveMILPProblemStandardForm(A, b, c,
....: integer_variables=True)
sage: P.integer_variables()
{x1, x2, x3, x4}
sage: b2 = (11/10, 5)
sage: P = InteractiveMILPProblemStandardForm(A, b2, c,
....: integer_variables=True)
sage: P.integer_variables()
{x1, x2, x4}
sage: A2 = ([1, 1], [3/10, 1])
sage: P = InteractiveMILPProblemStandardForm(A2, b2, c,
....: integer_variables=True)
sage: P.integer_variables()
{x1, x2}

Also, InteractiveMILPProblemStandardForm allows the user to choose some slack variables to be integer, which may violate the sufficient conditions:

sage: P = InteractiveMILPProblemStandardForm(A2, b2, c,
....: integer_variables={'x1', 'x2', 'x3'})
sage: P.integer_variables()
{x1, x2, x3}
objective_name()

Return the objective name used in dictionaries for this problem.

OUTPUT: a symbolic expression

EXAMPLES:

sage: from sage_numerical_interactive_mip import *
sage: A = ([1, 1], [3, 1], [-1, -1])
sage: b = (1000, 1500, -400)
sage: c = (10, 5)
sage: P = InteractiveMILPProblemStandardForm(A, b, c)
sage: P.objective_name()
z
sage: style("Vanderbei")
'Vanderbei'
sage: P = InteractiveMILPProblemStandardForm(A, b, c)
sage: P.objective_name()
zeta
sage: style("UAlberta")
'UAlberta'
sage: P = InteractiveMILPProblemStandardForm(A, b, c, objective_name="custom")
sage: P.objective_name()
custom
pick_eligible_source_row(dictionary, integer_variables, separator=None, basic_variable=None)

Pick an eligible source row for self.

INPUT:

  • dictionary – a dictionary

  • integer_variables – the set of integer variables

  • separator – (default: None) a string indicating the cut generating function separator

  • basic_variable – (default: None) a string specifying the basic variable that will provide the source row for the cut

OUTPUT:

  • choose_variable – the basic variable for the chosen cut

  • index – an integer indicating the choose_variable’s index in constant_terms()

EXAMPLES:

sage: from sage_numerical_interactive_mip import *
sage: A = ([-1, 1], [8, 2])
sage: b = (2, 17)
sage: c = (55/10, 21/10)
sage: P = InteractiveMILPProblemStandardForm(A, b, c,
....: integer_variables=True)
sage: D = P.final_dictionary()
sage: D.basic_variables()
(x2, x1)
sage: P.integer_variables()
{x1, x2, x3, x4}
sage: D.constant_terms()
(33/10, 13/10)

None of the variables are continuous, and the constant term of \(x_2\) is not an integer. Therefore, the row for x2 is an eligible source row:

sage: P.pick_eligible_source_row(D, P.integer_variables(),
....: separator="gomory_fractional")
(x2, 0)

See add_a_cut() for examples of ineligible source rows

relaxation()

Return the relaxation problem of self

OUTPUT: an LP problem in standard form

EXAMPLES:

sage: from sage_numerical_interactive_mip import *
sage: A = ([1, 1], [3, 1])
sage: b = (1000, 1500)
sage: c = (10, 5)
sage: P = InteractiveMILPProblemStandardForm(A, b, c)
sage: R = InteractiveLPProblemStandardForm(A, b, c)
sage: P.relaxation() == R
True
revised_dictionary(*x_B)

Construct a revised dictionary for the relaxation of self.

INPUT:

  • basic variables for the dictionary to be constructed; if not given, slack_variables() will be used

OUTPUT: a revised dictionary

EXAMPLES:

sage: from sage_numerical_interactive_mip import *
sage: A = ([1, 1], [3, 1])
sage: b = (1000, 1500)
sage: c = (10, 5)
sage: P = InteractiveMILPProblemStandardForm(A, b, c)
sage: D = P.revised_dictionary("x1", "x2")
sage: D.basic_variables()
(x1, x2)

If basic variables are not given the initial dictionary is constructed:

sage: P.revised_dictionary().basic_variables()
(x3, x4)
sage: P.initial_dictionary().basic_variables()
(x3, x4)
run_cutting_plane_method(separator=None, revised=False, plot=False, show_steps=False, *args, **kwds)

Perform the cutting plane method to solve a MILP problem. Return the number of cuts needed to solve the problem and the final dictionary.

INPUT:

  • separator – (default: None) a string indicating the cut generating function separator

  • revised – (default: False) a flag indicating using normal dictionary or revised dictionary to run the cutting plane method.

  • plot – (default:False) a boolean value to decide whether to plot the final problem or not when using revised dictionary

  • show_steps – (default:False) a boolean value to decide whether to return each step of the cutting plane method or not. When show_steps is True, plot each new problem when using revised dictionary

  • xmin, xmax, ymin, ymax – bounds for the axes, if not given, an attempt will be made to pick reasonable values

  • alpha – (default: 0.2) determines how opaque are shadows

OUTPUT:

  • a number which is the total number of cuts needed to solve a ILP problem

  • a dictionary or a revised dictionary depending on the revised

  • HtmlFragment with HTML/\(\LaTeX\) code of all encountered dictionaries if show_steps is True

EXAMPLES:

sage: from sage_numerical_interactive_mip import *
sage: A = ([-1, 1], [8, 2])
sage: b = (2, 17)
sage: c = (55/10, 21/10)
sage: P = InteractiveMILPProblemStandardForm(A, b, c,
....: integer_variables=True)
sage: n, D, output = P.run_cutting_plane_method(separator="gomory_fractional",
....: revised=True, plot=True, show_steps=True, xmin=-2, xmax=6, ymin=0, ymax=12)
sage: n
5
sage: type(D)
<class 'sage_numerical_interactive_mip._vendor.interactive_simplex_method.LPRevisedDictionary'>
sage: output
The original problem is:
\begin{equation*}
...
\end{equation*}
We solve the linear relaxation with the simplex methodobtaining the following final dictionary:
\begin{equation*}
...
\end{equation*}
After adding cut 1
...
\begin{equation*}
...
\end{equation*}
Run the dual simplex to restore primal feasibility.
The dictionary becomes:
\begin{equation*}
...
\end{equation*}
Now we have integer variables: $x_{1}, x_{2}, x_{3}, x_{4}, x_{5}$
Since some integer variables don't have integer solutions, we need to make another cut.
...
\begin{equation*}
...
\end{equation*}
Run the dual simplex to restore primal feasibility.
The dictionary becomes:
\begin{equation*}
...
\end{equation*}
The dictionary now is feasible and optimal, as well as integer feasibility.
The optimal value: $\frac{59}{5}$. An optimal solution: $\left(1,\,3\right)$.

sage: from sage_numerical_interactive_mip.interactive_milp_problem import _form_thin_long_triangle
sage: A1, b1 = _form_thin_long_triangle(4)
sage: c1 = (-1/27, 1/31)
sage: P1 = InteractiveMILPProblemStandardForm(A1, b1, c1,
....: integer_variables=True)
sage: n, D = P1.run_cutting_plane_method(
....: separator="gomory_fractional")
sage: n
9
sage: type(D)
<class 'sage_numerical_interactive_mip._vendor.interactive_simplex_method.LPDictionary'>
run_revised_simplex_method()

Apply the revised simplex method on the relaxation of self and return all steps.

OUTPUT:

  • HtmlFragment with HTML/\(\LaTeX\) code of all encountered dictionaries

Note

You can access the final_revised_dictionary(), which can be one of the following:

  • an optimal dictionary with the auxiliary_variable() among basic_variables() and a non-zero optimal value indicating that self is infeasible;

  • a non-optimal dictionary that has marked entering variable for which there is no choice of the leaving variable, indicating that self is unbounded;

  • an optimal dictionary.

EXAMPLES:

sage: from sage_numerical_interactive_mip import *
sage: A = ([1, 1], [3, 1], [-1, -1])
sage: b = (1000, 1500, -400)
sage: c = (10, 5)
sage: P = InteractiveMILPProblemStandardForm(A, b, c)
sage: P.run_revised_simplex_method()
\begin{equation*}
...
\end{equation*}
Entering: $x_{1}$. Leaving: $x_{0}$.
\begin{equation*}
...
\end{equation*}
Entering: $x_{5}$. Leaving: $x_{4}$.
\begin{equation*}
...
\end{equation*}
Entering: $x_{2}$. Leaving: $x_{3}$.
\begin{equation*}
...
\end{equation*}
The optimal value: $6250$. An optimal solution: $\left(250,\,750\right)$.
run_simplex_method()

Apply the simplex method on the relaxation of self and return all steps and intermediate states.

OUTPUT:

  • HtmlFragment with HTML/\(\LaTeX\) code of all encountered dictionaries

Note

You can access the final_dictionary(), which can be one of the following:

  • an optimal dictionary for the auxiliary_problem() with a non-zero optimal value indicating that self is infeasible;

  • a non-optimal dictionary for self that has marked entering variable for which there is no choice of the leaving variable, indicating that self is unbounded;

  • an optimal dictionary for self.

EXAMPLES:

sage: from sage_numerical_interactive_mip import *
sage: A = ([1, 1], [3, 1], [-1, -1])
sage: b = (1000, 1500, -400)
sage: c = (10, 5)
sage: P = InteractiveMILPProblemStandardForm(A, b, c)
sage: P.run_simplex_method()
\begin{equation*}
...
\end{equation*}
The initial dictionary is infeasible, solving auxiliary problem.
...
Entering: $x_{0}$. Leaving: $x_{5}$.
...
Entering: $x_{1}$. Leaving: $x_{0}$.
...
Back to the original problem.
...
Entering: $x_{5}$. Leaving: $x_{4}$.
...
Entering: $x_{2}$. Leaving: $x_{3}$.
...
The optimal value: $6250$. An optimal solution: $\left(250,\,750\right)$.
slack_variables()

Return slack variables of self.

Slack variables are differences between the constant terms and left hand sides of the constraints.

If you want to give custom names to slack variables, you have to do so during construction of the problem.

OUTPUT: a tuple

EXAMPLES:

sage: from sage_numerical_interactive_mip import InteractiveMILPProblemStandardForm
sage: A = ([1, 1], [3, 1])
sage: b = (1000, 1500)
sage: c = (10, 5)
sage: P = InteractiveMILPProblemStandardForm(A, b, c)
sage: P.slack_variables()
(x3, x4)
sage: P = InteractiveMILPProblemStandardForm(A, b, c, ["C", "B"],
....:     slack_variables=["L", "F"])
sage: P.slack_variables()
(L, F)
classmethod with_relaxation(relaxation, integer_variables=False)

Construct a MILP problem in standard form by a relaxation and a set of integer variables.

INPUT:

  • relaxation – an LP problem in standard form

  • integer_variables – (default: False) either a boolean value indicating if all the problem variables are integer or not, or a set of strings giving some problem variables’ names, where those problem variables are integer

OUTPUT:

EXAMPLES:

sage: from sage_numerical_interactive_mip import *
sage: A = ([1, 1, 2], [3, 1, 7], [6, 4, 5])
sage: b = (1000, 1500, 2000)
sage: c = (10, 5, 1)
sage: P = InteractiveLPProblemStandardForm(A, b, c)
sage: P1 = InteractiveMILPProblemStandardForm.with_relaxation(P, True)
sage: P1
MILP problem (use ... details)
sage: P == P1.relaxation()
True
sage_numerical_interactive_mip.interactive_milp_problem._form_thin_long_triangle(k)

Generate a thin long triangle.

Note

_form_thin_long_triangle() is for internal use. Generate a thin long triangle with vertices \((0, 0)\), \((1, 0)\), and \((1/2, k)\) for some given integer \(k\), and return a matrix \(A\), and an vector \(b\), where the triangle is represented by a polytope defined by \(Ax <= b\). This thin long triangle is an example of a system with large Chvatal rank.

INPUT:

  • k– an integer indicating the y coordinate of the top vertex for the triangle

OUTPUT:

  • A – a two by two matrix

  • b – a two-element vector

EXAMPLES:

sage: from sage_numerical_interactive_mip.interactive_milp_problem import _form_thin_long_triangle
sage: A, b, = _form_thin_long_triangle(4)
sage: A, b
(
    [-8  1]
    [ 8  1], (0, 8)
    )