Model¶
Model
¶
The optimization model.
Model regular linear constraints and variables like
m = Model()
m += xsum(2 * m.addVar(lb=0, ub=1, obj=c[i], type="B") for i in range(2)) == 1
Do graph stuff like
m = Model()
g = m.addGraph(
obj=c,
edges=e,
source=0,
sink=n - 1,
L=1,
U=n - 2,
type="B"
)
m.addResourceDisposable(
graph=g,
consumptionType="E",
weight=t,
boundsType="V",
lb=a,
ub=b,
name="t",
)
constr: List[flowty.entities.Constr]
property
readonly
¶
The constraints of the model.
graphs: List[flowty.entities.Graph]
property
readonly
¶
The graphs of the model.
name: str
property
writable
¶
The model name.
objectiveBound: float
property
readonly
¶
The best bound found on the objective value.
objectiveValue: float
property
readonly
¶
The objective value.
solutions: List[Solution]
property
readonly
¶
The solutions of the model.
vars: List[Var]
property
readonly
¶
The variables of the model.
__init__(self, name='')
special
¶
Initialize the optimization model.
Parameters:
Name | Type | Description | Default |
---|---|---|---|
name |
str |
The name of the model. |
'' |
addConstr(self, equa, name='')
¶
Add constraint to the model
Parameters:
Name | Type | Description | Default |
---|---|---|---|
equa |
LinEqua |
The constraint as a linear equation. |
required |
name |
str |
Name of the variable |
'' |
Returns:
Type | Description |
---|---|
Constr |
The constraint added |
addGraph(self, obj=[], edges=[], source=0, sink=-1, L=1, U=1, type='B', names=None)
¶
Add a graph. Implicitly adds edges as variables.
Parameters:
Name | Type | Description | Default |
---|---|---|---|
obj |
List[float] |
The edge cost to map into the objective function for each variable. |
[] |
edges |
List[Tuple[int, int]] |
The list of edges given as tuples of vertex indices. |
[] |
source |
int |
The source vertex. |
0 |
sink |
int |
The sink vertex. |
-1 |
L |
float |
Lower bound on path flow. |
1 |
U |
float |
Upper bound on path flow. |
1 |
type |
str |
Type as in VarType for the path flow values. The type can be "C", "B" or "I" which is continuous, binary or integer path flow. For <{http://www.w3.org/1998/Math/MathML}math><{http://www.w3.org/1998/Math/MathML}semantics><{http://www.w3.org/1998/Math/MathML}mrow><{http://www.w3.org/1998/Math/MathML}mi>U<{http://www.w3.org/1998/Math/MathML}mo>><{http://www.w3.org/1998/Math/MathML}mn>1<{http://www.w3.org/1998/Math/MathML}annotation encoding="application/x-tex">U > 1 this allows integer flow on paths. Enforcing a binary restriction in this case is a modeling decision. |
'B' |
names |
Union[str, List[str]] |
A prefix or a list of names for the edges. |
None |
Returns:
Type | Description |
---|---|
Graph |
The graph added. |
addPackingSet(self, packingSet)
¶
Add a packing set <{http://www.w3.org/1998/Math/MathML}math><{http://www.w3.org/1998/Math/MathML}semantics><{http://www.w3.org/1998/Math/MathML}mrow><{http://www.w3.org/1998/Math/MathML}mi>B<{http://www.w3.org/1998/Math/MathML}annotation encoding="application/x-tex">B where <{http://www.w3.org/1998/Math/MathML}math><{http://www.w3.org/1998/Math/MathML}semantics><{http://www.w3.org/1998/Math/MathML}mrow><{http://www.w3.org/1998/Math/MathML}msub><{http://www.w3.org/1998/Math/MathML}mo>∑<{http://www.w3.org/1998/Math/MathML}mrow><{http://www.w3.org/1998/Math/MathML}mi>i<{http://www.w3.org/1998/Math/MathML}mo>∈<{http://www.w3.org/1998/Math/MathML}mi>B<{http://www.w3.org/1998/Math/MathML}msub><{http://www.w3.org/1998/Math/MathML}mi>x<{http://www.w3.org/1998/Math/MathML}mi>i<{http://www.w3.org/1998/Math/MathML}mo>≤<{http://www.w3.org/1998/Math/MathML}mn>1<{http://www.w3.org/1998/Math/MathML}annotation encoding="application/x-tex">\sum_{i \in B} x_i \leq 1 holds true.
Parameters:
Name | Type | Description | Default |
---|---|---|---|
packingSet |
List[Var] |
The set of variables in <{http://www.w3.org/1998/Math/MathML}math><{http://www.w3.org/1998/Math/MathML}semantics><{http://www.w3.org/1998/Math/MathML}mrow><{http://www.w3.org/1998/Math/MathML}mi>B<{http://www.w3.org/1998/Math/MathML}annotation encoding="application/x-tex">B |
required |
addResourceCustom(self, graph, name='')
¶
Add a custom resource constraint.
Can be accessed using the name in callbacks.
Parameters:
Name | Type | Description | Default |
---|---|---|---|
graph |
Graph |
The graph to add the resource constraint to. |
required |
name |
str |
The resource name. |
'' |
addResourceDisposable(self, graph, consumptionType='V', weight=1, boundsType='V', lb=0, ub=1, name=None)
¶
Add a disposable resource constraint.
Parameters:
Name | Type | Description | Default |
---|---|---|---|
graph |
Graph |
The graph to add the resource constraint to. |
required |
consumptionType |
str |
Where is the resource being consumed, edge |
'V' |
weight |
Union[float, List[float]] |
The amount to consume. |
1 |
boundsType |
str |
Where is the resource being bounded, edge |
'V' |
lb |
Union[float, List[float]] |
Lower bound enforced as indicated by |
0 |
ub |
Union[float, List[float]] |
Upper bound enforced as indicated by |
1 |
name |
str |
The resource name. |
None |
addResourceNonDisposable(self, graph, consumptionType='V', weight=1, boundsType='V', lb=0, ub=1, name=None)
¶
Add a non-disposable resource constraint.
Parameters:
Name | Type | Description | Default |
---|---|---|---|
graph |
Graph |
The graph to add the resource constraint to. |
required |
consumptionType |
str |
Where is the resource being consumed, edge |
'V' |
weight |
Union[float, List[float]] |
The amount to consume. |
1 |
boundsType |
str |
Where is the resource being bounded, edge |
'V' |
lb |
Union[float, List[float]] |
Lower bound enforced as indicated by |
0 |
ub |
Union[float, List[float]] |
Upper bound enforced as indicated by |
1 |
name |
str |
The resource name. |
None |
addVar(self, lb=-inf, ub=inf, obj=0, type='C', name='')
¶
Add variable to the model
Parameters:
Name | Type | Description | Default |
---|---|---|---|
lb |
float |
Lower bound |
-inf |
ub |
float |
Upper bound |
inf |
obj |
float |
Objective coefficient |
0 |
type |
str |
Type as in VarType. Values can be "C", "B", or "I" which is continuous, binary, or general integer type respectively |
'C' |
name |
str |
Name of the variable |
'' |
Returns:
Type | Description |
---|---|
Var |
The variable added |
optimize(self)
¶
Optimize the model.
Returns:
Type | Description |
---|---|
OptimizationStatus |
The status of the optimization. |
read(self, filename)
¶
Read a model from file.
Parameters:
Name | Type | Description | Default |
---|---|---|---|
filename |
str |
The path to file. |
required |
setCallback(self, callback)
¶
Set a callback function with signature
def callback(callbackModel: CallbackModel, where: Where) -> None:
pass
Use the CallbackModel to get/set data. Use the Where to determine where in the algorithm flow the callback is invoked.
Parameters:
Name | Type | Description | Default |
---|---|---|---|
callback |
Callable |
The callback function in python |
required |
setCallbackGraphWeight(self, graph, states, callback)
¶
Set a callback function to get user defined weights of edges for a specific graph with signature
def callbackGraphWeight(
states: Dict[str, float], edge: Tuple[int, int]
) -> Dict[str, float]:
pass
The states
list defines a list of resource names whose values are
passed to the callback.
The callback returns a dictionary with resource names
as keys and edge weights as values. System resources cost
and actualCost
can be used. Note that, cost
represents reduced cost calculation in a path
MIP context. The returned edge weights are used in the extension step.
Use the parameter CallbackGraphWeightUseCache
to enable/disable caching for
identical calls to the callback. Caching is enabled on default.
If states["name"]
is equal to the minimum value of a float
then the
callbacks asks for a global minimum value of the resource name
for this edge.
This is used to calculate the step size in the dynamic programming algorithm.
Test this with
import sys
def callbackGraphWeight(
states: Dict[str, float], edge: Tuple[int, int]
) -> Dict[str, float]:
if states["name"] == sys.float_info.min:
minValue = 0
return {"name": minValue}
pass
Parameters:
Name | Type | Description | Default |
---|---|---|---|
graph |
Graph |
The graph to attach the weight function to |
required |
states |
List[str] |
List of resource names whose state is given as input to the callback |
required |
callback |
Callable |
The callback function |
required |
setDominancePenalty(self, graph, resourceName, coef)
¶
Set a penalty term to be used for dominance in the dynamic programming algorithm. For instance, for resource dependent costs it may be necessary to add a penalty term when comparing costs between labels if one desires the resources to be disposable.
For two labels <{http://www.w3.org/1998/Math/MathML}math><{http://www.w3.org/1998/Math/MathML}semantics><{http://www.w3.org/1998/Math/MathML}mrow><{http://www.w3.org/1998/Math/MathML}mi>L<{http://www.w3.org/1998/Math/MathML}annotation encoding="application/x-tex">L and <{http://www.w3.org/1998/Math/MathML}math><{http://www.w3.org/1998/Math/MathML}semantics><{http://www.w3.org/1998/Math/MathML}mrow><{http://www.w3.org/1998/Math/MathML}msup><{http://www.w3.org/1998/Math/MathML}mi>L<{http://www.w3.org/1998/Math/MathML}mo lspace="0em" mathvariant="normal" rspace="0em">′<{http://www.w3.org/1998/Math/MathML}annotation encoding="application/x-tex">L' the penlaty term is of the form
<{http://www.w3.org/1998/Math/MathML}math><{http://www.w3.org/1998/Math/MathML}semantics><{http://www.w3.org/1998/Math/MathML}mrow><{http://www.w3.org/1998/Math/MathML}mi>p<{http://www.w3.org/1998/Math/MathML}mi>e<{http://www.w3.org/1998/Math/MathML}mi>n<{http://www.w3.org/1998/Math/MathML}mi>a<{http://www.w3.org/1998/Math/MathML}mi>l<{http://www.w3.org/1998/Math/MathML}mi>t<{http://www.w3.org/1998/Math/MathML}mi>y<{http://www.w3.org/1998/Math/MathML}mo>=<{http://www.w3.org/1998/Math/MathML}mi>max<{http://www.w3.org/1998/Math/MathML}mo><{http://www.w3.org/1998/Math/MathML}mo stretchy="false">{<{http://www.w3.org/1998/Math/MathML}mn>0<{http://www.w3.org/1998/Math/MathML}mo separator="true">,<{http://www.w3.org/1998/Math/MathML}mo stretchy="false">(<{http://www.w3.org/1998/Math/MathML}msup><{http://www.w3.org/1998/Math/MathML}mi>L<{http://www.w3.org/1998/Math/MathML}mo lspace="0em" mathvariant="normal" rspace="0em">′<{http://www.w3.org/1998/Math/MathML}mo stretchy="false">(<{http://www.w3.org/1998/Math/MathML}mi>r<{http://www.w3.org/1998/Math/MathML}mi>e<{http://www.w3.org/1998/Math/MathML}mi>s<{http://www.w3.org/1998/Math/MathML}mi>o<{http://www.w3.org/1998/Math/MathML}mi>u<{http://www.w3.org/1998/Math/MathML}mi>r<{http://www.w3.org/1998/Math/MathML}mi>c<{http://www.w3.org/1998/Math/MathML}mi>e<{http://www.w3.org/1998/Math/MathML}mi>N<{http://www.w3.org/1998/Math/MathML}mi>a<{http://www.w3.org/1998/Math/MathML}mi>m<{http://www.w3.org/1998/Math/MathML}mi>e<{http://www.w3.org/1998/Math/MathML}mo stretchy="false">)<{http://www.w3.org/1998/Math/MathML}mo>−<{http://www.w3.org/1998/Math/MathML}mi>L<{http://www.w3.org/1998/Math/MathML}mo stretchy="false">(<{http://www.w3.org/1998/Math/MathML}mi>r<{http://www.w3.org/1998/Math/MathML}mi>e<{http://www.w3.org/1998/Math/MathML}mi>s<{http://www.w3.org/1998/Math/MathML}mi>o<{http://www.w3.org/1998/Math/MathML}mi>u<{http://www.w3.org/1998/Math/MathML}mi>r<{http://www.w3.org/1998/Math/MathML}mi>c<{http://www.w3.org/1998/Math/MathML}mi>e<{http://www.w3.org/1998/Math/MathML}mi>N<{http://www.w3.org/1998/Math/MathML}mi>a<{http://www.w3.org/1998/Math/MathML}mi>m<{http://www.w3.org/1998/Math/MathML}mi>e<{http://www.w3.org/1998/Math/MathML}mo stretchy="false">)<{http://www.w3.org/1998/Math/MathML}mo stretchy="false">)<{http://www.w3.org/1998/Math/MathML}mi>c<{http://www.w3.org/1998/Math/MathML}mi>o<{http://www.w3.org/1998/Math/MathML}mi>e<{http://www.w3.org/1998/Math/MathML}mi>f<{http://www.w3.org/1998/Math/MathML}mo stretchy="false">}<{http://www.w3.org/1998/Math/MathML}annotation encoding="application/x-tex"> penalty = \max\{0, (L'(resourceName) - L(resourceName)) coef \}
and the cost comparison when determining dominance between the labels is
<{http://www.w3.org/1998/Math/MathML}math><{http://www.w3.org/1998/Math/MathML}semantics><{http://www.w3.org/1998/Math/MathML}mrow><{http://www.w3.org/1998/Math/MathML}mi>L<{http://www.w3.org/1998/Math/MathML}mo stretchy="false">(<{http://www.w3.org/1998/Math/MathML}mi>c<{http://www.w3.org/1998/Math/MathML}mi>o<{http://www.w3.org/1998/Math/MathML}mi>s<{http://www.w3.org/1998/Math/MathML}mi>t<{http://www.w3.org/1998/Math/MathML}mo stretchy="false">)<{http://www.w3.org/1998/Math/MathML}mo>+<{http://www.w3.org/1998/Math/MathML}mi>p<{http://www.w3.org/1998/Math/MathML}mi>e<{http://www.w3.org/1998/Math/MathML}mi>n<{http://www.w3.org/1998/Math/MathML}mi>a<{http://www.w3.org/1998/Math/MathML}mi>l<{http://www.w3.org/1998/Math/MathML}mi>t<{http://www.w3.org/1998/Math/MathML}mi>y<{http://www.w3.org/1998/Math/MathML}mo>≤<{http://www.w3.org/1998/Math/MathML}msup><{http://www.w3.org/1998/Math/MathML}mi>L<{http://www.w3.org/1998/Math/MathML}mo lspace="0em" mathvariant="normal" rspace="0em">′<{http://www.w3.org/1998/Math/MathML}mo stretchy="false">(<{http://www.w3.org/1998/Math/MathML}mi>c<{http://www.w3.org/1998/Math/MathML}mi>o<{http://www.w3.org/1998/Math/MathML}mi>s<{http://www.w3.org/1998/Math/MathML}mi>t<{http://www.w3.org/1998/Math/MathML}mo stretchy="false">)<{http://www.w3.org/1998/Math/MathML}annotation encoding="application/x-tex"> L(cost) + penalty \leq L'(cost)
Note
There can only be one penalty term applied per graph. The penalty term will always have the above form.
Parameters:
Name | Type | Description | Default |
---|---|---|---|
graph |
Graph |
The graph for which the penalty term is valid |
required |
resourceName |
str |
The name of resource on which the label cost depend |
required |
coef |
float |
the coefficient in the linear penalty term |
required |
setLicenseKey(self, user, key)
¶
Set the user and license key. If no key is set the community license is used.
Note
The community license is a free license to the general community which may have limited features and additional restrictions.
Parameters:
Name | Type | Description | Default |
---|---|---|---|
user |
str |
The user name. |
required |
key |
str |
The license key. |
required |
setObjective(self, expr)
¶
Set the objective function.
Parameters:
Name | Type | Description | Default |
---|---|---|---|
expr |
Union[flowty.entities.LinExpr, Tuple[str, flowty.entities.LinExpr]] |
Defaults to minimization. Otherwise set with tuple of a ObjSense and a linear expression. |
required |
setParam(self, key, value)
¶
Set a parameter. Valid parameters are
Name | Type | Description | Default |
---|---|---|---|
Algorithm |
str |
What algorithm to use. Options are PathMIP for the path MIP algorithm, MIP for the branch-and-cut algorithm, and DP for the dynamic programming algorithm. |
PathMIP |
Verbosity |
str |
Turn verbosity on/off. | On |
Threads |
int |
The approximate number of threads to use. | 4 |
NodeLimit |
int |
The branch-and-bound node limit. If limit is reached optimization stops with status NodeLimit | inf |
SolutionLimit |
int |
The maximum number of solutions. If limit is reached optimization stops with status SolutionLimit | inf |
TimeLimit |
float |
The computation time limit in seconds. If limit is reached optimization stops with status TimeLimit | inf |
SubproblemTimeLimit |
float |
The computation time limit in seconds for solving subproblems. If limit is reached and feasible solutions are found the subproblem stop otherwise it continues for another interval until proving optimality. | inf |
Gap |
float |
The absolute gap between objective upper and lower bound. | 1e-4 |
CallbackDP |
str |
If a callback function is set should it also be used in the dynamic programing algorithm. For performance reasons this should be avoided if not needed. | Off |
MIPSolver |
str |
Specify the underlying MIP solver. Options are Cbc for the COIN Cbc solver or Xpress for FICO Xpress solver. |
Cbc |
LogBranchNodeInterval |
int |
Interval to log branch node info. | 10 |
LogFilename |
str |
Name of logfile. Disable file logging by setting an empty string | flowty.log |
LogPath |
str |
Path to folder to place the log files. | logs |
LogRelaxationIterationInterval |
int |
Interval to log iteration info in branch node. | 1 |
LogRelaxationRootNodeOnly |
int |
Log only iterattion info in the root branch node. | 0 |
DumpLpProblems |
int |
Dump all LPs to disk and have a look around. | 0 |
NgMaxSize |
int |
Max size of the ng-neighbood path relaxation. | 8 |
RelaxDualSimplex |
int |
Priority of dual simplex relaxation. Can only be disabled if primal simplex or barrier is used. Set negtive value to disable. | 0 |
RelaxPrimalSimplex |
int |
Priority of primal simplex relaxation. Disabled on default. Set negtive value to disable. | -1 |
RelaxBarrier |
int |
Priority of barrier relaxation. Disabled on default. Set negtive value to disable. | -1 |
RelaxSubgradient |
int |
Priority of subgradient relaxation. Disabled on default. Set negtive value to disable. | -1 |
PricerMaxColumnsExact |
int |
Number of columns to add for the exact pricing algorithm. Per subproblem. | 150 |
PricerMaxColumnsHeuristic |
int |
Number of columns to add for the heuristic pricing algorithm. Per subproblem. | 30 |
PricerUseHeuristics |
int |
Use the heuristic pricing algorithm. | 1 |
PricerDoRelaxedBound |
int |
Periodically calculate lower bounds using relaxed pricing algorithms. | 0 |
PricerTolerance |
float |
The tolerence level for adding columns in the pricing algorithm. | 1e-4 |
PrimalHeuristicRestrictedMasterIterationInterval |
int |
Interval to call the restricted master heuristic in branch node. | 0 |
PrimalHeuristicRestrictedMasterDepthInterval |
int |
Branch tree depth interval for the restricted master heuristic. | 1 |
PrimalHeuristicRestrictedMasterDepthMax |
int |
Set max branch tree depth for the restricted master heuristic. | inf |
PrimalHeuristicRestrictedMasterTimeLimit |
float |
Set time limit for the restricted master heuristic. | 10 |
PricerTailingOffLength |
int |
The number of iterations to consider when tailing off. Setting to 0 length disables tailing off calculation. | 10 |
PricerTailingOffAvgActivity |
int |
The maximum average number of colums and cuts generated for tailing off iterations. | 3 |
PricerTailingOffImprovement |
float |
The minimum improvement in the dual value for the tailing off calculation. | 0.02 |
DoubleComparisonEpsilon |
float |
The epsilon used to compare floating point values. | 1e-6 |
CallbackGraphWeightUseCache |
int |
Enable caching if callback funtions for edge weights are used. | 1 |
Parameters:
Name | Type | Description | Default |
---|---|---|---|
key |
str |
The name of the parameter to set. |
required |
value |
Union[str, int, float] |
The value to assign. |
required |
write(self, filename)
¶
Write a model to file.
Parameters:
Name | Type | Description | Default |
---|---|---|---|
filename |
str |
The path to file. |
required |