CHUK MCP Solver

🔧 General-purpose constraint and optimization solver as an MCP server

A powerful Model Context Protocol (MCP) server that provides constraint satisfaction and optimization capabilities to LLMs and AI agents. Built on Google OR-Tools CP-SAT solver, it enables sophisticated decision-making for scheduling, resource allocation, puzzles, and more.

Features

✨ General Constraint Solver

• Integer and boolean variables

• Linear constraints

• Global constraints (all_different, element, table)

• Implication constraints (conditional logic)

• Scheduling constraints (cumulative, no_overlap)

• Routing constraints (circuit)

• Inventory constraints (reservoir)

• Satisfaction and optimization modes

🎯 Wide Range of Use Cases

• Project scheduling and resource allocation

• Logic puzzles (Sudoku, etc.)

• Knapsack and packing problems

• Tool/model selection under constraints

• Configuration optimization

• Budget allocation

🚀 Production Ready

• Async/await native

• Type-safe with Pydantic models

• Comprehensive test coverage (>90%)

• Clean architecture with provider pattern

• Configurable via environment or YAML

📊 Rich Solutions

• Optimal and feasible solutions

• Multi-objective optimization (priority-based)

• Warm-start from previous solutions

• Parallel search workers

• Binding constraint analysis

• Human-readable explanations

• Metadata preservation

🤖 LLM-Optimized (Phase 2: Developer Experience)

• Pre-solve validation with actionable error messages

• Smart typo detection ("Did you mean...?" suggestions)

• Three-level validation severity (ERROR, WARNING, INFO)

• Structured observability and diagnostics

• Detailed infeasibility analysis

⚡ Performance & Power (Phase 3)

• Solution caching with problem hashing (LRU + TTL)

• Partial solutions (best-so-far on timeout)

• Search strategy hints (first-fail, random, etc.)

• Deterministic solving with random seeds

• Cache hit rate tracking

✅ Production Quality

• 246 comprehensive tests (all passing)

• 94% test coverage

• Type-safe with mypy

• Extensive error handling

🎯 High-Level Problem APIs (Phase 4: LLM-Native Schemas) 🆕

• Scheduling: Tasks with dependencies, resources, deadlines → optimal project schedules

• Routing: TSP/VRP with locations and vehicles → optimal delivery routes

  • ✨ Multi-vehicle VRP with capacity constraints (Phase 1 - NEW!)

  • Single-vehicle TSP, minimize distance/time/cost/vehicles objectives

  • Load timeline tracking, service times, vehicle-specific costs

• Budget Allocation: Items with costs, values, dependencies → optimal portfolio selection

• Assignment: Tasks with skills to agents with capacity → optimal task-agent matching

• Automatically builds CP-SAT models from high-level specs

• Domain-specific validation and error messages

• Rich responses with critical paths, utilization, route sequences, resource usage, assignments

Example Use Cases

High-Level Problem APIs (🆕 Phase 4)

📅 Project Manager: "Schedule 15 tasks with dependencies and resource constraints to finish ASAP"

• High-level API: solve_scheduling_problem(tasks, resources, objective="minimize_makespan")

• No need to understand CP-SAT variables or cumulative constraints

• Returns: optimal schedule with start/end times, critical path, resource utilization

• See: scheduling_demo.py

🚚 Delivery Driver: "Find the shortest route visiting 10 customers with 2 trucks, respecting vehicle capacity"

• High-level API: solve_routing_problem(locations, vehicles, objective="minimize_distance")

• ✨ Now supports multi-vehicle VRP with capacity constraints!

• No need to understand flow conservation, MTZ constraints, or subtour elimination

• Returns: optimal routes per vehicle, total distance, load timelines

• See: routing_demo.py and vrp_multi_vehicle_demo.py

💰 Product Manager: "Select projects to maximize ROI under $100k budget with dependencies and conflicts"

• High-level API: solve_budget_allocation(items, budgets, objective="maximize_value")

• No need to understand knapsack patterns or implication constraints

• Returns: selected items, total cost/value, resource usage, slack analysis

• See: allocation_demo.py

👥 Team Lead: "Assign development tasks to engineers matching required skills and balancing workload"

• High-level API: solve_assignment_problem(agents, tasks, objective="balance_load")

• No need to understand binary assignment variables or capacity constraints

• Returns: optimal assignments, agent workload, over/underutilized agents

• See: assignment_demo.py

Low-Level Constraint Programming

