Formulation

class formulation_bench.formulation.Formulation(path, problem)

A MILP formulation for an optimization problem.

Parameters:

pathstr or pathlib.Path

Path to the directory containing this formulation. See Formulation Directory for the expected directory structure.

problemProblem

The parent optimization problem this formulation belongs to.

Attributes:

pathpathlib.Path

Resolved absolute path to the formulation directory.

problemProblem

The parent optimization problem this formulation belongs to.

validbool

Whether this formulation is a faithful reformulation of the parent problem.

parametersdict[str, Parameter]

The parametrization of this formulation. Note this may differ from the parent problem’s parameters which define the general problem data.

definitionsdict[str, Definition]

Optional named derived quantities computed from parameters before variables are declared. Useful for defining sets, constants, etc… that are referenced in multiple places in the formulation.

assumptionslist[Assumption]

Assumptions on the problem parameters.

variablesdict[str, Variable]

Decision variables, keyed by name.

constraintslist[Constraint]

Constraints on the decision variables.

objectiveObjective

Objective function.

importslist[str]

gen_solve_py() generates a Python script with an implementation of this formulation in Gurobi. By default, the import block includes json, gurobipy, and argpase. If the formulation requires additional imports (e.g., import networkx as nx), they are included here.

lean_formulation_pathpathlib.Path

Path to a Lean file (Formulation.lean) containing a formal specification of this formulation. See MILP Formulation for details on how a MILP formulation is represented in Lean.

metadatadict[str, Any]

Free-form metadata about the formulation. Typically includes a source field with details about the origin of the formulation and a notes field with additional commentary.

Examples

Load formulation a of p12 | Traveling Salesman Problem (TSP):

>>> from formulation_bench import Dataset
>>> ds = Dataset("dataset")
>>> f = ds.problems[12].formulations["a"]
>>> f.problem.name
'Traveling Salesman Problem (TSP)'

Check if the formulation is valid:

>>> f.valid
True

Get the formulation’s parameters and assumptions:

