Qaekwy，一个崭新的Python运筹优化库

今天给大家介绍一下Qaekwy，一个Python运筹优化库，该优化库是2023年才建立的，但文档方面介绍的比较齐全，建模和求解过程简单适用，本文介绍这个优化库的基本使用。

安装

pip install Qaekwy

案例

先看看官方基础案例。（从这个案例入门很简单，看完就能实现基础建模操作。）

from qaekwy.engine import DirectEngine
from qaekwy.model.constraint.relational import RelationalExpression
from qaekwy.model.specific import SpecificMaximum
from qaekwy.model.variable.integer import IntegerVariable
from qaekwy.model.modeller import Modeller
from qaekwy.model.searcher import SearcherType

# Define the optimization problem using Qaekwy Python Client
class SimpleOptimizationProblem(Modeller):
    def __init__(self):
        super().__init__()

        # Create a integer variables
        x = IntegerVariable(var_name="x", domain_low=0, domain_high=100)
        y = IntegerVariable(var_name="y", domain_low=0, domain_high=10)
        z = IntegerVariable(var_name="z", domain_low=0, domain_high=10)

        # Constraints
        constraint_1 = RelationalExpression(y > 2*x)
        constraint_2 = RelationalExpression(x >= 4)
        constraint_3 = RelationalExpression(z == y - x)

        # Objective: Maximize z
        self.add_objective(
            SpecificMaximum(variable=z)
        )

        # Add variable and constraint to the problem
        self.add_variable(x)
        self.add_variable(y)
        self.add_variable(z)
        self.add_constraint(constraint_1)
        self.add_constraint(constraint_2)
        self.add_constraint(constraint_3)

        # Set the search strategy
        self.set_searcher(SearcherType.BAB)

# Create a Qaekwy engine for interaction with the freely-available Cloud instance
qaekwy_engine = DirectEngine()

# Create the optimization problem instance
optimization_problem = SimpleOptimizationProblem()

# Request the Qaekwy engine to solve the problem
response = qaekwy_engine.model(model=optimization_problem)

# Retrieve the list of solutions from the response
list_of_solutions = response.get_solutions()

# Print the solution(s) obtained
for solution in list_of_solutions:
    print(f"Optimal solution: x = {solution.x}")
    print(f"Optimal solution: y = {solution.y}")
    print(f"Optimal solution: z = {solution.z}")

整体的思路是先进行建模，建模过程中把模型变量、目标、使用的搜索策略都设置好，然后再求解。

Qaekwy建模及求解框架

Qaekwy建模框架很清晰，主要有以下几个步骤。

设计模型

这里先设立模型框架，比如基础案例中，设定的是一个线性规划问题。

# Create the optimization problem instance
optimization_problem = SimpleOptimizationProblem()

定义问题

对问题进行定义，加上约束和目标各种函数。

  # Create a integer variables
        x = IntegerVariable(var_name="x", domain_low=0, domain_high=100)
        y = IntegerVariable(var_name="y", domain_low=0, domain_high=10)
        z = IntegerVariable(var_name="z", domain_low=0, domain_high=10)

        # Constraints
        constraint_1 = RelationalExpression(y > 2*x)
        constraint_2 = RelationalExpression(x >= 4)
        constraint_3 = RelationalExpression(z == y - x)

        # Objective: Maximize z
        self.add_objective(
            SpecificMaximum(variable=z)
        )

        # Add variable and constraint to the problem
        self.add_variable(x)
        self.add_variable(y)
        self.add_variable(z)
        self.add_constraint(constraint_1)
        self.add_constraint(constraint_2)
        self.add_constraint(constraint_3)

设定求解方法

本环节是设定求解的方法，Qaekwy内部封装了许多求解方法。

 # Set the search strategy
 self.set_searcher(SearcherType.BAB)

这里使用的是BAB方法，从文档介绍来看，应该是使用分支定界法求解最优解，也是比较常用的方法。

实例化 Qaekwy 引擎

这里用了自带的免费实例化引擎，官网文档介绍，中小规模可以用自带免费引擎求解。当然，可以换更牛的引擎（估计需要更高的算力，可能需要自己买算力。）

qaekwy_engine = DirectEngine()

解决问题

前面搭建好了以后，就可以求解了。

# Request the Qaekwy engine to solve the problem
response = qaekwy_engine.model(model=optimization_problem)

# Retrieve the list of solutions from the response
list_of_solutions = response.get_solutions()

# Print the solution(s) obtained
for solution in list_of_solutions:
    print(f"Optimal solution: x = {solution.x}")
    print(f"Optimal solution: y = {solution.y}")
    print(f"Optimal solution: z = {solution.z}")

更多案例-背包问题

为了方便大家理解建模及求解过程，再给一个背包问题的案例给大家参考学习。

from qaekwy.engine import DirectEngine
from qaekwy.model.constraint.relational import RelationalExpression
from qaekwy.model.specific import SpecificMaximum
from qaekwy.model.variable.branch import BranchIntegerVal
from qaekwy.model.variable.integer import IntegerVariable, IntegerExpressionVariable
from qaekwy.model.modeller import Modeller
from qaekwy.model.searcher import SearcherType

import json


class KnapsackProblem(Modeller):
    """
    KnapsackProblem
    """

    def __init__(self, weights, values, weight_limit):
        super().__init__()

        num_items = len(weights)
        selected_items = [
            IntegerVariable(
                var_name=f"item_{i}",
                domain_low=0,
                domain_high=1,
                branch_val=BranchIntegerVal.VAL_MIN,
            )
            for i in range(num_items)
        ]

        # Constraint: Total weight of selected items should be less than or equal
        # to the weight limit
        weight_constraint = RelationalExpression(
            sum(weights[i] * selected_items[i] for i in range(num_items))
            <= weight_limit
        )

        # Add variables and constraints to the problem
        for item_var in selected_items:
            self.add_variable(item_var)

        self.add_constraint(weight_constraint)

        # Maximize the total value
        total_value = IntegerExpressionVariable(
            var_name="total_value",
            expression=sum(values[i] * selected_items[i] for i in range(num_items)),
            branch_val=BranchIntegerVal.VAL_MIN,
        )

        self.add_variable(total_value)
        self.add_objective(SpecificMaximum(total_value))

        # Set the search strategy to Branch-and-bound Search (BAB)
        self.set_searcher(SearcherType.BAB)


if __name__ == "__main__":
    # Create a Qaekwy engine for direct interaction
    qaekwy_engine = DirectEngine()

    # Define the items' weights, values, and knapsack weight limit
    weights = [2, 3, 4, 5,1,2,4,4,1,1]
    values = [3, 4, 5, 6,120,3,4,5,1,2]
    knapsack_weight_limit = 3

    # Create the knapsack problem instance
    knapsack_problem = KnapsackProblem(weights, values, knapsack_weight_limit)

    # Request the Qaekwy engine to solve the knapsack problem
    response = qaekwy_engine.model(model=knapsack_problem)

    # Retrieve the list of solutions from the response
    list_of_solutions = response.get_solutions()

    solution = list_of_solutions[0]
    for solution_item, solution_value in solution.items():
        if "item" in str(solution_item).lower():
            idx = int(solution_item.split("_")[1])
            item_weight, item_value = weights[idx], values[idx]
            print(
                f"Item {idx}: Weight = {item_weight}; Value = {item_value}; Packed = {solution_value}"
            )

    print(f"Total Value: {solution.total_value}")

官方文档已经把求解过程、变量设定、目标设定等规则介绍的非常详细。感兴趣的可以查阅本文的参考资料链接。