🏗️ DevOps Team: "Schedule 20 deployment tasks across 5 servers with CPU/memory limits while minimizing total deployment time"

• Uses cumulative constraints to manage resource capacity

• Optimizes makespan while respecting dependencies

• See: resource_scheduler.py

🚚 Logistics Company: "Plan delivery routes for 10 trucks visiting 50 customers to minimize total distance"

• Uses circuit constraints for vehicle routing (TSP/VRP)

• Handles time windows and capacity constraints

• See: delivery_router.py

📦 Warehouse Manager: "Schedule production runs and customer orders while maintaining safety stock of 500 units"

• Uses reservoir constraints to track inventory levels

• Prevents stockouts and overstock situations

• See: inventory_manager.py

☁️ Cloud Architect: "Select AWS instances to meet requirements while minimizing cost, then latency"

• Uses multi-objective optimization with priorities

• Balances competing objectives (cost vs performance)

• See: multi_objective_planner.py

🤖 AI Platform: "Route 100 user requests to GPT-4, GPT-3.5, or Claude to minimize cost under $50 budget"

• Uses implication constraints for conditional logic

• Selects optimal model for each task based on capabilities

• See: tool_selector.py

🎯 Project Manager: "Schedule 10 tasks with dependencies to minimize project completion time"

• Uses linear constraints for precedence relationships

• Optimizes critical path and resource allocation

• See: project_scheduler.py

🧩 Puzzle Solver: "Solve a Sudoku puzzle or find valid N-Queens placement"

• Uses all_different constraints for logic puzzles

• Demonstrates pure constraint satisfaction

• See: sudoku_solver.py

💼 Budget Planner: "Allocate $10,000 across 20 initiatives to maximize ROI under capacity constraints"

• Uses knapsack optimization for resource allocation

• Handles multiple constraints (budget, headcount, time)

• See: knapsack_optimizer.py

LLM/AI Agent Examples

"Claude, I need to schedule a team meeting with 5 people. Alice is only free Mon/Wed, Bob can't do mornings, and Carol must attend before David. Find a time that works."

• LLM extracts: 5 people, availability constraints, precedence constraint

• Solver finds: Valid meeting time satisfying all constraints

• Response: "Schedule meeting Wednesday 2-3pm: Alice, Bob, Carol attend first half; David joins after Carol confirms"

"Help me plan a road trip visiting San Francisco, LA, Vegas, and Phoenix in the shortest route starting from Seattle."

• LLM converts to: TSP problem with 5 cities

• Solver optimizes: Circuit constraint for minimum distance route

• Response: "Optimal route (1,247 miles): Seattle → SF (808mi) → LA (382mi) → Vegas (270mi) → Phoenix (297mi) → Seattle (1,440mi)"

"I have $500/month for AI API costs. I need to process 10,000 text requests and 2,000 image requests. What's the cheapest mix of GPT-4, GPT-3.5, and Claude?"

• LLM builds: Cost optimization problem with budget constraint

• Solver finds: Optimal model selection minimizing cost

• Response: "Use GPT-3.5 for 8,000 text ($40), Claude for 2,000 text ($30), GPT-4 for 2,000 images ($400). Total: $470/month"

"I'm deploying a microservice that needs 16 CPU cores and 32GB RAM. Minimize cost but keep latency under 50ms. What AWS instances should I use?"

• LLM creates: Multi-objective problem (cost priority 1, latency priority 2)

• Solver optimizes: Instance selection meeting requirements

• Response: "Deploy 4x c5.large instances (16 cores, 32GB total) at $340/month with 30ms latency"

"We have 3 devs, 2 designers, 1 PM. Schedule 15 tasks over 2 weeks where: Task A needs 2 devs for 3 days, Task B needs 1 designer + 1 dev for 2 days, all tasks have dependencies."

• LLM extracts: Resource requirements, durations, dependencies

• Solver schedules: Cumulative resource constraints + precedence

• Response: "Project completes in 12 days. Task A: Days 1-3 (Alice, Bob). Task B: Days 4-5 (Carol, David)..."

"I need to maintain 500 units of inventory. I have supplier deliveries on days 1, 7, 14 and customer orders on days 3, 5, 10, 15. When should I schedule each delivery to never run out?"

• LLM models: Reservoir constraint problem with stock levels

• Solver finds: Valid delivery schedule maintaining safety stock

• Response: "Schedule delivery 1 on day 0 (300 units), delivery 2 on day 6 (250 units), delivery 3 on day 12 (200 units). Stock never drops below 500."

