DOCSEARCHbyAlgolia
Submit Docs

OptaPlanner Documentation

repository·main·Indexed 19 days ago

https://github.com/kiegroup/optaplanner

An open-source AI constraint solver built on Java for solving complex optimization problems. This documentation covers the use of optaplanner-benchmark for executing benchmarks via CLI or programmatically, configuring solver benchmarks using XML, implementing custom SolutionFileIO for JSON, XML, or binary formats, and managing benchmark warm-up, parallel execution, and solver ranking reports.

Tokens
77.6K
Snippets
185
Records
286
Agent score
67%

What's inside OptaPlanner

  2. OptaPlanner Project Overview

    main

    OptaPlanner is a fast, easy-to-use, open source AI constraint solver for software developers.

    Key Specifications:

    • Project Key: org.optaplanner:optaplanner
    • JVM Support: Java 11 and Java 17
    • Build Tool: Maven 3.x
    • License: Apache License 2.0

  3. Hospital bed planning (PAS) use case

    main

    The Hospital Bed Planning (Patient Admission Scheduling - PAS) use case involves assigning patients to specific hospital beds for every night of their stay.

    Key Entities:

    • Patient: Has fixed arrival and departure dates.
    • Bed: The assignment target for each night of a patient's stay.
    • Room: Contains beds.
    • Department: Contains rooms.

    This use case is designed to demonstrate handling overconstrained datasets, where it may not be possible to satisfy all hard constraints simultaneously.

  4. Meeting scheduling use case overview

    main

    The Meeting Scheduling use case involves assigning each meeting to a specific starting time and a room. Meetings vary in duration, and the goal is to optimize the schedule based on a hierarchy of constraints.

    Constraint Hierarchy

    Hard Constraints (Must be satisfied)

    • Room conflict: Two meetings cannot use the same room at the same time.
    • Required attendance: A person cannot be assigned to two required meetings simultaneously.
    • Required room capacity: A meeting must be assigned to a room that can accommodate all its attendees.
    • Start and end on same day: Meetings must not be scheduled across multiple days.

    Medium Constraints

    • Preferred attendance: A person cannot have two preferred meetings at the same time, nor a combination of a preferred and a required meeting at the same time.

    Soft Constraints (Optimization goals)

    • Sooner rather than later: Schedule all meetings as early as possible.
    • A break between meetings: Aim for at least one time grain break between any two meetings.
    • Overlapping meetings: Minimize the number of parallel meetings to reduce attendee choice conflicts.
    • Assign larger rooms first: Assign meetings to larger rooms when available to accommodate potential extra attendees.
    • Room stability: If a person has two consecutive meetings with a break of two or less time grains, they should ideally be in the same room.

  5. Understand the Conference Scheduling use case

    main

    The Conference Scheduling example demonstrates how to assign conference talks to specific timeslots and rooms. This use case is designed to handle complex scheduling requirements involving overlapping timeslots and various constraints. The problem data can be managed via *.xlsx files, which are compatible with LibreOffice or Excel.

    Key aspects of this use case include:

    • Goal: Assign each talk to a valid timeslot and room.
    • Complexity: Scales from small problems (18 talks) to large-scale problems (216 talks, 18 timeslots, 20 rooms) with search spaces reaching $10^{552}$.
    • Data Input: Uses Excel-compatible files for easy editing of input data.

  6. Understand the Exam Timetabling use case

    main

    The Exam Timetabling use case (based on ITC 2007 track 1) involves scheduling exams into specific periods and rooms. The goal is to satisfy hard constraints (mandatory requirements) while optimizing soft constraints (preferences).

    Hard Constraints (Mandatory)

    • Exam conflict: Exams sharing students must not occur in the same period.
    • Room capacity: Room seating capacity must be respected.
    • Period duration: The period must be long enough for all assigned exams.
    • Period-specific constraints: Coincidence (exams in same period), Exclusion (exams in different periods), and After (sequential ordering).
    • Room-specific constraints: Exclusive (exam should not share a room).

    Soft Constraints (Optimizable)

    • Student comfort: Avoid consecutive exams or multiple exams on the same day for the same student.
    • Scheduling quality: Period spread (spacing exams for students), mixed durations (avoiding different durations in the same room), and front-loading (scheduling large exams earlier).
    • Resource penalties: Penalties for using specific periods or rooms.

  7. What is a shadow variable?

    main

    A shadow variable is a planning variable whose value is automatically deduced from the state of genuine planning variables.

    While shadow variables violate normalization, they are useful for expressing constraints naturally (e.g., calculating arrival times in vehicle routing based on previous stops).

    Key Rules:

    • Optimization: OptaPlanner optimizes genuine variables; shadow variables are updated automatically to maintain consistency.
    • Entity Requirement: Any class containing at least one shadow variable must be annotated with @PlanningEntity and registered in the solver configuration, even if it has no genuine planning variables.
    • Shadow Planning Entity: A class with no genuine planning variables but at least one shadow variable is called a 'shadow planning entity'.

  8. What is a Move and a MoveSelector?

    main

    In OptaPlanner, a Move represents a change (or set of changes) that transitions a solution from state A to state B. A neighbor solution is any solution reachable via a single Move.

    A MoveSelector is responsible for creating an Iterator<Move> that an optimization algorithm can use to explore the neighborhood of the current solution.

    Key Constraints:

    • A Move can affect multiple entities, create entities, or delete entities.
    • A Move must not change the problem facts.

  9. Overview of Construction Heuristics

    main

    A construction heuristic is used to build a reasonably good initial solution within a finite amount of time. While the resulting solution might not always be feasible, it provides a fast starting point for metaheuristics to refine.

    Construction heuristics terminate automatically, so you typically do not need to configure a specific Termination for this phase.

  11. What is Partitioned Search and when to use it

    main

    Partitioned Search is a multithreaded optimization algorithm designed for large datasets (typically above 5,000 planning entities). It partitions the problem into smaller pieces and solves them separately, providing a performance boost on multi-core machines through higher CPU utilization and faster initial solution discovery.

    Key Considerations:

    • Suboptimal Results: Partitioning trades short-term solution quality for long-term speed. To compensate, it is recommended to run a non-partitioned Local Search phase after the Partitioned Search phase.
    • Constraint Requirements: Partitioning only works if planning entities and value ranges can be split into $n$ partitions without any constraints crossing the boundaries between partitions.

  12. Overview of optimization algorithm families

    main

    OptaPlanner supports three main families of algorithms:

    1. Exhaustive Search (ES): Checks every possible solution (e.g., Brute Force, Branch and Bound). Not scalable for real-world problems.
    2. Construction Heuristics (CH): Builds a solution from scratch (e.g., First Fit, Cheapest Insertion). These are fast and scalable but usually produce sub-optimal results. They are typically used to initialize a solution for metaheuristics.
    3. Metaheuristics (MH): Improves an existing solution (e.g., Tabu Search, Simulated Annealing). These are the recommended choice for real-world problems and are highly scalable and tweakable.