Constraint Relaxation

Understand how LumiX transforms hard constraints into soft constraints with deviation variables.

Overview

Constraint relaxation is the process of converting a hard constraint (must be satisfied) into a soft constraint (can be violated with a penalty). This is the foundation of goal programming.

The relaxation creates:

  • Equality constraint with deviation variables

  • Positive deviation variable (over-achievement)

  • Negative deviation variable (under-achievement)

  • Goal instances that serve as the data source for deviations

Relaxation Mathematics

Basic Transformation

A hard constraint is transformed by adding deviation variables:

Hard Constraint:  expr ≤ rhs

Relaxed Form:     expr + neg_dev - pos_dev = rhs
                  neg_dev ≥ 0
                  pos_dev ≥ 0

Interpretation:

  • If expr < rhs: neg_dev > 0, pos_dev = 0 (under-achievement)

  • If expr > rhs: neg_dev = 0, pos_dev > 0 (over-achievement)

  • If expr = rhs: neg_dev = 0, pos_dev = 0 (goal achieved)

Constraint Types

Different constraint senses require different deviation penalties:

Less-Than-or-Equal (LE: ≤):

Original:  expr ≤ rhs
Relaxed:   expr + neg_dev - pos_dev = rhs
Minimize:  pos_dev  (over-achievement is undesired)

Example: overtime ≤ 40 hours
- Want to stay under 40 hours
- Exceeding 40 (pos_dev > 0) is penalized

Greater-Than-or-Equal (GE: ≥):

Original:  expr ≥ rhs
Relaxed:   expr + neg_dev - pos_dev = rhs
Minimize:  neg_dev  (under-achievement is undesired)

Example: production ≥ 1000 units
- Want at least 1000 units
- Producing less (neg_dev > 0) is penalized

Equality (EQ: =):

Original:  expr = rhs
Relaxed:   expr + neg_dev - pos_dev = rhs
Minimize:  pos_dev + neg_dev  (any deviation is undesired)

Example: budget = 50000
- Want exactly 50000
- Both over and under are penalized

Automatic Relaxation

Using .as_goal()

LumiX automatically relaxes constraints when you use .as_goal():

from lumix import LXConstraint
from lumix.core.expressions import LXLinearExpression

# Define a hard constraint
demand_constraint = (
    LXConstraint[Product]("demand")
    .expression(production_expr)
    .ge()
    .rhs(lambda p: p.demand_target)
    .from_data(products)
)

# Mark as goal - automatic relaxation happens!
demand_goal = (
    LXConstraint[Product]("demand")
    .expression(production_expr)
    .ge()
    .rhs(lambda p: p.demand_target)
    .as_goal(priority=1, weight=1.0)  # This triggers relaxation
    .from_data(products)
)

# Behind the scenes, LumiX:
# 1. Creates pos_dev and neg_dev variables
# 2. Converts to equality: production + neg_dev - pos_dev = demand_target
# 3. Adds neg_dev to objective (since GE constraint)

What Happens Internally

        graph LR
    A[Original Constraint] -->|as_goal| B[LXGoalMetadata]
    B --> C[relax_constraint]
    C --> D[Create Goal Instances]
    C --> E[Create Deviation Variables]
    C --> F[Build Equality Constraint]
    D --> E
    E --> F
    F --> G[RelaxedConstraint]

    style A fill:#e1f5ff
    style B fill:#fff4e1
    style C fill:#ffe1e1
    style D fill:#e1ffe1
    style E fill:#f0e1ff
    style F fill:#e8f4f8
    style G fill:#ffe8e8

Manual Relaxation

Direct API Usage

You can manually relax constraints using the relaxation API:

from lumix.goal_programming import relax_constraint, LXGoalMetadata
from lumix.core.enums import LXConstraintSense

# Create goal metadata
metadata = LXGoalMetadata(
    priority=1,
    weight=1.0,
    constraint_sense=LXConstraintSense.GE
)

# Define constraint (not a goal yet)
demand_constraint = (
    LXConstraint[Product]("demand")
    .expression(production_expr)
    .ge()
    .rhs(lambda p: p.demand_target)
    .from_data(products)
)

