Extending Formulations
Learn how to create variants and extensions of existing formulations.
Why Extend Formulations?
- Test different mathematical models
- Add problem variants (e.g., TSP with time windows)
- Optimize for specific solvers
- Add constraints or objectives
Creating a Formulation Variant
Example: TSP with Penalties
from typing import Literal
from luna_quantum import Model, Sense
from luna_usecases.abstract import Registry, UcFormulation
from luna_usecases.traveling_salesman_problem import TspData, TspSolution
@Registry.add
class TspWithPenalties(UcFormulation[TspData, TspSolution]):
"""TSP formulation with penalty for long edges."""
name: Literal["tsp_penalties"] = "tsp_penalties"
penalty_threshold: float = 50.0
penalty_factor: float = 2.0
@staticmethod
def formulate(data: TspData) -> Model:
"""Formulate with edge penalties."""
model = Model(name="TSP_Penalties")
# ... standard TSP formulation ...
# Add penalties for long edges
for i in range(n):
for j in range(n):
if data.distance_matrix[i, j] > penalty_threshold:
objective += penalty_factor * x[i, j]
return model
Comparing Formulations
Compare different formulations on the same data:
from luna_usecases.traveling_salesman_problem import TspData, TspInstance
data = TspData(...) # Same data
formulations = {
"Standard": TspFormulation(),
"With Penalties": TspWithPenalties(penalty_threshold=50),
"Optimized": TspOptimized(),
}
for name, formulation in formulations.items():
instance = TspInstance(data=data, formulation=formulation)
# Run benchmark...
Adding New Constraints
Example: Must visit city B before city C:
# In formulate() method
model.add_constraint(
sum(p * x[b_idx, p] for p in range(n)) <
sum(p * x[c_idx, p] for p in range(n)),
name="visit_b_before_c"
)