← Back to Projects
Constraint SatisfactionOptimizationAlgorithmsPython

AI Scheduling with Hard Constraints

Constraint satisfaction system for scheduling with hard constraints using backtracking and constraint propagation.

Overview

A scheduling system that finds feasible solutions under hard constraints (time conflicts, resource limits, dependencies). Uses constraint propagation and backtracking search with heuristics.

Solves real-world scheduling problems where constraints cannot be violated. Demonstrates handling of NP-hard problems with practical heuristics and optimization techniques.

Your Role

What I Built

  • Constraint satisfaction problem (CSP) formulation
  • Backtracking search with constraint propagation
  • Variable and value ordering heuristics
  • Conflict-directed backjumping optimization

What I Owned End-to-End

  • Problem modeling and constraint definition
  • Algorithm selection and tuning
  • Performance optimization for large problem instances
  • Solution validation and correctness guarantees

Technical Highlights

Architecture Decisions

  • CSP representation with variables, domains, constraints
  • Arc consistency propagation (AC-3 algorithm)
  • Forward checking during search
  • Conflict set tracking for intelligent backtracking

Algorithms / Protocols / Constraints

  • Backtracking search with chronological backtracking
  • Minimum remaining values (MRV) heuristic
  • Least constraining value (LCV) heuristic
  • Conflict-directed backjumping

Optimization Strategies

  • Early constraint propagation to prune search space
  • Memoization of constraint checks
  • Incremental constraint checking

Tech Stack

PythonNumPyNetworkXFastAPI

Results / Learnings

What Worked

  • Solved scheduling problems with 100+ variables and 500+ constraints
  • Found solutions 10x faster than naive backtracking
  • Guaranteed constraint satisfaction (no violations)

What I Learned

  • Heuristic selection dramatically impacts search efficiency
  • Constraint propagation is crucial for large problems
  • Problem modeling significantly affects solver performance

Tradeoffs Considered

  • Chose completeness over speed (guaranteed solution if exists)
  • Accepted exponential worst-case for guaranteed correctness
  • Prioritized constraint satisfaction over optimality