kaiwu.solver package#

Module contents#

Module: solver

Function: Provides a series of solvers based on optimizers in cim/classical for solving

class kaiwu.solver.PenaltyMethodSolver(optimizer, controller, stop_after_feasible_count=None)#

Bases: SolverBase, JsonSerializableMixin

Penalty function method

设置 kw.common.CheckpointManager.save_dir = ‘/tmp’ 会打开缓存开关，当前状态和符合硬约束的惩罚系数组合都会被缓存打开缓存后 PenaltyMethodSolver 可以在上一次程序终止的基础上继续迭代求解, 程序运行过程中的可行解会保存对应json文件里面 results 中.

Args:

optimizer (OptimizerBase): Optimizer

controller (SolverLoopController): loop controller

stop_after_feasible_count (int): Iteration stops after finding how many feasible solutions, the default is None

Examples:

>>> import kaiwu as kw
>>> import numpy as np
>>> taskNums = 20
>>> machineNums = 5
>>> duration = np.array(range(1, taskNums + 1))
>>> machine_start_time = np.array(range(1, machineNums + 1))
>>> # Building a Qubo Model
>>> qubo_model = kw.qubo.QuboModel()
>>> X = kw.qubo.ndarray([taskNums, machineNums], "X", kw.qubo.binary)
>>> J_mean = (np.sum(duration) + np.sum(machine_start_time)) / machineNums
>>> J = [machine_start_time[i] + duration.dot(X[:, i]) for i in range(machineNums)]
>>> # Set objective function
>>> qubo_model.set_objective(kw.qubo.quicksum([(J[i] - J_mean) ** 2 for i in range(machineNums)]) / machineNums)
>>> # Set constraint
>>> for j in range(taskNums):
...     qubo_model.add_constraint((1 - kw.qubo.quicksum([X[j][i] for i in range(machineNums)])) == 0,
...                               f"c{j}", penalty=45)
>>> # Loop control
>>> controller = kw.common.SolverLoopController(max_repeat_step=5)
>>> # optimizer
>>> optimizer = kw.classical.SimulatedAnnealingOptimizer(initial_temperature=1e8,
...                                                      alpha=0.9,
...                                                      cutoff_temperature=0.01,
...                                                      iterations_per_t=200,
...                                                      size_limit=100)
>>> solver = kw.solver.PenaltyMethodSolver(optimizer, controller)
>>> sol_dict, hmt = solver.solve_qubo(qubo_model)
>>> J_end = np.zeros(machineNums)
>>> for i in range(machineNums):
...     ifturn_temp = kw.qubo.get_val(kw.qubo.quicksum(X[:, i]), sol_dict)
...     ifturn = 1 if ifturn_temp > 0 else 0
...     J_temp = duration.dot(X[:, i]) + machine_start_time[i] * ifturn
...     J_end[i] = kw.qubo.get_val(J_temp, sol_dict)
>>> print("duration array: ", duration)  
duration array:  [ 1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20]
>>> print("Machine startup time: ", machine_start_time)  
Machine startup time:  [1 2 3 4 5]
>>> print("End time of all machines：", J_end)  
End time of all machines： [43. 43. 48. 45. 46.]
>>> print('final result：{}'.format(np.max(J_end)))  
final result：48.0
>>> print('variance：', np.var(J_end))   
variance: 3.6

get_latest_penalty()#

Get the latest penalty combination

Returns:: dict: latest penalty coefficient combination

solve_qubo(*args, **kwargs)#

solve_qubo_multi_results(qubo_model, size_limit=10)#

Solve the QUBO model and return multiple solutions

Args:

qubo_model (QuboModel): QUBO model

size_limit (int): Returns the number of solutions

Returns:

list: dictionary of QUBO model solutions, target values and penalty coefficients, in the form of:

[
    {
        'sol_dict': {'x[0]': 1.0, 'x[1]': 0.0, 'x[2]': 0.0, 'x[3]': 0.0, 'x[4]': 1.0, 'x[5]': 0.0, ...}
        'objective': -15.01,
        'penalty': {'c35': 84.375, 'c39': 90.17578125, ...}
    },
    ...
]

load_json_dict(json_dict)#

The dict recovery object read from the JSON file

Returns:: Dict: json dictionary

to_json_dict(exclude_fields=('optimizer',))#

Convert to JSON dictionary

Returns:: Dict: json dictionary

class kaiwu.solver.SimpleSolver(optimizer)#

Bases: SolverBase

Implementing the use of Optimizer to solve QuboModel directly

Args:

optimizer (OptimizerBase): Ising solver

Examples:

>>> import kaiwu as kw
>>> n = 10
>>> W = 5
>>> p = [i + 1 for i in range(n)]
>>> w = [(i + 2) / 2 for i in range(n)]
>>> x = kw.qubo.ndarray(n, 'x', kw.qubo.Binary)
>>> qubo_model = kw.qubo.QuboModel()
>>> qubo_model.set_objective(sum(x[i] * p[i] * (-1) for i in range(n)))
>>> qubo_model.add_constraint(sum(x[i] * w[i] for i in range(n)) <= W, "c", 10)
>>> solver = kw.solver.SimpleSolver(kw.classical.SimulatedAnnealingOptimizer(alpha=0.999, iterations_per_t=50))
>>> sol_dict, qubo_val = solver.solve_qubo(qubo_model)
>>> unsatisfied_count, result_dict = qubo_model.verify_constraint(sol_dict)
>>> unsatisfied_count
0

solve_qubo(*args, **kwargs)#

class kaiwu.solver.SolverBase(optimizer)#

Bases: object

Solver Base Class

Args:: optimizer (OptimizerBase): Ising solver

solve_qubo(*args, **kwargs)#

kaiwu.solver package

Contents

kaiwu.solver package#

Module contents#