Docplex用户割回调方法的Python Notebook示例及LP根节点通用获取方法咨询

Let’s walk through a complete, practical example of implementing a user cut callback for the Asymmetric Traveling Salesman Problem (ATSP) using Docplex. We’ll focus on subtour elimination cuts (a common valid inequality for TSP/ATSP) and clarify how to detect the root node and add cuts dynamically.

Step 1: Import Required Libraries #

First, we’ll import Docplex modules and NetworkX (to simplify subtour detection—you can implement this without NetworkX if needed, but it saves time for demonstration).

from docplex.mp.model import Model
from docplex.mp.callbacks import UserCutCallback
import networkx as nx
import numpy as np

Step 2: Define the ATSP Instance #

Let’s create a small, reproducible ATSP instance with 5 nodes and random asymmetric costs.

# Number of nodes
n = 5

# Generate random cost matrix (asymmetric)
np.random.seed(42)  # For consistent results
cost_matrix = np.random.randint(1, 20, size=(n, n))
# Set diagonal values to a large number (no self-travel allowed)
np.fill_diagonal(cost_matrix, 1000)

# Node indices
nodes = list(range(n))

Step 3: Build the Initial LP Model #

We’ll set up the core model with decision variables, objective function, and basic flow conservation constraints.

# Initialize model
mdl = Model(name="ATSP_with_user_cuts")

# Decision variables: x[i,j] = 1 if we travel from node i to j, 0 otherwise
x = mdl.binary_var_matrix(nodes, nodes, name="x")

# Objective: Minimize total travel cost
mdl.minimize(mdl.sum(cost_matrix[i][j] * x[i,j] for i in nodes for j in nodes))

# Flow conservation constraints: Each node has exactly one incoming and one outgoing edge
for i in nodes:
    # Outgoing edges
    mdl.add_constraint(mdl.sum(x[i,j] for j in nodes if j != i) == 1, name=f"out_flow_{i}")
    # Incoming edges
    mdl.add_constraint(mdl.sum(x[j,i] for j in nodes if j != i) == 1, name=f"in_flow_{i}")

Step 4: Implement the User Cut Callback #

We’ll create a custom callback class that inherits from UserCutCallback. This callback will:

1. Check if we’re at the root LP node.
2. Extract the current fractional solution.
3. Detect subtours in the solution.
4. Add subtour elimination cuts to break those subtours.

class ATSPUserCutCallback(UserCutCallback):
    def __init__(self, model, x_vars, nodes):
        super().__init__(model)
        self.x = x_vars
        self.nodes = nodes
        self.n = len(nodes)
        self.epsilon = 1e-6  # Threshold for considering an edge as "active" in the solution
    
    def add_cuts(self):
        # Only generate cuts at the root node (adjust if you want cuts at other nodes)
        if self.is_root_node():
            print("Processing root node, generating user cuts...")
            
            # Get current LP solution values for x variables
            sol = self.get_current_solution()
            x_vals = {(i,j): sol.get_value(self.x[i,j]) for i in self.nodes for j in self.nodes}
            
            # Build directed graph from the fractional solution
            G = nx.DiGraph()
            G.add_nodes_from(self.nodes)
            for i in self.nodes:
                for j in self.nodes:
                    if i != j and x_vals[(i,j)] > self.epsilon:
                        G.add_edge(i, j, weight=x_vals[(i,j)])
            
            # Find all strongly connected components (SCCs) in the graph
            sccs = list(nx.strongly_connected_components(G))
            
            # Add subtour elimination cuts for each non-trivial SCC
            for scc in sccs:
                if len(scc) < self.n and len(scc) > 0:
                    # Cut constraint: sum of edges leaving the SCC must be at least 1
                    cut_expr = mdl.sum(self.x[i,j] for i in scc for j in self.nodes if j not in scc)
                    cut_ct = mdl.add_constraint(cut_expr >= 1, name=f"subtour_cut_{scc}")
                    
                    # Add the constraint as a user cut
                    self.add_user_cut_constraint(cut_ct)
                    print(f"Added subtour cut for component: {scc}")

Key Details Clarified: #

• Root Node Detection: self.is_root_node() tells us when we’re at the initial LP root node—this is where we typically add our first set of cuts.
• Solution Access: self.get_current_solution() gives us access to the fractional values of our variables at the current node.
• Cut Addition: self.add_user_cut_constraint(cut_ct) adds the generated constraint directly to the model for the current node (no need to pass the root node explicitly—this is handled automatically by the callback context).

Step 5: Register the Callback and Solve #

Now we’ll attach our callback to the model and run the solver.

# Create callback instance
callback = ATSPUserCutCallback(mdl, x, nodes)

# Register the callback with the model
mdl.register_callback(callback)

# Solve the model (enable log output to see cut activity)
solution = mdl.solve(log_output=True)

# Print results if a solution is found
if solution:
    print("\nOptimal Solution Found:")
    print(f"Total Cost: {solution.objective_value:.2f}")
    print("Route:")
    # Reconstruct the optimal route from the solution
    current_node = 0
    route = [current_node]
    for _ in range(n-1):
        for j in nodes:
            if solution.get_value(x[current_node,j]) > 0.9:
                current_node = j
                route.append(current_node)
                break
    print(" -> ".join(map(str, route)))
else:
    print("No valid solution found.")

Customization Tips #

• Cut Types: Replace subtour elimination cuts with any valid inequalities relevant to your problem (e.g., lifted cuts, path constraints).
• Non-Root Cuts: Remove the if self.is_root_node() check to generate cuts at all nodes, but be aware this may increase computation time.
• Efficiency: For large instances, use a more optimized subtour detection method (the NetworkX approach works well for small-to-medium problems).

内容的提问来源于stack exchange，提问作者pudu39