python - Docplex and callback problems - Stack Overflow

admin管理员组

文章数量:1356935

I’m trying to implement a custom callback that solves a subproblem during the optimization process. I want to:

1. Get the values of certain variables from the main model's solution.

2. Solve a subproblem (a separate optimization problem) based on these values.

3. If the subproblem solution suggests a cut, add it to the main model as a new constraint.

I'll share my code here, i really wanted to do it in python but im so lost right now, ive been trying also xpress and similar but documentation is useless, any help would be greatly appreciated.

from docplex.mp.model import Model
from cplex.callbacks import UserCutCallback
from docplex.mp.callbacks.cb_mixin import ConstraintCallbackMixin
import random

class CustomCutCallback(ConstraintCallbackMixin, UserCutCallback):
    def __init__(self, env):
        UserCutCallback.__init__(self, env)
        ConstraintCallbackMixin.__init__(self)
        self.eps = 1e-6
        self.nb_cuts = 0
        self.cts = []

    def add_cut_constraint(self, cut):
        self.register_constraint(cut)

    def __call__(self, context):
        """
        This method is invoked by CPLEX during optimization.
        It receives the 'context' to interact with the model and variables.
        """
        print("Callback called with context")
        m = context.model  # The main model from the context
        m_sol = m.solution

        x_values = {var: m_sol.get_value(var) for var in m.variables if var.name.startswith('x')}
        w_values = {var: m_sol.get_value(var) for var in m.variables if var.name.startswith('w')}
        m2_cuts = self.solve_subproblem(x_values, w_values, m, context)

    def solve_subproblem(self, x_values, w_values, m, context):
        """
        Solves the subproblem and generates cuts if necessary.
        """
        m2 = Model(name='subproblem')

        client_range = range(len(x_values))
        deposit_range = range(len(w_values))
        plant_range = range(len(w_values[0]))

        alpha = m2.continuous_var_matrix(client_range, deposit_range, name='alpha', lb=0)
        beta = m2.continuous_var_matrix(deposit_range, plant_range, name='beta', lb=0)

        m2.add_constraints(alpha[i, j] + (x_values.get((i, j), 0) * beta[j, k]) <= x_values.get((i, j), 0) * w_values.get((j, k), 0)
                           for i in client_range for j in deposit_range for k in plant_range)

        m2.maximize(m2.sum(alpha[i, j] * x_values.get((i, j), 0) for i in client_range for j in deposit_range) + 
                    m2.sum(beta[j, k] * w_values.get((j, k), 0) for j in deposit_range for k in plant_range))

        m2.solve()
        print(m2.solution)

        # Here, you perform an evaluation of the cut values
        for i in client_range:
            for j in deposit_range:
                for k in plant_range:
                    if  sum(m2.solution.get_value(alpha[i, j]) * x_values.get((i, j), 0) for i in client_range for j in deposit_range) + \
                    sum(m2.solution.get_value(beta[j, k]) * w_values.get((j, k), 0) for j in deposit_range for k in plant_range) > \
                    sum(transport_cost_deposit_client[j][i] * d[i] * x[i, j] for i in client_range for j in deposit_range) + \
                    sum(transport_cost_plant_deposit[j][k] * w[j, k] for j in deposit_range for k in plant_range):
                        m.add_constraint(sum(m2.solution.get_value(alpha[i, j]) * x[i, j] for i in client_range for j in deposit_range) + \
                                         sum(m2.solution.get_value(beta[j, k]) * w[j, k] for j in deposit_range for k in plant_range))


# Main model
def build_location_model(transport_cost_deposit_client, transport_cost_plant_deposit, p, q, d, **kwargs):
    m = Model(name='location', **kwargs)

    num_deposits = len(transport_cost_deposit_client)
    num_plants = len(transport_cost_plant_deposit[0])
    num_clients = len(d)
    
    deposit_range = range(num_deposits)
    plant_range = range(num_plants)
    client_range = range(num_clients)

    x = m.binary_var_matrix(client_range, deposit_range, name='x')
    w = m.integer_var_matrix(deposit_range, plant_range, name='w', lb=0)
    y = m.binary_var_list(deposit_range, name='y')
    h = m.binary_var_list(plant_range, name='h')

    m.add_constraints(m.sum(x[i, j] for j in deposit_range) == 1 for i in client_range)
    m.add_constraints(m.sum(w[j, k] for k in plant_range) == y[j] for j in deposit_range)
    m.add_constraints(x[i, j] <= y[j] for i in client_range for j in deposit_range)
    m.add_constraint(m.sum(h[k] for k in plant_range) == q)
    m.add_constraint(m.sum(y[j] for j in deposit_range) == p)
    m.add_constraints(m.sum(d[i] * x[i,j] for i in client_range) == m.sum(w[j, k] for k in plant_range) for j in deposit_range)
    m.add_constraints(w[j, k] <= (m.sum(d[i] for i in client_range) * h[k]) for j in deposit_range for k in plant_range)

    transport_cost = m.sum(transport_cost_deposit_client[j][i] * d[i] * x[i, j] for i in client_range for j in deposit_range) + \
                        m.sum(transport_cost_plant_deposit[j][k] * w[j, k] for j in deposit_range for k in plant_range)
    m.minimize(transport_cost)
    m.parameters.preprocessing.presolve = 0

    # Register the callback
    cut_cb = m.register_callback(CustomCutCallback)

    # Configure CPLEX parameters for cuts
    params = m.parameters
    params.mip.cuts.mircut = -1

    m.solve()

    return m