# Manually relax
relaxed = relax_constraint(demand_constraint, metadata)

# Access components
equality_constraint = relaxed.constraint
pos_deviation_var = relaxed.pos_deviation
neg_deviation_var = relaxed.neg_deviation
goal_instances = relaxed.goal_instances
metadata_ref = relaxed.goal_metadata

Batch Relaxation

Relax multiple constraints at once:

from lumix.goal_programming import relax_constraints

constraints = [demand_constraint, quality_constraint, cost_constraint]

metadata_map = {
    "demand": LXGoalMetadata(priority=1, weight=1.0, constraint_sense=LXConstraintSense.GE),
    "quality": LXGoalMetadata(priority=2, weight=1.0, constraint_sense=LXConstraintSense.GE),
    "cost": LXGoalMetadata(priority=3, weight=0.5, constraint_sense=LXConstraintSense.LE),
}

relaxed_list = relax_constraints(constraints, metadata_map)

for relaxed in relaxed_list:
    print(f"Relaxed: {relaxed.constraint.name}")
    print(f"  Positive deviation variable: {relaxed.pos_deviation.name}")
    print(f"  Negative deviation variable: {relaxed.neg_deviation.name}")
    print(f"  Goal instances: {len(relaxed.goal_instances)}")

Goal Instances

Semantic Indexing

Deviation variables are indexed by Goal instances, not by the original data. This provides semantic meaning to deviations:

# Each product gets a Goal instance
# Goal instance contains metadata about the goal

for goal in relaxed.goal_instances:
    print(f"Goal ID: {goal.id}")
    print(f"  Constraint: {goal.constraint_name}")
    print(f"  Priority: {goal.priority}")
    print(f"  Weight: {goal.weight}")
    print(f"  Target Value: {goal.target_value}")
    print(f"  Instance ID: {goal.instance_id}")

Example for indexed constraint:

# Constraint: production[product] >= demand[product]
# Creates goals:
#   - Goal("demand_product_A", constraint_name="demand", instance_id="product_A", ...)
#   - Goal("demand_product_B", constraint_name="demand", instance_id="product_B", ...)
#
# Deviation variables:
#   - pos_dev[Goal("demand_product_A")]
#   - pos_dev[Goal("demand_product_B")]
#   - neg_dev[Goal("demand_product_A")]
#   - neg_dev[Goal("demand_product_B")]

Business Value

Goal instances make deviations meaningful:

Instead of:
    "neg_dev[0] = 10"  (What does this mean?)

You get:
    "Route 5 needs 3 additional buses"
    "Product A has 20 units excess inventory"
    "Department B is 5 hours over overtime limit"

Practical Examples

Production Planning

from dataclasses import dataclass

@dataclass
class Product:
    id: str
    demand_target: float
    production_cost: float

products = [
    Product("A", demand_target=100, production_cost=5),
    Product("B", demand_target=150, production_cost=6),
]

# Define production variable
production = (
    LXVariable[Product, float]("production")
    .continuous()
    .bounds(lower=0)
    .indexed_by(lambda p: p.id)
    .from_data(products)
)

# Goal: Meet demand
demand_goal = (
    LXConstraint[Product]("demand")
    .expression(
        LXLinearExpression()
        .add_term(production, coeff=1.0)
    )
    .ge()
    .rhs(lambda p: p.demand_target)
    .as_goal(priority=1, weight=1.0)
    .from_data(products)
)

# When relaxed, creates:
#   - Goal instances: [Goal("demand_A", ...), Goal("demand_B", ...)]
#   - Variables: pos_dev[Goal], neg_dev[Goal] for each goal
#   - Constraint: production[p] + neg_dev - pos_dev = p.demand_target

Resource Constraints with Goals

@dataclass
class Resource:
    id: str
    capacity: float
    target_utilization: float  # e.g., 0.8 for 80%

# Hard constraint: Cannot exceed capacity
capacity_hard = (
    LXConstraint[Resource]("capacity")
    .expression(usage_expr)
    .le()
    .rhs(lambda r: r.capacity)
    .from_data(resources)
    # No .as_goal() - stays hard constraint
)

