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)#

Bases: SolverBase, JsonSerializableMixin

Penalty function method

Set kw.utils.CheckpointManager.save_dir = ‘/tmp’ will turn on the cache switch, and the current state and the penalty coefficient combination that meets the hard constraints will be cached. After turning on the cache, PenaltyMethodSolver can continue to iterate and solve based on the last program termination

Args:

optimizer (OptimizerBase): Optimizer

controller (SolverLoopController): loop controller

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.utils.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(qubo_model)#

Solve the QUBO model and return the solution with the lowest target value (the solution with the lowest target value may not be the optimal solution because the penalty coefficient changes)

Args:: qubo_model (QuboModel): QUBO model
Returns:: tuple: dictionary, target value, penalty coefficient of QUBO model solution

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, ...}
    },
    ...
]

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))
>>> sol_dict, qubo_val = solver.solve_qubo(qubo_model)
>>> unsatisfied_cnt, result_dict = qubo_model.verify_constraint(sol_dict)
>>> unsatisfied_cnt
0

solve_qubo(qubo_model)#

Solve QUBO

Args:

qubo_model (QuboModel): QUBO model

Returns:

tuple: Tuple containing the solution result information

dict: Solution dictionary
float: QUBO expression value

class kaiwu.solver.SolverBase(optimizer)#

Bases: object

Solver Base Class

Args:: optimizer (OptimizerBase): Ising solver

solve_qubo(qubo_model)#

Solve QUBO

Args:

qubo_model (QuboModel): QUBO model

Returns:

tuple: Tuple containing the solution result information

dict: Solution dictionary
float: QUBO expression value

kaiwu.solver package

Contents

kaiwu.solver package#

Module contents#