# Test function
def solve_model():
    num_deposits = 10
    num_plants = 4
    num_clients = 20

    TRANSPORT_COST_DEPOSITS_CLIENTS = [
        [random.randint(20, 100) for _ in range(num_clients)] for _ in range(num_deposits)
    ]

    TRANSPORT_COST_PLANTS_DEPOSITS = [
        [random.randint(30, 80) for _ in range(num_plants)] for _ in range(num_deposits)
    ]

    p = 5
    q = 3
    d = [random.randint(5, 20) for _ in range(num_clients)]

    m = build_location_model(TRANSPORT_COST_DEPOSITS_CLIENTS, TRANSPORT_COST_PLANTS_DEPOSITS, p, q, d)
    if m.solution is None:
        print("No valid solution found.")
        return None
    print(m.solution)
    return m


if __name__ == "__main__":
    solve_model()

I’m trying to implement a custom callback that solves a subproblem during the optimization process. I want to:

1. Get the values of certain variables from the main model's solution.

2. Solve a subproblem (a separate optimization problem) based on these values.

3. If the subproblem solution suggests a cut, add it to the main model as a new constraint.

I'll share my code here, i really wanted to do it in python but im so lost right now, ive been trying also xpress and similar but documentation is useless, any help would be greatly appreciated.

from docplex.mp.model import Model
from cplex.callbacks import UserCutCallback
from docplex.mp.callbacks.cb_mixin import ConstraintCallbackMixin
import random

class CustomCutCallback(ConstraintCallbackMixin, UserCutCallback):
    def __init__(self, env):
        UserCutCallback.__init__(self, env)
        ConstraintCallbackMixin.__init__(self)
        self.eps = 1e-6
        self.nb_cuts = 0
        self.cts = []

    def add_cut_constraint(self, cut):
        self.register_constraint(cut)

    def __call__(self, context):
        """
        This method is invoked by CPLEX during optimization.
        It receives the 'context' to interact with the model and variables.
        """
        print("Callback called with context")
        m = context.model  # The main model from the context
        m_sol = m.solution

        x_values = {var: m_sol.get_value(var) for var in m.variables if var.name.startswith('x')}
        w_values = {var: m_sol.get_value(var) for var in m.variables if var.name.startswith('w')}
        m2_cuts = self.solve_subproblem(x_values, w_values, m, context)

    def solve_subproblem(self, x_values, w_values, m, context):
        """
        Solves the subproblem and generates cuts if necessary.
        """
        m2 = Model(name='subproblem')

        client_range = range(len(x_values))
        deposit_range = range(len(w_values))
        plant_range = range(len(w_values[0]))

        alpha = m2.continuous_var_matrix(client_range, deposit_range, name='alpha', lb=0)
        beta = m2.continuous_var_matrix(deposit_range, plant_range, name='beta', lb=0)

        m2.add_constraints(alpha[i, j] + (x_values.get((i, j), 0) * beta[j, k]) <= x_values.get((i, j), 0) * w_values.get((j, k), 0)
                           for i in client_range for j in deposit_range for k in plant_range)

        m2.maximize(m2.sum(alpha[i, j] * x_values.get((i, j), 0) for i in client_range for j in deposit_range) + 
                    m2.sum(beta[j, k] * w_values.get((j, k), 0) for j in deposit_range for k in plant_range))

        m2.solve()
        print(m2.solution)

        # Here, you perform an evaluation of the cut values
        for i in client_range:
            for j in deposit_range:
                for k in plant_range:
                    if  sum(m2.solution.get_value(alpha[i, j]) * x_values.get((i, j), 0) for i in client_range for j in deposit_range) + \
                    sum(m2.solution.get_value(beta[j, k]) * w_values.get((j, k), 0) for j in deposit_range for k in plant_range) > \
                    sum(transport_cost_deposit_client[j][i] * d[i] * x[i, j] for i in client_range for j in deposit_range) + \
                    sum(transport_cost_plant_deposit[j][k] * w[j, k] for j in deposit_range for k in plant_range):
                        m.add_constraint(sum(m2.solution.get_value(alpha[i, j]) * x[i, j] for i in client_range for j in deposit_range) + \
                                         sum(m2.solution.get_value(beta[j, k]) * w[j, k] for j in deposit_range for k in plant_range))


