Bachelor’s Thesis on Constraint Programming

Overview

As a computer-science undergraduate, my research asked a practical question: when a simulator accumulates many possible conditions, how can it stop reconsidering the ones that can no longer occur? I developed and evaluated a method for HydLa that uses the direction in which a value is changing to remove obsolete conditions from the search. In the benchmark model, it reduced the total simulation time to approximately half.

This work is an early foundation of my design philosophy. Constraint programming taught me that complex outcomes do not always need to be specified directly: they can emerge from a carefully defined space of rules, priorities, and boundaries. That way of thinking now informs my approach to design based on constraints in the age of AI—designing the conditions within which a generative system is free to act.

Abstract

HydLa is a modeling language for hybrid systems: systems in which continuous change and discrete events interact. Its constraint-based design allows such systems to be described concisely and simulated with high precision. The cost is that a large model may leave the simulator checking a great many conditional rules, even after some have become irrelevant.

This research proposed reducing those guarded constraints dynamically. By recognizing monotonic behavior—a value continuing to move in one direction—the simulator can determine that certain guards will never become true in the future and safely stop checking them. The approach was especially effective in a model containing many similarly guarded objects, where the measured runtime fell to roughly half of the original.

1. Introduction

A hybrid system combines continuous behavior with discrete events. A bouncing ball is a simple example: its position and velocity change continuously while it is in the air, but the instant it hits a surface creates a discrete event that changes its direction. Thermostats, vehicles, and robots all contain more consequential versions of the same mixture.

HydLa lets a modeler describe these systems with mathematical and logical constraints instead of spelling out a single procedural sequence. Its simulator, HyLaGI, can perform symbolic calculations without rounding error and can work with uncertain parameters. This expressive approach, however, creates a scaling problem: when a model contains many rules that activate only under particular conditions, the simulator repeatedly has to ask whether each condition could be the next one to occur.

2. Guarded Constraints in Simulations

A guarded constraint is a rule that becomes active only when its guard condition is satisfied. In the benchmark above, every surface segment has its own rule: if the ball reaches height zero while its horizontal position lies within that segment, the bounce rule applies. Dividing the surface into more pieces therefore gives the simulator more guards to inspect.

The experiment varied the number of segments from 10 to 200. The original simulator became slower approximately with the square of that number. This matters beyond the toy example: a larger model may represent many physical objects, contact regions, or possible events in exactly this guarded form.

3. Location of the Bottleneck

Profiling showed that the slowdown was not spread evenly across the simulator. With 100 surface segments, 96% of the measured runtime was spent in FindMinTime, the operation that searches for the earliest possible next event. It was repeatedly evaluating the guards of every candidate constraint.

That result made the optimization target specific: reduce the number of guards that FindMinTime has to consider, while preserving exactly the same simulated behavior.

4. Reduction of Guarded Constraints

Imagine a ball bouncing down a staircase. Once the ball has passed a step and continues moving forward, that step can no longer affect it. A person looking at the diagram ignores the steps behind the ball immediately; the original algorithm continued checking every one of them.

The difficult part is proving that a discarded guard will never be needed later. Removing one merely because it is false now could silently produce the wrong result if it becomes true again. The proposal therefore uses monotonicity: whether a variable is guaranteed to keep increasing or keep decreasing over a time interval.

4.1 Approach to Uniform Monotonicity

The first approach applies when a variable moves in one direction for the entire simulation. In the split-surface model, the ball’s horizontal position always increases. Once it has moved beyond a segment, the condition for that segment can never be satisfied again. Model-checking techniques can establish this property before simulation, allowing obsolete guards to be removed safely as the run proceeds.

4.2 Approach to Alternating Monotonicity

Many real systems do not move in one direction forever. A variable may increase, turn, and then decrease. The paper therefore outlined a second approach: begin with an assumed direction, monitor that assumption with assertions, and restart the reduction logic from the point where the direction changes. Guards removed for one monotonic interval are reset when the next interval begins.

5. Experimental Results

I implemented the uniform-monotonicity approach and evaluated it with the split-surface model. Both the original and proposed algorithms still took longer as the number of segments grew, but the proposed version consistently did less work. Comparing the fitted curves, the leading coefficient fell from 1.1463 to 0.6083; for this benchmark, the total simulation time was approximately halved.

The result is not a claim that every HydLa model becomes twice as fast. It shows where the method helps: models with many guarded objects and a provable direction of change, where guards become permanently irrelevant during a run.

6. Conclusion and Future Work

The research demonstrated that knowledge about a model—not only faster low-level computation—can make simulation more efficient. By using monotonicity to recognize which possibilities have become impossible, HyLaGI can shrink its active constraint set without changing the result.

The implemented experiment covered uniform monotonicity. The paper left two directions for later work: evaluating the assertion-based method for alternating behavior, and using invariants other than monotonicity to identify further constraints that can be removed safely.