models

Typed records for components of a formulation.

These dataclasses mirror the JSON schema defined in Dataset Schema.

class formulation_bench.models.Parameter(description, type, shape)

MILP formulation parameter.

Attributes:

descriptionstr

Human-readable description of the parameter.

typeParameterType

Numeric type of a parameter (continuous, integer, or binary).

shapeShape

Index structure of the parameter.

Examples

Examine the CashMachineProcessingRate of formulation a for problem p1 | Amusement Park Ticket Machines:

>>> from formulation_bench import Dataset
>>> ds = Dataset("dataset")
>>> p1 = ds.problems[1]
>>> p = p1.formulations["a"].parameters["CashMachineProcessingRate"]
>>> p.description
'Processing rate of a cash-based machine in people per hour'
>>> p.type
<ParameterType.continuous: 'continuous'>
>>> p.shape
Shape([])

Examine the shape of the cost matrix c in p12 | Traveling Salesman Problem (TSP), a matrix indexed by the scalar parameter n (number of cities):

>>> p12 = ds.problems[12]
>>> p = p12.formulations["a"].parameters["c"]
>>> p.description
'Travel cost from city i to city j'
>>> p.shape
Shape(['n', 'n'])

class formulation_bench.models.ParameterType(*values)

Numeric type of a Parameter.

binary = 'binary'

continuous = 'continuous'

integer = 'integer'

class formulation_bench.models.Variable(description, type, shape, indices=None)

MILP formulation decision variable.

Attributes:

descriptionstr

Human-readable description of the variable.

typeVariableType

Variable domain (continuous, integer, or binary).

shapeShape

Index structure of the variable. If the shape contains a cardinality dimension (DimensionType.cardinality), the Python expression for the indices to create the variable can’t be inferred. They must be provided via the indices attribute (see below).

indicesstr or None, optional

Python expression (a generator or comprehension) producing the explicit set of index keys passed to model.addVars. Must be provided if the shape contains a cardinality dimension.

Examples

A scalar variable (empty shape) from formulation a of p1 | Amusement Park Ticket Machines:

>>> from formulation_bench import Dataset
>>> ds = Dataset("dataset")
>>> v = ds.problems[1].formulations["a"].variables["NumCashMachines"]
>>> v.description
'The number of cash-based machines'
>>> v.type
<VariableType.integer: 'integer'>
>>> v.shape
Shape([])
>>> v.indices is None
True

A one-dimensional variable in formulation a of p2 | Electricity Generation Experiment. The single dimension is driven by the scalar parameter NumExperiments:

>>> v = ds.problems[2].formulations["a"].variables["ConductExperiment"]
>>> v.type
<VariableType.integer: 'integer'>
>>> v.shape
Shape(['NumExperiments'])

A variable with a ragged dimension in formulation a of p11 | Sub-Hour Unit Commitment (SHUC). The middle dimension n_S[n_G] is ragged: for each generator g it ranges over n_S[g] startup categories:

>>> v = ds.problems[11].formulations["a"].variables["d_su"]
>>> v.type
<VariableType.binary: 'binary'>
>>> v.shape
Shape(['n_G', 'n_S[n_G]', 'T'])
>>> v.shape.is_ragged
True

A variable indexed over an irregular set in formulation a of p7 | Rectangular Tiling with One Hole per Row and Column (IMO6). Its shape carries a cardinality dimension |I| documenting the conceptual size, while indices gives the explicit expression passed to model.addVars:

>>> p7a = ds.problems[7].formulations["a"]
>>> p7a.definitions["I"].description
'Set of column interval pairs (a, b) with a <= b'
>>> x = p7a.variables["x"]
>>> x.shape
Shape(['N', '|I|'])
>>> x.shape.has_cardinality
True
>>> x.indices
'(i, a, b) for i in R for (a, b) in I'

class formulation_bench.models.VariableType(*values)

Domain of a decision Variable.

binary = 'binary'

continuous = 'continuous'

integer = 'integer'

class formulation_bench.models.Definition(description, code, formulation)

A named derived quantity computed from parameters.

Typically defines sets, constants, etc… that are used by multiple constraints and/or the objective.