# Main model
def build_location_model(transport_cost_deposit_client, transport_cost_plant_deposit, p, q, d, **kwargs):
    m = Model(name='location', **kwargs)

    num_deposits = len(transport_cost_deposit_client)
    num_plants = len(transport_cost_plant_deposit[0])
    num_clients = len(d)
    
    deposit_range = range(num_deposits)
    plant_range = range(num_plants)
    client_range = range(num_clients)

    x = m.binary_var_matrix(client_range, deposit_range, name='x')
    w = m.integer_var_matrix(deposit_range, plant_range, name='w', lb=0)
    y = m.binary_var_list(deposit_range, name='y')
    h = m.binary_var_list(plant_range, name='h')

    m.add_constraints(m.sum(x[i, j] for j in deposit_range) == 1 for i in client_range)
    m.add_constraints(m.sum(w[j, k] for k in plant_range) == y[j] for j in deposit_range)
    m.add_constraints(x[i, j] <= y[j] for i in client_range for j in deposit_range)
    m.add_constraint(m.sum(h[k] for k in plant_range) == q)
    m.add_constraint(m.sum(y[j] for j in deposit_range) == p)
    m.add_constraints(m.sum(d[i] * x[i,j] for i in client_range) == m.sum(w[j, k] for k in plant_range) for j in deposit_range)
    m.add_constraints(w[j, k] <= (m.sum(d[i] for i in client_range) * h[k]) for j in deposit_range for k in plant_range)

    transport_cost = m.sum(transport_cost_deposit_client[j][i] * d[i] * x[i, j] for i in client_range for j in deposit_range) + \
                        m.sum(transport_cost_plant_deposit[j][k] * w[j, k] for j in deposit_range for k in plant_range)
    m.minimize(transport_cost)
    m.parameters.preprocessing.presolve = 0

    # Register the callback
    cut_cb = m.register_callback(CustomCutCallback)

    # Configure CPLEX parameters for cuts
    params = m.parameters
    params.mip.cuts.mircut = -1

    m.solve()

    return m



# Test function
def solve_model():
    num_deposits = 10
    num_plants = 4
    num_clients = 20

    TRANSPORT_COST_DEPOSITS_CLIENTS = [
        [random.randint(20, 100) for _ in range(num_clients)] for _ in range(num_deposits)
    ]

    TRANSPORT_COST_PLANTS_DEPOSITS = [
        [random.randint(30, 80) for _ in range(num_plants)] for _ in range(num_deposits)
    ]

    p = 5
    q = 3
    d = [random.randint(5, 20) for _ in range(num_clients)]

    m = build_location_model(TRANSPORT_COST_DEPOSITS_CLIENTS, TRANSPORT_COST_PLANTS_DEPOSITS, p, q, d)
    if m.solution is None:
        print("No valid solution found.")
        return None
    print(m.solution)
    return m


if __name__ == "__main__":
    solve_model()

• python
• optimization
• cplex
• docplex

Share Improve this question Follow asked Mar 29 at 19:13 JavierJavier 311 bronze badge 2

• Could you give some additional info on which issues you encounter, what your expected output would look like etc.? Thanks! – Cleb Commented Mar 30 at 4:30
• Hello I am trying to solve the problem by adding constraints based on the solution of the subproblem that I defined in the callback for each of the nodes in the branching tree. The problem is that it doesn't enter the callback, and I think I am not defining and solving the subproblem properly. Also, I'm not sure how to add the constraints to the original problem using the values from the subproblem's solution. Also there is one constraint that must be commented: m.add_constraints(m.sum(d[i] * x[i,j] for i in client_range) == m.sum(w[j, k] for k in plant_range) for j in deposit_range) THANKS – Javier Commented Mar 30 at 14:56

Add a comment  | 

1 Answer 1

Sorted by: Reset to default 1

Your basic model ("location") is infeasible. I ran your code with output on solve(log_output=True)

and it stops at once as infeasible. Hence the callback is never called. I suggest you modify the code to start from a feasible model, and then add the callbacks.

Here is the output I of the solve:

C:\python\anaconda202210\envs\docplex_dev38\python.exe C:\OPTIM\PYLAB\stackov\cutcb.py 
Model: location
 - number of variables: 254
   - binary=214, integer=40, continuous=0
 - number of constraints: 282
   - linear=282
 - parameters:
     parameters.mip.cuts.mircut = -1
     parameters.preprocessing.presolve = 0
 - objective: minimize
 - problem type is: MILP
Version identifier: 20.1.0.0 | 2020-11-10 | 9bedb6d68
CPXPARAM_Preprocessing_Presolve                  0
CPXPARAM_Read_DataCheck                          1
CPXPARAM_MIP_Cuts_MIRCut                         -1
Legacy callback                                  UD
Warning: Control callbacks may disable some MIP features.
Clique table members: 211.
MIP emphasis: balance optimality and feasibility.
MIP search method: traditional branch-and-cut.
Parallel mode: none, using 1 thread.
Root relaxation solution time = 0.00 sec. (0.23 ticks)

        Nodes                                         Cuts/
   Node  Left     Objective  IInf  Best Integer    Best Bound    ItCnt     Gap         Variable B NodeID Parent  Depth

      0     0    infeasible                                          2         

Root node processing (before b&c):
  Real time             =    0.00 sec. (1.57 ticks)
Sequential b&c:
  Real time             =    0.00 sec. (0.00 ticks)
                          ------------
Total (root+branch&cut) =    0.00 sec. (1.57 ticks)
No valid solution found.

Process finished with exit code 0

本文标签： pythonDocplex and callback problemsStack Overflow