Constraint satisfaction solver

Constraint Satisfaction Solver

Overview

The Constraint Satisfaction Solver skill provides capabilities for solving constraint satisfaction problems (CSPs) and constraint optimization problems (COPs). It excels at scheduling, configuration, assignment, and combinatorial problems where finding feasible solutions is as important as optimization.

Capabilities

• Variable and domain definition
• Constraint specification (global constraints)
• Solution search strategies
• Optimization with constraints
• Scheduling constraint handling
• Configuration problem solving
• All-solutions enumeration
• Constraint propagation explanation

Used By Processes

• Prescriptive Analytics and Optimization
• Resource Scheduling
• Operational Decisions

Usage

Problem Definition

# 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

Constraint	Description	Example Use
AllDifferent	All variables take distinct values	Sudoku, assignment
Cumulative	Resource usage over time	Scheduling
Circuit	Variables form a Hamiltonian circuit	TSP, routing
Table	Allowed/forbidden combinations	Configuration
Regular	Sequence matches automaton	Shift patterns
Cardinality	Count of value occurrences	Workload balance

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

Strategy	Description	Best For
First Fail	Choose variable with smallest domain	General CSPs
Min Domain	Same as first fail	General CSPs
Impact	Choose by constraint propagation impact	Large problems
Activity	Choose frequently changed variables	Restart searches
Random	Random variable/value selection	Diversification

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