Attributes:

descriptionstr

Human-readable description.

formulationstr

LaTeX form of the definition.

codedict[str, str]

Per-language source for the definition. The "python" key is used by Formulation.gen_solve_py() to generate Python code that computes the definition in the solver script.

Examples

Formulation a of p8 | Job Shop Scheduling Problem (JSSP) defines a big-M constant M:

>>> from formulation_bench import Dataset
>>> ds = Dataset("dataset")
>>> p8 = ds.problems[8]
>>> d = p8.formulations["a"].definitions["M"]
>>> d.description
'Big-M constant: sum of all processing times'
>>> d.code["python"]
'M = sum(p[j][k] for j in range(n) for k in range(m))'

class formulation_bench.models.Assumption(description, formulation, explicit, code)

An assumption on the problem parameters.

Attributes:

descriptionstr

Human-readable description.

formulationstr

LaTeX form of the assumption.

codedict[str, str]

Per-language source for the assumption. The "python" key is used by Formulation.gen_solve_py() to generate assertions in the solver script.

explicitbool

True if the assumption is stated explicitly in the source problem text; False if it is implicit.

Examples

Formulation a of p8 | Job Shop Scheduling Problem (JSSP) assumes that all processing times are non-negative:

>>> from formulation_bench import Dataset
>>> ds = Dataset("dataset")
>>> p8 = ds.problems[8]
>>> a = p8.formulations["a"]
>>> a.assumptions[0].description
'Processing times are non-negative.'
>>> a.assumptions[0].explicit
False
>>> a.assumptions[0].code["python"]
'assert all(p[j][k] >= 0 for j in range(n) for k in range(m))'

class formulation_bench.models.Constraint(description, formulation, explicit, code)

A constraint on the decision variables.

Attributes:

descriptionstr

Human-readable description.

formulationstr

LaTeX form of the constraint.

codedict[str, str]

Per-language source for the constraint. The "gurobipy" key is used by Formulation.gen_solve_py() to add constraints to the model in the solver script.

explicitbool

True if the constraint is stated explicitly in the source problem text; False if it is implicit.

Examples

Formulation a of p12 | Traveling Salesman Problem (TSP) includes the MTZ subtour elimination constraint:

>>> from formulation_bench import Dataset
>>> ds = Dataset("dataset")
>>> p12 = ds.problems[12]
>>> a = p12.formulations["a"]
>>> c = a.constraints[2]
>>> c.description
'MTZ subtour elimination constraint.'
>>> c.explicit
True
>>> c.formulation
'u_i - u_j + n \\cdot x_{ij} \\leq n - 1 ...'
>>> c.code["gurobipy"]
'model.addConstrs(u[i] - u[j] + n * x[i, j] <= n - 1...)'

class formulation_bench.models.Objective(description, formulation, code)

The objective function of a formulation.

Attributes:

descriptionstr

Human-readable description.

formulationstr

LaTeX form of the objective.

codedict[str, str]

Per-language source for the objective. The "gurobipy" key is used by Formulation.gen_solve_py() to set the objective in the model in the solver script.

Examples

Formulation a of p12 | Traveling Salesman Problem (TSP) minimizes the total travel cost:

>>> from formulation_bench import Dataset
>>> ds = Dataset("dataset")
>>> p12 = ds.problems[12]
>>> a = p12.formulations["a"]
>>> a.objective.description
'Minimize the total travel cost of the Hamiltonian cycle.'
>>> a.objective.formulation
'\\min \\sum_{i \\in V} \\sum_{j \\in V,\\, j \\neq i} c_{ij} \\cdot x_{ij}'
>>> a.objective.code["gurobipy"]
'model.setObjective(gp.quicksum(c[i][j] * x[i, j] ...), GRB.MINIMIZE)'

class formulation_bench.models.Solution(variables, objective)

A reference optimal solution.

Attributes:

variablesdict[str, object]

Variable values keyed by name.

objectivefloat

Optimal objective value.

Examples

p12 | Traveling Salesman Problem (TSP) has a reference solution with objective value 6859:

>>> from formulation_bench import Dataset
>>> ds = Dataset("dataset")
>>> p12 = ds.problems[12]
>>> p12.solution.objective
6859

