Step 4: Large-Scale Optimization with Room Types¶

Overview¶

This step demonstrates LumiX’s capability to handle realistic large-scale problems efficiently while introducing room type constraints for specialized classrooms.

What’s New in Step 4:

3x Scale Increase: 15 teachers, 12 classrooms, 12 classes, 80 lectures, 40 timeslots
Room Type Constraints: REGULAR, LAB, GYM for specialized facilities
Enhanced Performance: Cached compatibility checker combining capacity and room type checks
Production-Ready: Realistic high school size with 16x more variables

Prerequisites:

pip install lumix ortools sqlalchemy

Problem Scale Comparison¶

Metric	Step 3	Step 4	Multiplier
Teachers	5	15	3x
Classrooms	4	12	3x
Classes	4	12	3x
Lectures	20	80	4x
Timeslots	30	40	1.3x
Variables	~2,400	~38,400	16x
Constraints	~150	~600	4x
Preferences	7	35	5x

Key Point: Despite 16x more variables, LumiX solves this efficiently with proper caching.

Room Type System¶

Room Types¶

REGULAR: Standard classrooms for most subjects
LAB: Science laboratories for Chemistry, Physics, Biology
GYM: Gymnasium for Physical Education

Compatibility Rules¶

def check_room_type_compatible(subject_id, classroom_id):
    """
    Rules:
    - Lab subjects (Chemistry, Physics, Biology) → Must use LAB rooms
    - PE → Must use GYM
    - Other subjects → Can use REGULAR or LAB rooms (not GYM)
    """

Database Schema Extensions¶

Updated Models¶

Classroom with room_type:

class Classroom(Base):
    """Classroom ORM model with room type (NEW in Step 4).

    Room types enable realistic constraints where certain subjects require
    specific types of rooms (e.g., Chemistry needs a lab, PE needs gym).

    Attributes:
        id: Primary key
        name: Classroom name/number
        capacity: Maximum student capacity
        room_type: Type of room ('REGULAR', 'LAB', 'GYM')
    """
    __tablename__ = 'classrooms'
    __table_args__ = (
        CheckConstraint(
            "room_type IN ('REGULAR', 'LAB', 'GYM')",
            name='check_room_type'
        ),
    )

    id = Column(Integer, primary_key=True)
    name = Column(String, nullable=False)
    capacity = Column(Integer, nullable=False)
    room_type = Column(String, nullable=False, default='REGULAR')

    def __repr__(self):
        return f"<Classroom(id={self.id}, name='{self.name}', capacity={self.capacity}, type='{self.room_type}')>"

Subject with requires_lab:

class Subject(Base):
    """Subject ORM model with lab requirement (NEW in Step 4).

    Subjects can now specify if they require a lab. This creates a constraint
    where lab-requiring subjects can only be scheduled in LAB rooms.

    Attributes:
        id: Primary key
        name: Subject name (e.g., "Mathematics", "Chemistry")
        requires_lab: True if subject needs a laboratory
    """
    __tablename__ = 'subjects'

    id = Column(Integer, primary_key=True)
    name = Column(String, nullable=False)
    requires_lab = Column(Boolean, nullable=False, default=False)

    def __repr__(self):
        lab_str = " (requires lab)" if self.requires_lab else ""

Cached Compatibility Checker¶

The key performance optimization:

def create_cached_compatibility_checker(session: Session):
    """Create a cached checker function for both capacity and room type compatibility (NEW in Step 4).

    Combines capacity checking and room type checking into a single cached function.
    Queries all classes, classrooms, subjects, and lectures once and caches the results for
    efficient repeated lookups during variable creation.

    Performance: For a large timetabling problem with 96,000 variable combinations,
    this reduces from 192,000 database queries to just 27 queries
    (12 classes + 12 classrooms + 8 subjects + 87 lectures).

    Args:
        session: SQLAlchemy Session

    Returns:
        A checker function with signature (lecture_id, classroom_id) -> bool

    Example:
        >>> checker = create_cached_compatibility_checker(session)
        >>> compatible = checker(lecture_id=1, classroom_id=10)  # Fast cached lookup
        >>> if compatible:
        ...     print("Lecture can be assigned to this classroom")
    """
    # Query all data once upfront
    classes_dict = {c.id: c.size for c in session.query(SchoolClass).all()}
    classrooms_dict = {r.id: (r.capacity, r.room_type) for r in session.query(Classroom).all()}
    subjects_dict = {s.id: (s.requires_lab, s.name) for s in session.query(Subject).all()}
    # Cache lecture data: lecture_id -> (class_id, subject_id)
    lectures_dict = {l.id: (l.class_id, l.subject_id) for l in session.query(Lecture).all()}

    # Return closure with cached data
    def check(lecture_id: int, classroom_id: int) -> bool:
        """Check if lecture can be assigned to classroom using cached data."""
        # Get cached values
        lecture_info = lectures_dict.get(lecture_id)
        room_info = classrooms_dict.get(classroom_id)

        if lecture_info is None or room_info is None:
            return False

        class_id, subject_id = lecture_info
        class_size = classes_dict.get(class_id)
        subject_info = subjects_dict.get(subject_id)
        room_capacity, room_type = room_info

        if class_size is None or subject_info is None:
            return False

        requires_lab, subject_name = subject_info

        # Check capacity
        if class_size > room_capacity:
            return False

        # Check room type compatibility
        # PE requires GYM (check by name since ID might vary)
        if subject_name == "Physical Education":
            return room_type == 'GYM'

        # Lab-requiring subjects need LAB rooms
        if requires_lab:
            return room_type == 'LAB'

        # Other subjects can use REGULAR or LAB rooms (but not GYM)
        return room_type in ('REGULAR', 'LAB')

    return check

