What is Constraint Solving? From a specific need to a full thesis
It all started with a very specific problem: a university partnering with Bitlogic sought a streamlined and efficient way to schedule exam sessions. The task wasn’t simple: it required coordinating classrooms, professors, courses, degrees, and timetables, all under a set of restrictions that had to be satisfied simultaneously.
This type of challenge isn’t exclusive to academia. In any organization, allocating limited resources while respecting specific conditions can quickly become a headache. From work shifts to delivery routes, complexity grows exponentially as more variables and rules are added.
Faced with this scenario, Edgardo Hames, co-founder of Bitlogic, suggested that I investigate a tool called OptaPlanner to see whether it could be applied directly to the university’s problem. Eventually, the research grew, and what started as an applied exploration turned into a broader benchmark: a comparative analysis of different Constraint Solving technologies and frameworks.
What is Constraint Solving?
It’s a programming paradigm that consists of modeling a problem as a set of constraints that must be satisfied simultaneously. Unlike traditional programming approaches—where we usually define a sequence of steps to reach a solution—here we describe the problem and the conditions that limit its possible solutions. The algorithm’s job is to find a combination of assignments that meets those conditions.
These constraints are usually divided into two types:
- Hard constraints: unbreakable. If violated, the solution is simply invalid.
- Soft constraints: desirable but not mandatory. They can be relaxed if needed, though each violation adds a “cost” the algorithm tries to minimize.
Simple example: imagine we need to schedule university exams.
- A hard constraint could be: “Two exams from the same degree program cannot be scheduled at the same time.”
- Another hard constraint: “A classroom cannot be assigned to two exams simultaneously.”
- A soft constraint: “Try not to schedule exams for a professor on consecutive days” or “Avoid having students take more than two exams on the same day.”
If we only consider hard constraints, any solution that satisfies them would technically be valid. But by also including soft constraints, we aim for not just feasible solutions but optimal ones: solutions that minimize conflicts and maximize comfort for both professors and students.
Applications beyond academia
The same applies across many other domains:
- Logistics: a truck must visit all cities (hard), but fuel consumption or travel time should be minimized (soft).
- Shift scheduling: a doctor cannot be on two shifts at once (hard), but working hours should be distributed fairly (soft).
The real power of Constraint Solving lies in transforming highly complex problems into declarative models that an algorithm can process. The challenge is designing the model precisely and selecting the right algorithm and tool to find solutions in a search space so large it would be impossible to navigate manually or with naive methods.
In practice, this means finding optimal or near-optimal solutions to problems where the number of possible combinations is unmanageable for traditional approaches. These problems are often NP-hard, meaning that even small instances cause the search space to grow exponentially.
Algorithms in the thesis
To tackle this complexity, my thesis focused on Local Search algorithms and some of its most common variants:
- Hill Climbing: progressively improves the current solution by evaluating its closest neighbors.
- Tabu Search: prevents cycles or poor local optima by keeping a “tabu list” of already explored states.
- Simulated Annealing: inspired by metallurgy processes, it allows worse solutions to be accepted with some probability early in the search, then gradually refines toward global convergence.
These methods don’t always guarantee the perfect solution but deliver high-quality results in reasonable times—crucial when dealing with real-world planning, logistics, or resource allocation.
Frameworks tested
Within this framework, I selected three widely used open-source Java frameworks to bring the research into practice:
I tested them against different representative case studies:
- N-Queens: a classic of computational theory. Useful for comparing modeling ease and solving speed.
- “Everest” Sudoku: considered the hardest in the world. A benchmark to test robustness in highly combinatorial problems. Not all solvers managed acceptable times, revealing clear differences.
- Notebook assignment: an original, real-life–inspired case: minimizing the number of notebooks a student needs based on their class schedule. This tested the ability to model realistic scenarios with both hard and soft constraints. For more details about the problem, please refer to the thesis document attached at the end.
Key findings
The results led to several insights:
- Choco-solver: stood out for its efficiency and compact modeling. It was the fastest in many experiments, especially with combinatorial problems. Best suited for classic, well-structured cases.
- OptaPlanner: strongest in realistic planning scenarios, where flexibility and heuristic configuration matter. Very expressive in modeling, though it required more implementation effort. Ideal for complex planning problems.
- JaCoP: limited for handling soft constraints, which affects optimization in realistic scenarios. Simpler and more accessible, making it a good entry point for beginners in constraint programming.
Ultimately, the comparison showed there’s no “perfect solver” for every case. The choice depends on the problem type, model complexity, and practical needs.
Beyond academia
The conclusion was clear: this approach has enormous potential for solving real-world planning and optimization problems. From scheduling in educational institutions, to optimizing delivery routes, allocating work shifts, or managing resources in industrial companies.
What began as one client’s specific need became a thesis that not only explored the state of the art in Constraint Solving tools but also opened the door to countless practical applications—more relevant than ever for organizations seeking efficiency and flexibility.
This article summarizes the main points of the research, but the full thesis includes a more detailed analysis of algorithms, experiments, and results. You can access the complete document here: Constraint solving and its practical application to constraint-based problems.
If you’re evaluating your options and want to share them with us to get our perspective, let’s set up a chat ☕—the coffee is on us!
