Modelling

🧩 Modelling with Qaekwy

This guide will show you how to build a model, which is just a fancy word for a description of your problem.

A model has three main ingredients:

  1. Variables: The things you want to find the values of.
  2. Constraints: The rules that your solution must follow.
  3. Objectives: What you want to achieve (minimizing or maximizing one or more variables of the model).

Let’s look at each of these ingredients one by one.

1. Variables 📦

Variables are the unknowns in your problem. Think of them as empty boxes that Qaekwy needs to fill with values.

Qaekwy has different types of variables for different types of problems:

  • IntegerVariable: For whole numbers (e.g., 1, 2, 3).
  • FloatVariable: For numbers with decimal points (e.g., 1.5, 3.14).
  • BooleanVariable: For true/false decisions (represented as 1 for true and 0 for false).
  • IntegerVariableArray, FloatVariableArray, BooleanVariableArray: For a list of variables of the same type.

Creating Variables

Here’s how you can create some variables:

from qaekwy.model.variable.integer import IntegerVariable, IntegerVariableArray
from qaekwy.model.variable.float import FloatVariable
from qaekwy.model.variable.boolean import BooleanVariable

# An integer variable named "x" that can be any whole number from 1 to 10
x = IntegerVariable("x", 1, 10)

# A float variable named "y" that can be any number between 0.0 and 1.0
y = FloatVariable("y", 0.0, 1.0)

# A boolean variable named "b" that can be either true (1) or false (0)
b = BooleanVariable("b")

# An array of 5 integer variables, each of which can be a number from 0 to 9
arr = IntegerVariableArray("arr", 5, 0, 9)

2. Constraints 📜

Constraints are the rules of your problem. They tell Qaekwy what a valid solution looks like.

Relational Constraints

You can use standard Python comparison operators to create constraints:

# x must be greater than y
modeller.add_constraint(x > y)

# The sum of the first two elements of arr must be less than or equal to 5
modeller.add_constraint(arr[0] + arr[1] <= 5)

Global Constraints

Qaekwy has some special “global” constraints that are useful for common problems:

  • ConstraintDistinctArray: Makes sure that all the elements in an array have different values.
  • ConstraintElement: Links the value of a variable to an element in an array.
from qaekwy.model.constraint.distinct import ConstraintDistinctArray

# All the elements in our array must be different
modeller.add_constraint(ConstraintDistinctArray(arr))

Logical Constraints

You can also combine constraints using logical operators:

from qaekwy.model.constraint.if_then_else import ConstraintIfThenElse

# If y is greater than 2, then x must be less than 5
modeller.add_constraint(ConstraintIfThenElse(y > 2, x < 5))

# You can also use | for "or"
modeller.add_constraint((x > 5) | (y < 0.5))

3. Objectives 🎯

Objectives are what you want to achieve. This is the optional optimization part of your problem.

from qaekwy.model.specific import SpecificMinimum, SpecificMaximum

# I want to find the solution with the smallest value of x
modeller.add_objective(SpecificMinimum(x))

# I want to find the solution with the largest value of y
modeller.add_objective(SpecificMaximum(y))

🧠 Advanced Modelling Techniques

Here are a few more advanced techniques that can help you solve more complex problems.

Reification: Enabling or Disabling Constraints

Reification enables the implementation of conditional constraints, where the enforcement of a constraint depends on the validity of the associated condition.

In Qaekwy, you can use ConstraintIfThenElse to do this.

Example: Conditional Constraints

Suppose you are modelling a simple physics scenario: a block can slide or stay still depending on the applied force.

from qaekwy.model.constraint.if_then_else import ConstraintIfThenElse

friction_limit = 5

# If the applied force is greater than the friction limit, then the block moves (velocity > 0)
# Otherwise, the block stays still (velocity == 0)
modeller.add_constraint(
    ConstraintIfThenElse(
        force > friction_limit,
        velocity > 0,
        velocity == 0
    )
)

Symmetry Breaking: Don’t Waste Time on a Mirrored Solution

Some problems have “symmetries,” which are different solutions that are essentially the same. For example, in a coloring problem, it doesn’t matter if you color a region blue and its neighbor red, or vice-versa.

Symmetry breaking is the process of adding extra constraints to your model to eliminate these symmetries. This can save the solver a lot of time.

Example: Coloring Problem

Imagine you’re coloring a map with two colors, red and blue (represented as 0 and 1). To break the symmetry, you can say that the first region’s color must be less than or equal to the second’s.

# color is an array of variables representing the color of each region
modeller.add_constraint(color[0] <= color[1])

Redundant Constraints: Sometimes, More is More!

A redundant constraint is a constraint that is already implied by the other constraints. It might seem strange, but adding redundant constraints can sometimes help the solver find a solution faster. This is because redundant constraints can help the solver to prune the search space more effectively. By making information more explicit, you can help the solver to make deductions that it might not have been able to make otherwise.

Putting It All Together 🧑‍🍳

Here’s an example of a very simple model:

from qaekwy.model.modeller import Modeller
from qaekwy.model.searcher import SearcherType
from qaekwy.model.variable.integer import IntegerVariable
from qaekwy.model.specific import SpecificMinimum

# 1. Create a modeller
modeller = Modeller()

# 2. Define variables
x = IntegerVariable("x", 0, 10)
y = IntegerVariable("y", 0, 10)

modeller.add_variable(x).add_variable(y)

# 3. Define constraints
modeller.add_constraint(x + y == 10)
modeller.add_constraint(x * 2 <= y)

# 4. Define objective
modeller.add_objective(SpecificMinimum(x))

# 5. Set searcher
modeller.set_searcher(SearcherType.BAB)

This model will find the values of x and y that satisfy the constraints and have the smallest possible value of x.