"Find me a valid Sudoku solution for this puzzle..."

• LLM recognizes: Constraint satisfaction problem

• Solver finds: Valid solution using all_different constraints

• Response: Shows completed Sudoku grid

"I have 10 research papers to review. Each needs 2-4 hours. Some must be done before others. I have 20 hours this week. Create an optimal schedule."

• LLM extracts: Tasks, durations, precedence, time budget

• Solver optimizes: Maximize papers reviewed in 20 hours

• Response: "Can complete 7 papers in 20 hours: Paper A (2h, Mon 9-11am), Paper D (3h, Mon 11am-2pm)..."

Installation

⚡ Quick Start with uvx (Recommended)

No installation required! Use uvx to run directly:

Or install with uvx:

🌐 Public MCP Endpoint

Use our hosted solver directly - no installation needed:

• MCP Endpoint: https://solver.chukai.io/mcp

Perfect for testing, demos, or production use without infrastructure setup.

Install from PyPI

Local Development

Quick Start

As an MCP Server

Option 1: Public Hosted Endpoint (Easiest)

Use our hosted solver at solver.chukai.io - no installation required!

Add to your Claude Desktop config (~/Library/Application Support/Claude/claude_desktop_config.json on macOS):

Option 2: Local with uvx (Recommended)

Run locally using uvx for full control and privacy:

Option 3: Development Mode

For local development from source:

With Docker

Build and run using Docker:

The Docker container runs the MCP server in HTTP mode by default on port 8000. For stdio mode (local usage), run without arguments: python -m chuk_mcp_solver.server

Programmatic Usage

Examples

The examples/ directory contains 16 complete examples demonstrating different constraint types and use cases:

High-Level Problem APIs

Scheduling Demo (scheduling_demo.py) 🆕

• API: solve_scheduling_problem - High-level scheduling interface

• Use Case: Project scheduling, resource allocation, DevOps pipelines

• Features: Tasks with dependencies, resource constraints, deadlines, release times

Shows 6 scheduling scenarios:

1. Simple sequential project (build → test → deploy)

2. Parallel task execution

3. Resource-constrained scheduling with capacity limits

4. Deadlines and earliest start times

5. Infeasible problem detection

6. Complex DevOps pipeline with mixed constraints

Routing Demo (routing_demo.py) 🆕

• API: solve_routing_problem - High-level TSP/VRP interface

• Use Case: Delivery routing, traveling salesman, logistics optimization

• Features: Coordinates or distance matrix, service times, vehicle costs

Shows 6 routing scenarios:

1. Simple TSP with coordinates

2. TSP with asymmetric distance matrix

3. TSP with service times at locations

4. TSP with cost optimization (fixed + variable)

5. Real-world 7-location delivery route

6. Small 3-city TSP with detailed breakdown

Budget Allocation Demo (allocation_demo.py) 🆕

• API: solve_budget_allocation - High-level knapsack/portfolio interface

• Use Case: Project selection, feature prioritization, resource allocation

• Features: Dependencies, conflicts, multi-resource constraints, min/max thresholds

Shows 7 allocation scenarios:

1. Simple knapsack problem (maximize value under budget)

2. Portfolio selection with dependencies (backend required for frontend)

3. Feature prioritization with conflicts (mobile vs web checkout)

4. Multi-resource allocation (budget + headcount + time)

5. Maximize item count (get as many as possible)

6. Minimize cost while meeting value threshold

7. Item count constraints (min/max selection limits)

Assignment Demo (assignment_demo.py) 🆕

• API: solve_assignment_problem - High-level task-agent assignment interface

• Use Case: Work assignment, task delegation, resource matching

• Features: Skill matching, capacity constraints, load balancing, cost optimization

Shows 7 assignment scenarios:

1. Simple assignment (minimize cost with different hourly rates)

2. Skill matching (assign tasks requiring specific skills to qualified agents)

3. Load balancing (distribute tasks evenly across agents)

4. Capacity constraints (agents with limited task capacity)

5. Maximize assignments (assign as many tasks as possible)

6. Infeasible assignment (insufficient capacity)

7. Custom cost matrix (task-agent preference matching)

Performance & Features

Performance Metrics Demo (performance_metrics_demo.py) 🆕

• Features: Enhanced status codes, optimality gap, solve timing

• Use Case: Understanding solver performance and timeout behavior

