Solving with Qaekwy

🎓 Solving with Qaekwy

In our previous lesson, we built a Qaekwy model for a map coloring problem. Now it’s time to find a solution! We will also explore optimization, which is about finding the best solution, not just any valid one.

Solving a Constraint Satisfaction Problem

Once you have a model, finding a solution is straightforward. You need a Qaekwy Engine. The engine takes your model, works its magic (called “search”), and gives you back a SolutionResponse.

Let’s solve our map coloring problem from the last lesson:

# (Assuming the model from the previous lesson is defined)
from qaekwy.engine import DirectEngine

# 1. Create an engine
engine = DirectEngine()

# 2. Ask the engine to solve the model
solution_response = engine.model(modeller)

# 3. Check the result and print the solution
if solution_response and solution_response.is_status_ok():
    solutions = solution_response.get_solutions()
    if solutions:
        # Get the values for our 'countries' variable array
        solution = solutions[0].countries
        print(f"Solution found!")
        print(f"  Country A color: {solution[0]}")
        print(f"  Country B color: {solution[1]}")
        print(f"  Country C color: {solution[2]}")
    else:
        print("No solution found.")
else:
    print(f"An error occurred.")

Possible Output:

Solution found!
  Country A color: 0
  Country B color: 1
  Country C color: 0

This corresponds to Red, Green, Red, which is a valid coloring!

From Satisfaction to Optimization

Sometimes, you don’t just want any solution; you want the best one. This is the difference between Constraint Satisfaction and Optimization.

To have an optimization problem, you need one more ingredient:

  • Objective Function: A function that you want to either minimize or maximize.

Example: The 0/1 Knapsack Problem

Imagine you are a burglar with a knapsack that can only carry a certain weight. You have a choice of items, each with its own weight and value. Your goal is to maximize the total value of the items you steal without exceeding the knapsack’s weight limit.

Let’s model a simple version:

  • Knapsack Capacity: 10 kg
  • Items:
    • Item 1: 5 kg, Value: 10
    • Item 2: 4 kg, Value: 8
    • Item 3: 3 kg, Value: 6

Here’s the Qaekwy model:

from qaekwy.model.modeller import Modeller
from qaekwy.model.variable.integer import IntegerExpressionVariable, IntegerVariableArray
from qaekwy.model.specific import SpecificMaximum
from qaekwy.model.searcher import SearcherType
from qaekwy.engine import DirectEngine

# Data
weights = [5, 4, 3]
values = [10, 8, 6]
capacity = 10
n_items = len(weights)

# Initialize model
modeller = Modeller()

# Create integer variables for item selection
#
# Note: As the set of Booleans isn't the same set as the set of Integers, we use
# IntegerVariableArray with domain 0..1. Indeed, the next steps involve operations
# (multiplications and summations), and the mixing of types isn't allowed in Qaekwy.
items_to_take = IntegerVariableArray("items", n_items, domain_low=0, domain_high=1)
modeller.add_variable(items_to_take)

# Constraint: Total weight must not exceed capacity
total_weight = IntegerExpressionVariable(
    "total_weight",
    sum(items_to_take[i] * weights[i] for i in range(n_items))
)
modeller.add_variable(total_weight)
modeller.add_constraint(total_weight <= capacity)

# Objective: Maximize total value
total_value = IntegerExpressionVariable(
    "total_value",
    sum(items_to_take[i] * values[i] for i in range(n_items))
)
modeller.add_variable(total_value)
modeller.add_objective(SpecificMaximum(total_value))

# Set search strategy
modeller.set_searcher(SearcherType.BAB)

# Solve model
engine = DirectEngine()
solution_response = engine.model(modeller)

# Output results
if solution_response and solution_response.is_status_ok():
    solutions = solution_response.get_solutions()
    if solutions:
        solution = solutions[0].items
        print("Optimal solution found!")
        for i in range(n_items):
            print(f"  Take Item {i+1}: {'Yes' if solution[i] else 'No'}")
        print(f"Total Value: {sum(solution[i] * values[i] for i in range(n_items))}")
        print(f"Total Weight: {sum(solution[i] * weights[i] for i in range(n_items))}")
else:
    print("No solution found.")

Expected Output:

Optimal solution found!
  Take Item 1: Yes
  Take Item 2: Yes
  Take Item 3: No
Total Value: 18
Total Weight: 9

The optimal solution is to take Item 1 and Item 2, for a total weight of 9 kg and a total value of 18.

Conclusion

Congratulations! You have now learned how to:

  1. Define a problem using variables, domains, and constraints.
  2. Model that problem in Qaekwy.
  3. Use the Qaekwy engine to find a valid solution.
  4. Add an objective function to find the best possible solution.

This is the foundation of all work done in constraint programming and optimization. Happy modeling!