>>> f.parameters
{'n': Parameter(...), 'c': Parameter(...)}
>>> f.assumptions
[Assumption(description='There must be at least two cities ...)]

Get the first constraint of the formulation:

>>> f.constraints[0]
Constraint(description='Each city has exactly one outgoing arc ...)

Get the formulation’s objective function:

>>> f.objective
Objective(description='Minimize the total travel cost ...)

Get the path to the Lean specification of this formulation:

>>> f.lean_formulation_path
PosixPath('.../dataset/problems/p12/formulations/a/Formulation.lean')

gen_solve_py()

Generate a Python script with a Gurobi implementation of this formulation.

The script is generated from the gurobipy code snippets in the code attribute of every formulation component (parameters, definitions, assumptions, variables, constraints, and objective). Additional imports are also included at the top of the script.

The resulting script expects --params and --solution command-line arguments for paths to the input parameters and output solution, respectively.

Examples

Generate the solve script for p12 | Traveling Salesman Problem (TSP):

>>> from formulation_bench import Dataset
>>> ds = Dataset("dataset")
>>> f = ds.problems[12].formulations["a"]  # MTZ formulation of TSP
>>> script = f.gen_solve_py()
>>> print(script)
import json
import gurobipy as gp
from gurobipy import GRB
import argparse
...
if __name__ == "__main__":
    parser = argparse.ArgumentParser()
    parser.add_argument("params", help="Path to parameters.json")
    parser.add_argument("solution", help="Path to write solution.json")
    ...

render_markdown(include_implicit=True)

Render this formulation in Markdown.

The output is produced by rendering the following Jinja template. The assumptions and constraints passed to this template are filtered according to include_implicit flag.

# {{ problem_name }}

## Problem Description

{{ problem_description }}

## Formulation

### Parameters

{% for name, p in parameters.items() %}
- **{{ name }}** (type: {{ p.type.value }}, shape: `{{ p.shape }}`): {{ p.description }}
{% endfor %}

{% if assumptions %}

### Assumptions

{% for a in assumptions %}
- {{ a.description }}
$${{ a.formulation }}$$
{% endfor %}
{% endif %}

{% if definitions %}

### Definitions

{% for name, d in definitions.items() %}
- **{{ name }}**: {{ d.description }}
$${{ d.formulation }}$$
{% endfor %}
{% endif %}

### Variables

{% for name, v in variables.items() %}
- **{{ name }}** (type: {{ v.type.value }}, shape: `{{ v.shape }}`): {{ v.description }}
{% endfor %}

### Constraints

{% for c in constraints %}
- {{ c.description }}
$${{ c.formulation }}$$
{% endfor %}

### Objective

{{ objective.description }}
$${{ objective.formulation }}$$

Parameters:

include_implicitbool, default True

If False, omit assumptions and constraints with explicit=False.

Returns:

markdownstr

The rendered Markdown string.

Examples

Render a formulation of p12 | Traveling Salesman Problem (TSP) without implicit constraints:

>>> from formulation_bench import Dataset
>>> ds = Dataset("dataset")
>>> f = ds.problems[12].formulations["a"]  # MTZ formulation of TSP
>>> md = f.render_markdown(include_implicit=False)
>>> print(md)
# Traveling Salesman Problem (TSP)

## Problem Description

The Traveling Salesman Problem (TSP) aims to find the shortest cycle in a graph that visits every node exactly once.
...
## Formulation

### Parameters

- **n** (type: integer, shape: `[]`): Number of cities
- **c** (type: continuous, shape: `['n', 'n']`): Travel cost from city i to city j
...
### Variables

- **x** (type: binary, shape: `['n', 'n']`): 1 if the tour goes directly from city i to city j, 0 otherwise
- **u** (type: continuous, shape: `['n']`): MTZ position of city i in the tour

### Constraints

- Each city has exactly one outgoing arc in the tour.
$$\sum_{j \in V,\, j \neq i} x_{ij} = 1 \quad \forall i \in V$$
- Each city has exactly one incoming arc in the tour.
$$\sum_{i \in V,\, i \neq j} x_{ij} = 1 \quad \forall j \in V$$
- MTZ subtour elimination constraint.
$$u_i - u_j + n \cdot x_{ij} \leq n - 1 \quad \forall i, j \in V \setminus \{0\},\; i \neq j$$
- Depot position is fixed to 1 to anchor the tour ordering.
$$u_0 = 1$$
- Lower bound on MTZ position: each non-depot city's position is at least 2.
$$u_i \geq 2 \quad \forall i \in V \setminus \{0\}$$
- Upper bound on MTZ position: each non-depot city's position is at most n.
$$u_i \leq n \quad \forall i \in V \setminus \{0\}$$

### Objective

Minimize the total travel cost of the Hamiltonian cycle.
$$\min \sum_{i \in V} \sum_{j \in V,\, j \neq i} c_{ij} \cdot x_{ij}$$

run_gen_params(input_path=None, output_path=None)

Run this formulation’s gen_params.py script.

Each formulation includes a gen_params.py script that transforms problem-level instance data into the specific parameter values used by the formulation. Note the solver script generated by gen_solve_py() expects these formulation-specific parameters.

Parameters:

input_pathstr or pathlib.Path, optional

Path to a data.json file containing the problem instance data. Defaults to the parent problem’s data.json.

output_pathstr or pathlib.Path, optional

Path to write the generated parameters. Defaults to parameters.json in this formulation’s directory.

Examples

Run the parameter generation script for formulation b of p1 | Amusement Park Ticket Machines:

>>> import json
>>> from formulation_bench import Dataset
>>> ds = Dataset("dataset")
>>> f = ds.problems[1].formulations["b"]

>>> # Inspect the raw problem instance data
>>> data = json.load(open(f.problem.path / "data.json", "r"))
>>> data["CashMachineProcessingRate"]
20

>>> # Run the parameter generation script and inspect
>>> f.run_gen_params()
>>> params = json.load(open(f.path / "parameters.json", "r"))
>>> params["A"]  # The variable name for "CashMachineProcessingRate"
20

with_constraint(constraint)

Return a new Formulation with one extra constraint appended.

The original formulation is not modified. Useful for creating formulations from cutting planes or fixing variable values.

Parameters:

constraintConstraint

The constraint to be added to the formulation.

Returns:

formulationFormulation

A new formulation with the added constraint.

Examples

Add a cutting plane to the MTZ TSP formulation of p12 | Traveling Salesman Problem (TSP) that prevents two-city subtours:

>>> from formulation_bench import Dataset
>>> ds = Dataset("dataset")
>>> f = ds.problems[12].formulations["a"]  # MTZ formulation of TSP
>>> c = Constraint(
...     description="No 2-city subtours",
...     formulation=r"x_{1,2} + x_{2,1} \leq 1",
...     explicit=False,
...     code={"gurobipy": "model.addConstr(x[1,2] + x[2,1] <= 1)"}
... )
>>> new_f = f.with_constraint(c)
>>> new_f.constraints[-1]
Constraint(description='No 2-city subtours', ...)