Demonstrates the new v0.2.0+ performance metrics: optimality_gap, solve_time_ms, timeout_best, and timeout_no_solution status codes.

Logic & Constraint Satisfaction

Sudoku Solver (sudoku_solver.py)

• Constraints: all_different

• Use Case: Logic puzzles, constraint satisfaction

Solves a 4x4 Sudoku puzzle using all_different constraints for rows, columns, and boxes.

Optimization Problems

Knapsack Optimizer (knapsack_optimizer.py)

• Constraints: Linear (capacity), binary variables

• Use Case: Resource allocation, packing problems

Classic 0/1 knapsack problem: maximize value subject to weight capacity.

Project Scheduler (project_scheduler.py)

• Constraints: Linear (precedence), optimization

• Use Case: Task scheduling with dependencies

Minimizes project makespan with task precedence constraints.

Advanced Scheduling Constraints

Resource Scheduler (resource_scheduler.py) 🆕

• Constraints: Cumulative (resource capacity)

• Use Case: CPU/memory allocation, worker scheduling

Schedules tasks with resource demand under capacity limits. Shows resource utilization timeline.

Delivery Router (delivery_router.py) 🆕

• Constraints: Circuit (Hamiltonian path)

• Use Case: TSP, vehicle routing, delivery optimization

Finds optimal delivery route visiting all customers with minimum distance.

Inventory Manager (inventory_manager.py) 🆕

• Constraints: Reservoir (stock levels)

• Use Case: Production/consumption scheduling, inventory management

Manages inventory levels with production and consumption events, maintaining safety stock.

Multi-Objective & AI Orchestration

Multi-Objective Planner (multi_objective_planner.py) 🆕

• Constraints: Multi-objective optimization

• Use Case: Cloud deployment, trade-off analysis

Optimizes cloud deployment with multiple objectives: minimize cost (priority 1), minimize latency (priority 2).

Tool/Model Selection (tool_selector.py)

• Constraints: Implication (conditional logic)

• Use Case: MCP tool orchestration, model selection

Selects optimal AI models/tools for tasks under budget constraints using implication constraints.

Complex Real-World Examples 🔥

GPU Job Scheduler (gpu_job_scheduler.py) 🆕

• Constraints: Resource assignment, memory limits, job dependencies, deadlines, budget

• Use Case: ML/AI workload scheduling across heterogeneous GPUs

Schedules ML jobs (embedding generation, fine-tuning, inference) across different GPU types (A100, V100, T4) optimizing cost vs time with resource constraints.

Embedding Pipeline Scheduler (embedding_pipeline_scheduler.py) 🆕

• Constraints: Multi-stage pipeline, rate limits, throughput constraints

• Use Case: Document processing through embedding extraction pipeline

Orchestrates document batches through preprocessing → embedding → vector DB ingestion, selecting optimal providers (OpenAI, Cohere, Voyage) under rate limits.

ML Pipeline Orchestrator (ml_pipeline_orchestrator.py) 🆕

• Constraints: End-to-end pipeline, conditional deployment, quality gates

• Use Case: Multi-variant model training with A/B testing

Trains multiple model variants through full ML lifecycle (ingest → preprocess → train → eval → deploy), deploys only models meeting quality thresholds.

Example Output

Resource Scheduler Output:

Delivery Router Output:

Tool Reference

solve_constraint_model

Solve a general constraint or optimization model.

Parameters:

• mode (str): "satisfy" for any feasible solution, "optimize" for best solution

• variables (list): Decision variables with domains

• constraints (list): Constraints to satisfy

• objective (dict, optional): Objective function (required if mode is "optimize")

• search (dict, optional): Search configuration (time limits, etc.)

Variable Schema:

Constraint Types:

