Constraint Satisfaction Solver

# Define CSP
csp_problem = {
    "name": "Employee Scheduling",
    "variables": {
        "shift_mon_morning": {"domain": ["Alice", "Bob", "Carol", "David"]},
        "shift_mon_afternoon": {"domain": ["Alice", "Bob", "Carol", "David"]},
        "shift_tue_morning": {"domain": ["Alice", "Bob", "Carol", "David"]},
        "shift_tue_afternoon": {"domain": ["Alice", "Bob", "Carol", "David"]},
        # ... more shifts
    },
    "constraints": [
        {
            "type": "all_different",
            "scope": ["shift_mon_morning", "shift_mon_afternoon"],
            "description": "Different employees on same day"
        },
        {
            "type": "not_equal",
            "variables": ["shift_mon_afternoon", "shift_tue_morning"],
            "condition": "employee",
            "description": "No back-to-back closing/opening"
        },
        {
            "type": "count",
            "variable": "Alice",
            "min": 3,
            "max": 5,
            "description": "Alice works 3-5 shifts per week"
        }
    ]
}

Scheduling Constraints

# Job shop scheduling
scheduling_problem = {
    "jobs": [
        {
            "id": "Job1",
            "tasks": [
                {"id": "J1_T1", "machine": "M1", "duration": 3},
                {"id": "J1_T2", "machine": "M2", "duration": 2, "after": "J1_T1"}
            ]
        },
        {
            "id": "Job2",
            "tasks": [
                {"id": "J2_T1", "machine": "M2", "duration": 2},
                {"id": "J2_T2", "machine": "M1", "duration": 3, "after": "J2_T1"}
            ]
        }
    ],
    "constraints": {
        "no_overlap": "tasks on same machine cannot overlap",
        "precedence": "tasks must respect ordering within job",
        "deadline": {"Job1": 10, "Job2": 8}
    },
    "objective": "minimize_makespan"  # or "minimize_tardiness"
}

Configuration Problem

# Product configuration
config_problem = {
    "components": {
        "engine": {"options": ["V6", "V8", "Electric"]},
        "transmission": {"options": ["Manual", "Automatic", "CVT"]},
        "wheel_size": {"options": [17, 18, 19, 20]},
        "color": {"options": ["Red", "Blue", "Black", "White"]}
    },
    "constraints": [
        {
            "type": "implication",
            "if": {"engine": "Electric"},
            "then": {"transmission": ["Automatic", "CVT"]},
            "description": "Electric engines don't support manual transmission"
        },
        {
            "type": "incompatible",
            "values": [{"engine": "V6"}, {"wheel_size": 20}],
            "description": "V6 not available with 20-inch wheels"
        }
    ]
}

Global Constraints

Input Schema

{
  "problem_type": "csp|cop|scheduling|configuration",
  "variables": {
    "var_name": {
      "domain": "array or range",
      "type": "integer|boolean|set"
    }
  },
  "constraints": [
    {
      "type": "string",
      "scope": ["string"],
      "parameters": "object"
    }
  ],
  "objective": {
    "type": "minimize|maximize",
    "expression": "string"
  },
  "search_config": {
    "strategy": "default|first_fail|min_domain",
    "time_limit": "number",
    "all_solutions": "boolean",
    "max_solutions": "number"
  }
}

Output Schema

{
  "status": "Satisfied|Optimal|Infeasible|Unknown",
  "solution": {
    "variable_name": "value"
  },
  "objective_value": "number (if COP)",
  "all_solutions": [
    {"variable_name": "value"}
  ],
  "statistics": {
    "nodes_explored": "number",
    "propagations": "number",
    "backtracks": "number",
    "solve_time": "number"
  },
  "explanation": {
    "unsatisfied_constraints": ["string"],
    "conflict_set": ["string"]
  }
}

Search Strategies

Best Practices

1. Define tight domains to reduce search space
2. Use appropriate global constraints (more efficient than decomposed)
3. Add redundant constraints to improve propagation
4. Consider symmetry breaking constraints
5. Use restarts for large, hard problems
6. Profile to identify propagation bottlenecks
7. Validate solutions against business requirements

Integration Points

• Connects with Linear Programming Solver for hybrid approaches
• Feeds into Optimization Specialist agent
• Supports Scheduling and Assignment processes
• Integrates with Decision Visualization for Gantt charts