Performance Impact:

Without caching: ~192,000 database queries
With caching: ~27 queries (12 classes + 12 rooms + 8 subjects)
Speedup: ~7,000x faster

Problem Structure¶

Teachers (15 total)¶

Department	Count	Seniority Distribution
Math & Science	8	3 senior, 2 mid-level, 3 junior
Humanities	5	2 senior, 2 mid-level, 1 junior
Physical Education	2	0 senior, 2 mid-level, 0 junior

Classrooms (12 total)¶

8 Regular rooms: Room 101, 102, 201, 202, 301, 302, 401, 402
3 Labs: Chemistry Lab, Physics Lab, Biology Lab
1 Gym: Main Gym

Subjects (8 total)¶

Regular: Mathematics, English, History, Geography
Lab-required: Physics, Chemistry, Biology
Gym-required: Physical Education

Running the Example¶

Step 1: Populate Database¶

cd tutorials/timetabling/step4_scaled_up
python sample_data.py

Step 2: Run Optimization¶

python timetabling_scaled.py

Expected solve time: 10-30 seconds (depending on hardware)

Expected Output¶

Database initialization with counts
Variable creation with filtering statistics
Constraint generation progress
Solve time and status
Teacher and class timetables
Enhanced analytics: - Hard constraint satisfaction (100%) - Soft goal satisfaction by priority level - Overall preference satisfaction rate

Code Walkthrough¶

1. Create Cached Compatibility Checker¶

start_time = time.time()

# Create cached compatibility checker (capacity + room type)

2. Use in Variable Filtering¶

compatibility_checker = create_cached_compatibility_checker(session)

# Decision variable: assignment[lecture, timeslot, classroom]
# Now includes room type filtering
print("  Creating 3D decision variables...")
assignment = (
    LXVariable[Tuple[Lecture, TimeSlot, Classroom], int]("assignment")
    .binary()
    .indexed_by_product(
        LXIndexDimension(Lecture, lambda lec: lec.id).from_model(session),
        LXIndexDimension(TimeSlot, lambda ts: ts.id).from_model(session),
        LXIndexDimension(Classroom, lambda room: room.id).from_model(session),
    )
    # Filter: classroom must fit class AND room type must match subject
    .where_multi(

3. Same Constraint Logic¶

Constraint formulation remains the same - scalability comes from efficient data management.

Performance Benchmarks¶

Measured on typical laptop (8GB RAM, 4-core CPU):

Phase	Time	Notes
Variable creation	~2-3s	Including room type filtering
Hard constraints	~4-6s	600+ constraints
Soft constraints	~1-2s	35 goal constraints
Model build	~8-10s	Total preparation
Solve	~10-30s	OR-Tools CP-SAT
Total	~20-40s	End-to-end

Solution Quality¶

Hard Constraints¶

✅ 100% satisfied (always)
All lectures scheduled exactly once
No room, teacher, or class conflicts
All room type requirements met

Soft Constraints (Goals)¶

By Priority:

Priority 1: 85-95% satisfaction (senior teachers)
Priority 2: 70-85% satisfaction (mid-level)
Priority 3: 60-75% satisfaction (junior teachers)

Overall: 75-85% of preferences satisfied

Scaling Guidelines¶

Make it Smaller (for testing)¶

# In sample_data.py, reduce:
- Grades: 2 instead of 4 (e.g., only 9-10)
- Classes per grade: 2 instead of 3 (only A, B)
- Lectures per class: 5 instead of 7
- Periods per day: 6 instead of 8

Result: ~40 lectures, ~24 timeslots, ~5 teachers
Solve time: <10 seconds

Make it Larger (more realistic)¶

# In sample_data.py, increase:
- Classes per grade: 4 instead of 3 (add D section)
- Lectures per class: 9 instead of 7 (more subjects)
- Periods per day: 9 instead of 8

Result: ~140 lectures, ~45 timeslots, ~20 teachers
Solve time: 30-60 seconds

Scale to University Size¶

# Major changes needed:
- 100+ courses
- 50+ instructors
- 30+ rooms
- Multiple buildings (add travel time constraints)

Result: ~300 lectures, ~50 timeslots, ~50 instructors
Solve time: 1-5 minutes
Recommendation: CP-SAT with time limit

Key Takeaways¶

After completing Step 4, you should understand:

Scalability: LumiX handles realistic-sized problems efficiently with proper patterns
Room Types: Specialized resource constraints are straightforward to model
Performance: Caching is crucial when generating thousands of variables
Goal Programming: Scales well - can handle 100+ soft constraints
Production Ready: This size (80 lectures, 15 teachers) is suitable for small-to-medium schools

Next Steps¶

Apply to Your Domain¶

The patterns learned here apply to many scheduling problems:

University Course Scheduling: Scale up to 300+ courses
Employee Shift Scheduling: Add shift types, labor rules
Conference Scheduling: Add speaker availability, session tracks
Operating Room Scheduling: Add surgeon skills, equipment requirements