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. Instantiating a new model

Here’s how to start a new model:

# Unique import
import qaekwy as qw

# Instantiating a new Model
m = qw.Model()

2. Variables

Variables represent the unknown values the solver will assign. Each variable has a domain, which defines the set of values it is allowed to take. Variables and their domains define the “search space” of your problem.

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

  • Integer: For whole numbers (e.g., 1, 2, 3).
  • Float: For numbers with decimal points (e.g., 1.5, 3.14).
  • Boolean: For true/false decisions (represented as 1 for true and 0 for false).
  • Array of integer: For a list of variables of integers.
  • Array of floats: For a list of variables of floats.
  • Array of booleans: For a list of variables of booleans.
  • Matrix of integer: For a matrix of variables of type integers.
  • Matrix of floats: For a matrix of variables of type floats.
  • Matrix of booleans: For a matrix of variables of type booleans.

Here’s how you can create some variables:

# x, an integer in [-10, 10]
x = m.integer_variable("x", (-10, 10))

# y, an integer in [-10, 10]
y = m.integer_variable("y", (-10, 10))

# z, such that z equals x + y
z = m.integer_variable("z", expression=x + y)

# w, a 2x3 matrix having each cell w_i_j in [0, 50]
w = m.integer_matrix("w", rows=2, cols=3, domain=(0, 50))

Note: Variables defined with an expression are derived variables. They are automatically constrained to equal the given expression and do not introduce additional degrees of freedom.

3. Constraints

Constraints are the rules that your solution must follow. They are the heart of your model, telling Qaekwy what a valid solution looks like.

Think of constraints as the rules of a puzzle. For example, in a Sudoku puzzle, the constraints are:

  • Each row must have the digits 1 through 9, with no repeats.
  • Each column must have the digits 1 through 9, with no repeats.
  • Each 3x3 square must have the digits 1 through 9, with no repeats.

Why are Constraints Important?

Constraints give your model its structure. The solver uses them to eliminate possibilities and find a solution. This process is called constraint propagation. The progapators prune variables’ domain until a viable/optimal solution has been found.

Relational Constraints

You can use standard Python comparison operators to create constraints:

# Enforces x + 2y + 3 <= 15
m.constraint(x + 2 * y + 3 <= 15)

# Enforces the sum of the 2nd column of w to be equal to 10 + z
m.constraint(sum(w.col(1)) == 10 + z)

# Enforces either:
#   abs(z) to be equal to (x - (y + 1))^2, or
#   z to be greater or equal to 4
m.constraint(
    (qw.math.absolute(z) == qw.math.power(x - (y + 1), 2)) | (z >= 4)
)

Global Constraints

Global constraints capture common patterns (like uniqueness or indexing) in a single, optimized constraint that the solver can reason about more efficiently.

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

  • distinct: Makes sure that all the elements in an array (or matrix row, column or block) have different values.
  • element: Links the value of a variable to an element in an array (enforces array[i] == j).
# Ensures all values of 'my_array' are unique
m.constraint_distinct(my_array)

# Ensures all values in column 'i' of 'my_matrix' are unique
m.constraint_distinct(my_matrix.col(i))

# Ensures the value of 'my_array' at position 'variable x' equals 'variable y'
m.constraint_element(my_array, x, y)

Logical Constraints

You can also combine constraints using logical operators, if-then-else-style:

# Ensures that if 'condition' is enforced, then 'then_constraint' is enforced,
# otherwise 'else_constraint' is enforced.
m.constraint_if_then_else(
    condition=x + y <= 7,
    then_constraint=z >= 2,
    else_constraint=z <= 2
)

4. Objectives

Objectives are what you want to achieve. This is the optional optimization part of your problem. In Qaekwy, you can add multiple objectives.

# I want to find the solution with the smallest value of x
m.minimize(x)

# I want to find the solution with the largest value of y
m.maximize(y)

Simple model example

Here’s an example of a very simple model:

import qaekwy as qw

# 1. Create a model
m = qw.Model()

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

# 3. Define constraints
m.constraint(x + y == 10)
m.constraint(x * 2 <= y)

# 4. Define objective
m.minimize(x)

The solver will find the values of x and y that satisfy the constraints with the smallest possible value of x.

Advanced Modelling Techniques

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

Symmetry Breaking

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
m.constraint(color[0] <= color[1])

Redundant constraints

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.