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:

# 4. Solve the model, asking for an unique solution
solution = m.solve_one()

# 5. Print the solution
if solution:
    print(f"Solution found!")
    print(f"  Country A color: {solution.countries[0]}")
    print(f"  Country B color: {solution.countries[1]}")
    print(f"  Country C color: {solution.countries[2]}")

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:

import qaekwy as qw

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

# Initialize model
m = qw.Model()

# Create integer variables for item selection using the array helper
# domain=(0, 1) acts as binary selection
items_to_take = m.integer_array(name="items", length=n_items, domain=(0, 1))

# Constraint: Total weight must not exceed capacity
# We can define the expression directly within the constraint
m.constraint(
    sum(items_to_take[i] * weights[i] for i in range(n_items)) <= capacity
)

# Objective: Maximize total value
# We promote the total_value expression to a variable to easily retrieve it later
total_value = m.integer_variable(
    name="total_value",
    expression=sum(items_to_take[i] * values[i] for i in range(n_items))
)

m.maximize(total_value)

# Solve model using Branch-and-bound searcher
solution = m.solve_one(searcher="bab")

# Output results
if solution:
    print("Optimal solution found!")
    
    # Access the array of variables directly from the solution object
    selected_indices = solution["items"]
    
    for i in range(n_items):
        decision = "Yes" if selected_indices[i] == 1 else "No"
        print(f"  Take Item {i+1}: {decision}")
    
    # Direct access to the promoted objective variable
    print(f"Total Value: {solution.total_value}")
    
    # We can also compute values on the fly if not promoted
    current_weight = sum(selected_indices[i] * weights[i] for i in range(n_items))
    print(f"Total Weight: {current_weight}")
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. Solving the model 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 modelling!