使用Gurobi求解多最优解时出现重复结果的问题及解决方法

Hey there! The duplicate optimal solutions you're seeing are almost certainly due to symmetry in your graph model (Gurobi generates equivalent solutions when nodes/edges are interchangeable) or small gaps in how you're filtering and collecting solutions. Let's fix this step by step:

1. Tweak Gurobi Parameters to Prioritize Distinct Optimal Solutions #

First, adjust your parameters to ensure Gurobi only collects true optimal solutions and avoids redundant ones during the search:

m.Params.PoolSearchMode = 2  # Systematic search for all optimal solutions
m.Params.PoolSolutions = 1000  # Set a higher limit to capture more potential unique solutions
m.Params.PoolGap = 0.0  # Only keep solutions with objective value equal to the global optimum
m.Params.PoolReplace = 1  # Prioritize adding new distinct solutions over duplicates when the pool is full

The PoolReplace=1 parameter tells Gurobi to swap out existing duplicate solutions in the pool for new unique ones once it hits the PoolSolutions limit.

2. Break Symmetry in Your Graph Model (Critical Fix) #

Graphs often have symmetric structures (e.g., identical nodes or edges) that lead Gurobi to generate duplicate solutions. Add symmetry-breaking constraints to eliminate these. For example:

• If you're selecting a node set, pick a "reference" node (like the lowest-indexed node) and enforce an order relative to other nodes to prevent permutation duplicates:

  # Example: Ensure node 1 is only included if node 0 is included (adjust based on your problem logic)
  m.addConstr(b[(0, target_edge)] <= b[(1, target_edge)])
  

• Alternatively, enforce lexicographical ordering on your binary variables to block symmetric solution permutations.

3. Fix Your Solution Collection & Deduplication Logic #

Your current code has minor issues in filtering and collecting solutions. Here's the revised version with built-in deduplication:

m.Params.PoolSearchMode = 2
m.Params.PoolSolutions = 1000
m.Params.PoolGap = 0.0
m.Params.PoolReplace = 1

b = m.addVars(Edges, vtype=GRB.BINARY, name="b")
# ... rest of your model setup ...

if m.status == GRB.Status.OPTIMAL:
    optimal_obj = m.ObjVal  # Store the global optimal objective value
    unique_optimal_sets = set()  # Use a set to automatically deduplicate solutions

    for sol_num in range(m.SolCount):
        m.setParam(GRB.Param.SolutionNumber, sol_num)
        # Skip non-optimal solutions (redundant with PoolGap=0, but safe for numerical edge cases)
        if abs(m.PoolObjVal - optimal_obj) > 1e-6:
            continue
        
        # Extract the node set for this solution
        current_set = []
        for e in Edges:
            # Use a threshold for binary variables to avoid floating point precision issues
            if b[e].Xn > 0.5:
                # Extract node ID from variable name (adjust parsing logic if your naming differs)
                node_id = int(b[e].varname[0:2])
                if b[e].varname[2:] == f"{External_node}":
                    current_set.append(node_id)
        
        # Convert to sorted tuple so [1,2,3] and [3,2,1] are treated as the same set
        current_set_tuple = tuple(sorted(current_set))
        unique_optimal_sets.add(current_set_tuple)
    
    # Convert back to list of lists if your use case requires it
    optimal_sets = [list(s) for s in unique_optimal_sets]
    # Optional: Limit to 100 unique solutions if needed
    optimal_sets = optimal_sets[:100]
    return optimal_sets

Key improvements here:

• We use a set with sorted tuples to deduplicate solutions (node order doesn't matter for node sets, so sorting ensures equivalent sets are treated as one).
• A threshold (>0.5) for binary variable values avoids false positives from floating point precision errors.
• We use a small epsilon when comparing objective values to handle minor numerical discrepancies.

4. Verify Uniqueness #

After collecting solutions, you can check the length of unique_optimal_sets to confirm you're getting distinct node sets.

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