# Soft goal: Target utilization
utilization_goal = (
    LXConstraint[Resource]("utilization")
    .expression(usage_expr)
    .eq()  # Want exact target
    .rhs(lambda r: r.capacity * r.target_utilization)
    .as_goal(priority=2, weight=1.0)
    .from_data(resources)
)

# Result:
#   - Capacity is hard limit (never exceeded)
#   - Utilization can deviate but is penalized

Deviation Variable Details

Naming Convention

Deviation variables follow a standard naming pattern:

from lumix.goal_programming import get_deviation_var_name

# For a goal named "demand"
pos_name = get_deviation_var_name("demand", "pos")  # "demand_pos_dev"
neg_name = get_deviation_var_name("demand", "neg")  # "demand_neg_dev"

Variable Bounds

Deviation variables are always non-negative continuous variables:

# Automatically created as:
pos_deviation = (
    LXVariable[LXGoal, float]("demand_pos_dev")
    .continuous()
    .bounds(lower=0.0)  # Non-negative
    .indexed_by(lambda g: g.id)
    .from_data(goal_instances)
)

Accessing in Solution

Deviation values are available in the solution:

solution = optimizer.solve(model)

# Via goal deviations
deviations = solution.get_goal_deviations("demand")
print(f"Positive deviations: {deviations['pos']}")
print(f"Negative deviations: {deviations['neg']}")

# Via variable access
pos_dev_values = solution.get_variable(relaxed.pos_deviation)
neg_dev_values = solution.get_variable(relaxed.neg_deviation)

Understanding Undesired Deviations

Deviation Selection

The relaxation automatically determines which deviations to minimize:

# For LE (≤)
undesired = relaxed.goal_metadata.is_pos_undesired()  # True
# Minimizes: pos_dev (over-achievement)

# For GE (≥)
undesired = relaxed.goal_metadata.is_neg_undesired()  # True
# Minimizes: neg_dev (under-achievement)

# For EQ (=)
undesired_pos = relaxed.goal_metadata.is_pos_undesired()  # True
undesired_neg = relaxed.goal_metadata.is_neg_undesired()  # True
# Minimizes: both pos_dev and neg_dev

Getting Undesired Variables

# Get list of deviation variables to include in objective
undesired_vars = relaxed.get_undesired_variables()

# For GE constraint, returns: [neg_deviation]
# For LE constraint, returns: [pos_deviation]
# For EQ constraint, returns: [pos_deviation, neg_deviation]

Best Practices

  1. Mix Hard and Soft Constraints

    # Hard constraints for physical limits
capacity = (
    LXConstraint[Resource]("capacity")
    .expression(usage_expr)
    .le()
    .rhs(lambda r: r.max_capacity)
    # No .as_goal()
)

# Soft goals for targets
target = (
    LXConstraint[Resource]("target")
    .expression(usage_expr)
    .eq()
    .rhs(lambda r: r.target_usage)
    .as_goal(priority=1, weight=1.0)
)

  2. Choose Appropriate Constraint Sense

    # Use GE for minimum requirements
min_production.ge().rhs(min_qty).as_goal(priority=1, weight=1.0)

# Use LE for maximum limits
max_overtime.le().rhs(max_hours).as_goal(priority=2, weight=1.0)

# Use EQ only when exact target is truly needed
exact_budget.eq().rhs(budget).as_goal(priority=1, weight=1.0)

  3. Understand Goal Semantics

    # Goal instances provide meaning
for goal in relaxed.goal_instances:
    # Can identify specific instances that deviated
    if goal.instance_id == "product_A":
        print(f"Product A target: {goal.target_value}")

  4. Check Relaxation Results

    # Verify relaxation created expected structure
relaxed = relax_constraint(constraint, metadata)

print(f"Original sense: {metadata.constraint_sense}")
print(f"Relaxed to EQ: {relaxed.constraint.sense == LXConstraintSense.EQ}")
print(f"Deviation variables: {relaxed.pos_deviation.name}, {relaxed.neg_deviation.name}")
print(f"Goal instances: {len(relaxed.goal_instances)}")

Next Steps