class formulation_bench.models.Shape(dimensions)

The index structure of a Parameter or Variable.

Attributes:

dimensionstuple[Dimension, …]

The ordered dimensions of the shape; an empty tuple denotes a scalar.

is_scalarbool

Whether the shape has no dimensions (i.e. denotes a scalar).

has_cardinalitybool

Whether any dimension is DimensionType.cardinality.

is_raggedbool

Whether any dimension is DimensionType.ragged.

Examples

A scalar has an empty shape:

>>> from formulation_bench import Dataset
>>> ds = Dataset("dataset")
>>> ds.problems[1].formulations["a"].variables["NumCashMachines"].shape
Shape([])

A multi-dimensional shape is a sequence of Dimension objects:

>>> shape = ds.problems[12].formulations["a"].parameters["c"].shape
>>> shape
Shape(['n', 'n'])
>>> shape[0]
Dimension(dim_str='n', type=<DimensionType.fixed: 'fixed'>)
>>> shape.is_scalar
False

A ragged shape’s index can be resolved to the dimension it refers to:

>>> shape = ds.problems[11].formulations["a"].parameters["ell"].shape
>>> shape
Shape(['n_G', 'n_S[n_G]'])
>>> shape.is_ragged
True
>>> shape.resolve(shape[1])
Dimension(dim_str='n_G', type=<DimensionType.fixed: 'fixed'>)

classmethod parse(raw)

Parse a raw JSON shape list into a typed Shape.

resolve(dimension)

Return the dimension a ragged dimension’s index refers to.

For a ragged dimension "X[Y]", returns the dimension in this shape whose dim_str is Y, or None if there is no such dimension or dimension is not ragged.

class formulation_bench.models.Dimension(dim_str, type)

A single dimension of a Shape.

Attributes:

dim_strstr

String representation of the dimension.

typeDimensionType

The type of the dimension that determines how dim_str is interpreted.

arraystr or None

For a ragged dimension of the form "X[Y]", the array X; None otherwise.

indexed_bystr or None

For a ragged dimension of the form "X[Y]", the index Y; None otherwise.

set_namestr or None

For a cardinality dimension of the form "|X|", the set X; None otherwise.

Examples

A fixed dimension names a scalar parameter:

>>> from formulation_bench import Dataset
>>> ds = Dataset("dataset")
>>> shape = ds.problems[12].formulations["a"].parameters["c"].shape
>>> shape
Shape(['n', 'n'])
>>> shape[0]
Dimension(dim_str='n', type=<DimensionType.fixed: 'fixed'>)

An expression dimension names an expression of scalar parameters:

>>> shape = ds.problems[10].formulations["a"].variables["x"].shape
>>> shape
Shape(['K+N', 'K+N'])
>>> shape[0]
Dimension(dim_str='K+N', type=<DimensionType.expression: 'expression'>)

A ragged dimension "X[Y]" exposes its array X and index Y:

>>> shape = ds.problems[11].formulations["a"].parameters["ell"].shape
>>> shape
Shape(['n_G', 'n_S[n_G]'])
>>> shape[1].type
<DimensionType.ragged: 'ragged'>
>>> shape[1].array
'n_S'
>>> shape[1].indexed_by
'n_G'

A cardinality dimension "|X|" exposes its set X:

>>> shape = ds.problems[7].formulations["a"].variables["x"].shape
>>> shape
Shape(['N', '|I|'])
>>> shape[1].type
<DimensionType.cardinality: 'cardinality'>
>>> shape[1].set_name
'I'

classmethod parse(raw)

Classify a raw dimension string into a typed Dimension.

class formulation_bench.models.DimensionType(*values)

The type of a Dimension of a Shape.

• Fixed. Range over scalar parameter (e.g., range(n))

• Expression. Range over expression of scalar parameters (e.g., range(x+y))

• Ragged. Range over indexed array of scalars (e.g., range(a[i]))

• Cardinality. Range over the cardinality of a set (e.g., range(|I|))

cardinality = 'cardinality'

expression = 'expression'

fixed = 'fixed'

ragged = 'ragged'