1. Linear: sum(coef * var) sense rhs

   { "id": "c1", "kind": "linear", "params": { "terms": [{"var": "x", "coef": 2}, {"var": "y", "coef": 3}], "sense": "<=", # "<=", ">=", or "==" "rhs": 10 } }

2. All Different: Variables must have distinct values

   { "id": "c2", "kind": "all_different", "params": {"vars": ["x", "y", "z"]} }

3. Element: Array indexing target = array[index]

   { "id": "c3", "kind": "element", "params": { "index_var": "idx", "array": [10, 20, 30], "target_var": "result" } }

4. Table: Allowed tuples

   { "id": "c4", "kind": "table", "params": { "vars": ["x", "y"], "allowed_tuples": [[0, 1], [1, 0]] } }

5. Implication: If-then constraint

   { "id": "c5", "kind": "implication", "params": { "if_var": "use_feature", "then": { "id": "cost", "kind": "linear", "params": {...} } } }

6. Cumulative: Resource scheduling with capacity

   { "id": "c6", "kind": "cumulative", "params": { "start_vars": ["s1", "s2", "s3"], "duration_vars": [3, 4, 2], # or variable IDs "demand_vars": [2, 1, 3], # or variable IDs "capacity": 5 } }

7. Circuit: Routing/Hamiltonian circuit

   { "id": "c7", "kind": "circuit", "params": { "arcs": [ (0, 1, "arc_0_1"), # (from_node, to_node, bool_var) (1, 2, "arc_1_2"), # ... ] } }

8. Reservoir: Inventory/stock management

   { "id": "c8", "kind": "reservoir", "params": { "time_vars": ["t1", "t2", "t3"], "level_changes": [5, -3, -2], # production/consumption "min_level": 0, "max_level": 10 } }

9. No-Overlap: Disjunctive scheduling

   { "id": "c9", "kind": "no_overlap", "params": { "start_vars": ["s1", "s2", "s3"], "duration_vars": [3, 4, 2] # or variable IDs } }

Multi-Objective Optimization:

Search Configuration:

Search Strategies:

• "auto" (default): Let solver choose best strategy

• "first_fail": Choose variables with smallest domain first

• "largest_first": Choose variables with largest domain first

• "random": Random variable selection

• "cheapest_first": Choose least expensive variables first

Solution Caching:

The solver automatically caches solutions using problem hashing to avoid re-solving identical problems. Enable/disable with enable_solution_caching (default: true).

Cache uses LRU eviction (max 1000 entries) with 1-hour TTL. Access global cache stats:

Partial Solutions on Timeout:

When solving complex problems with time limits, enable return_partial_solution to get the best solution found so far:

If timeout occurs, you'll get a FEASIBLE solution with a note explaining it's the best found so far.

Validation and Error Messages:

The solver validates models before solving and provides actionable error messages to help LLMs self-correct:

Validation checks:

• Undefined variables (with "did you mean?" suggestions)

• Duplicate IDs

• Invalid domain bounds

• Empty constraint sets

• Objective without variables

• Type mismatches

Response Schema:

Status Codes:

• optimal: Proven optimal solution found

• feasible: Valid solution found, but may not be optimal

• satisfied: All constraints satisfied (for satisfy mode)

• infeasible: No solution exists

• unbounded: Objective can be improved infinitely

• timeout_best: Timeout reached, returning best solution found so far

• timeout_no_solution: Timeout reached before finding any solution

• error: Solver error occurred

Performance Metrics:

• optimality_gap: Percentage gap from best bound (0.0 for optimal solutions)

• solve_time_ms: Actual wall-clock time spent solving

solve_scheduling_problem

🆕 High-Level Scheduling API - A simpler interface for task scheduling problems that automatically builds the CP-SAT model for you.

Use this instead of solve_constraint_model when you have tasks with durations, dependencies, and resource constraints. Perfect for project planning, job scheduling, and resource allocation.

Parameters:

• tasks (list): Tasks to schedule, each with:

  • id (str): Unique task identifier

  • duration (int): Task duration in time units

  • resources_required (dict, optional): {resource_id: amount} mapping

  • dependencies (list, optional): Task IDs that must complete first

  • earliest_start (int, optional): Release time (can't start before this)

  • deadline (int, optional): Due date (must finish by this)

  • priority (int, optional): Task priority (default 1)

  • metadata (dict, optional): Custom metadata preserved in response

• resources (list, optional): Resources with capacity limits:

  • id (str): Resource identifier

  • capacity (int): Maximum units available at any time

  • cost_per_unit (float, optional): Cost per unit-time

  • metadata (dict, optional): Custom metadata

• objective (str): Optimization goal

  • "minimize_makespan" (default): Minimize total project duration

  • "minimize_cost": Minimize total resource cost

  • "minimize_lateness": Minimize lateness/tardiness

• max_time_ms (int, optional): Maximum solver time in milliseconds (default: 60000)

Response:

Example: Simple Project Schedule

Example: Resource-Constrained Scheduling

Example: Deadlines and Release Times

When to Use This vs. solve_constraint_model:

✅ Use solve_scheduling_problem when:

• You have tasks with durations and dependencies

• You need to manage resource capacities

• You want to minimize makespan/cost/lateness

• You want a simpler, domain-specific API

🔧 Use solve_constraint_model when:

• You need custom constraints beyond scheduling

• You're solving non-scheduling problems (puzzles, knapsack, etc.)

• You need fine-grained control over the model

• You're combining scheduling with other constraint types

Behind the Scenes:

This tool automatically converts your high-level scheduling problem into a CP-SAT model with:

• Start/end time variables for each task

• Duration constraints: end = start + duration

• Precedence constraints for dependencies

• Cumulative constraints for resource capacity

• Deadline constraints

• Makespan variable and objective

See scheduling_demo.py for comprehensive examples.

solve_routing_problem

🆕 High-Level Routing API - A simpler interface for TSP and VRP problems that automatically builds the CP-SAT model for you.

Use this instead of solve_constraint_model when you need to find optimal routes for vehicles visiting locations. Perfect for delivery routing, traveling salesman problems, and logistics optimization.

Parameters:

• locations (list): Locations to visit, each with:

  • id (str): Unique location identifier

  • coordinates (tuple, optional): (x, y) or (lat, lon) coordinates

  • service_time (int, optional): Time spent at location (default 0)

  • time_window (tuple, optional): (earliest, latest) arrival time

  • demand (int, optional): Demand at location for capacity constraints

  • priority (int, optional): Location priority (default 1)

• vehicles (list, optional): Vehicles (if empty, assumes single vehicle TSP):

  • id (str): Vehicle identifier

  • capacity (int, optional): Maximum load (default 999999)

  • start_location (str): Starting location ID

  • end_location (str, optional): Ending location if different from start

  • max_distance (int, optional): Maximum distance vehicle can travel

  • max_time (int, optional): Maximum time vehicle can be in use

  • cost_per_distance (float, optional): Cost per unit distance (default 1.0)

  • fixed_cost (float, optional): Fixed cost if vehicle is used (default 0.0)

• distance_matrix (list[list[int]], optional): Distance matrix where [i][j] = distance from location i to j. If not provided, uses Euclidean distance from coordinates.

• objective (str): Optimization goal

  • "minimize_distance" (default): Minimize total distance

  • "minimize_time": Minimize total time

  • "minimize_vehicles": Use fewest vehicles

  • "minimize_cost": Minimize total cost

• max_time_ms (int, optional): Maximum solver time in milliseconds (default: 60000)

Response:

Example: Simple TSP with Coordinates

Example: TSP with Distance Matrix

Example: Routing with Service Times and Costs

When to Use This vs. solve_constraint_model:

✅ Use solve_routing_problem when:

• You need to find optimal routes for visiting locations

• You have TSP (Traveling Salesman Problem) scenarios

• You want to optimize delivery routes

• You want a simpler, domain-specific API

🔧 Use solve_constraint_model when:

• You need custom constraints beyond routing

• You're solving non-routing problems

• You need fine-grained control over the circuit constraint

• You're combining routing with other constraint types

Behind the Scenes:

This tool automatically converts your high-level routing problem into a CP-SAT model with:

• Boolean arc variables for each possible location-to-location connection

• Multi-vehicle support with flow conservation and MTZ subtour elimination ✨ NEW

• Capacity constraints for vehicle load limits ✨ NEW

• Circuit constraint for single-vehicle TSP (Hamiltonian tour)

• Distance/time/cost/vehicles objective functions

• Support for service times at locations

• Vehicle cost modeling (fixed + per-distance)

• Load timeline tracking for capacity-constrained routing ✨ NEW

Supported Features:

✅ Single-vehicle TSP (Traveling Salesman Problem) ✅ Multi-vehicle VRP (Vehicle Routing Problem) with capacity constraints ✨ NEW (Phase 1) ✅ Multiple optimization objectives: minimize_distance, minimize_time, minimize_cost, minimize_vehicles ✅ Service times at locations ✅ Vehicle-specific costs (fixed + per-distance) ✅ Demand/capacity constraints

Current Limitations:

• No time window constraints yet

• No pickup and delivery yet

• No heterogeneous fleets (different vehicle types with different capabilities)

See routing_demo.py for comprehensive examples.

solve_budget_allocation 🆕

High-level interface for budget allocation and knapsack problems.

Solves portfolio selection, feature prioritization, and resource allocation problems. Automatically handles dependencies, conflicts, and multiple resource constraints.

Parameters:

• items (list[dict]): Items to choose from, each with:

  • id (str): Unique identifier

  • cost (float): Cost of selecting this item

  • value (float): Value/benefit (ROI, utility, priority)

  • resources_required (dict, optional): Multi-resource requirements like {"headcount": 2, "time": 3}

  • dependencies (list, optional): Item IDs that must also be selected

  • conflicts (list, optional): Item IDs that cannot be selected together

• budgets (list[dict]): Resource constraints, each with:

  • resource (str): Resource name (e.g., "money", "time", "headcount")

  • limit (float): Maximum available

• objective (str): Goal - "maximize_value" (default), "maximize_count", or "minimize_cost"

• min_value_threshold (float, optional): Minimum total value required

• max_cost_threshold (float, optional): Maximum total cost allowed

• min_items (int, optional): Minimum number of items to select

• max_items (int, optional): Maximum number of items to select

• max_time_ms (int): Maximum solver time (default: 60000)

Response:

Example 1: Simple Knapsack

Example 2: With Dependencies

Example 3: With Conflicts

Example 4: Multi-Resource

When to Use:

✅ Use solve_budget_allocation when:

• You need to select items under budget constraints

• You have knapsack or portfolio selection problems

• You need to handle dependencies or conflicts between items

• You have multiple resource constraints (budget, time, headcount)

• You want to maximize value, minimize cost, or maximize count

🔧 Use solve_constraint_model when:

• You need custom constraints beyond allocation

• You're solving non-allocation problems

• You need fine-grained control over the knapsack formulation

• You're combining allocation with other constraint types

Behind the Scenes:

This tool automatically converts your high-level allocation problem into a CP-SAT model with:

• Binary selection variables for each item

• Linear budget constraints for each resource

• Implication constraints for dependencies (if A then B)

• Linear constraints for conflicts (A + B ≤ 1)

• Value/cost/count objective function

• Optional min/max value, cost, and item count constraints

Current Limitations:

• No soft budget constraints (penalty-based) yet

• No category-based selection rules yet

• No multi-period allocation yet

See allocation_demo.py for comprehensive examples.

solve_assignment_problem 🆕

High-level task-to-agent assignment interface - Automatically builds CP-SAT models for assigning tasks to agents with skill matching, capacity constraints, and load balancing.

Example 1: Simple Assignment (Minimize Cost)

Example 2: Skill Matching

Example 3: Load Balancing

Example 4: Maximize Assignments (Optional Tasks)

When to Use:

✅ Use solve_assignment_problem when:

• You need to assign tasks to agents/workers/servers

• You have skill or qualification requirements

• You need to respect capacity or workload limits

• You want to minimize cost, maximize assignments, or balance load

• You have custom task-agent costs or preferences

🔧 Use solve_constraint_model when:

• You need custom constraints beyond assignment

• You're solving non-assignment problems

• You need fine-grained control over the assignment formulation

• You're combining assignment with other constraint types

Behind the Scenes:

This tool automatically converts your high-level assignment problem into a CP-SAT model with:

• Binary assignment variables for each (task, agent) pair

• Task assignment constraints (each task to exactly one agent, or at most one if optional)

• Agent capacity constraints (max number of tasks per agent)

• Skill matching constraints (forbid incompatible assignments)

• Cost minimization, assignment maximization, or load balancing objective

• Automatic cost matrix generation from agent cost_multiplier and task duration

Response Fields:

Current Limitations:

• No multi-skill level support (e.g., junior vs senior) yet

• No task priority or preemption yet

• No time windows or deadlines yet

• No agent preferences or task affinity yet

See assignment_demo.py for comprehensive examples.

Configuration

Environment Variables

YAML Configuration

Create ~/.config/chuk-mcp-solver/config.yaml:

Development

Setup

Testing

Code Quality

Running Locally

Architecture

Key Design Patterns:

• Modular Architecture: Focused modules with single responsibilities

• Solver Pattern: Pluggable solver backends via abstract interface

• Factory Function: Simple get_solver() for solver instantiation

• Pydantic Models: Type-safe throughout

• Async Native: Non-blocking I/O

• No Magic Strings: Enums for all constants

• Mirrored Test Structure: Tests match source organization

Use Cases

Scheduling & Resource Allocation

• Project Scheduling: Task scheduling with precedence constraints → project_scheduler.py

• Resource-Constrained Scheduling: CPU/memory/worker allocation with capacity limits → resource_scheduler.py

• Inventory Management: Production/consumption planning with stock levels → inventory_manager.py

• Shift Rostering: Employee scheduling with availability and skill constraints

• Meeting Scheduling: Calendar optimization with participant constraints

Routing & Logistics

• Vehicle Routing: Delivery route optimization (TSP/VRP) → delivery_router.py

• Circuit Planning: Hamiltonian path/circuit problems

• Network Design: Optimal path selection in graphs

• Warehouse Optimization: Pick path optimization

Optimization Problems

• Knapsack Problems: Resource allocation under weight/capacity limits → knapsack_optimizer.py

• Budget Allocation: Optimal spending across categories

• Portfolio Selection: Asset selection under risk/return constraints

• Packing Problems: Bin packing, cutting stock

AI/LLM Orchestration

• Multi-Model Selection: Choose optimal AI models under budget → tool_selector.py

• Multi-Objective Planning: Balance cost, latency, quality trade-offs → multi_objective_planner.py

• Rate-Limit Aware Scheduling: Task scheduling respecting API limits

• Capability-Based Routing: Route requests to appropriate models

• Cost-Latency Optimization: Minimize cost while meeting SLAs

Configuration & Selection

• System Configuration: Parameter optimization under constraints

• Feature Selection: Optimal feature subset selection

• Bundle Recommendations: Best product/service combinations

• Resource Sizing: Cloud instance selection and sizing

Logic Puzzles

• Sudoku: Constraint satisfaction puzzles → sudoku_solver.py

• Kakuro, KenKen: Arithmetic constraint puzzles

• Logic Grids: Deductive reasoning puzzles

• N-Queens: Placement problems

Roadmap

Phase 1: Trust & Foundations ✅ (Completed)

• Structured observability and logging

• Health checks and diagnostics

• Problem hashing for deduplication

• Infeasibility diagnosis

• Deterministic solving (random seeds)

• Solution metadata tracking

Phase 2: Developer Experience ✅ (Completed)

• Pre-solve model validation

• Actionable error messages for LLMs

• Smart typo detection ("Did you mean...?")

• Three-level validation severity (ERROR, WARNING, INFO)

• Detailed validation suggestions

Phase 3: Power & Performance ✅ (Completed)

• Solution caching with LRU + TTL

• Partial solutions (best-so-far on timeout)

• Search strategy hints (first-fail, random, etc.)

• Cache statistics and hit rate tracking

• Warm-start solution hints

Phase 1-3 Foundation Features ✅

• Cumulative constraints (resource scheduling)

• Circuit constraints (routing/TSP)

• Reservoir constraints (inventory management)

• No-overlap constraints (disjunctive scheduling)

• Multi-objective optimization (priority-based)

• Parallel search workers

• Search progress logging

Phase 4: LLM-Native Problem Schemas 🚧 (In Progress)

Completed:

• High-level scheduling API (solve_scheduling_problem)

• Task model with dependencies, resources, deadlines

• Resource model with capacity constraints

• Automatic CP-SAT model generation from high-level specs

• Rich scheduling responses (makespan, critical path, utilization)

• Scheduling examples and documentation

• High-level routing API (TSP/VRP) ✨ NEW

• Multi-vehicle VRP with capacity constraints ✨ NEW (Phase 4.1)

• MTZ subtour elimination for VRP ✨ NEW

• Multiple optimization objectives (distance, time, cost, vehicles) ✨ NEW

• Load timeline tracking ✨ NEW

• VRP examples and documentation ✨ NEW

• High-level budget allocation API

• High-level assignment API

In Progress:

• Time window constraints for VRP

• Pickup and delivery for VRP

• Heterogeneous fleet support

Phase 5-7: Planned 🔮

• Solution enumeration (find N diverse solutions)

• Solution visualization (Gantt charts, graphs)

• Enhanced debugging (conflict analysis)

• Export to MPS/LP formats

• Advanced search strategies (custom heuristics)

• Symmetry breaking

• Decomposition strategies

• Documentation generation from models

Contributing

Contributions welcome! Please:

1. Fork the repository

2. Create a feature branch

3. Add tests for new functionality

4. Ensure make check passes

5. Submit a pull request

License

MIT License - see LICENSE for details.

Support

• 📖 Documentation

• 🐛 Issue Tracker

• 💬 Discussions

Acknowledgments

Built with:

• Google OR-Tools - CP-SAT solver

• Pydantic - Data validation

• chuk-mcp-server - MCP framework

Made with ❤️ by CHUK AI