基于选择矩阵的员工最优匹配需求咨询（140人配对场景）

Problem Recap #

We have 140 employees, each with a ranked list of 8 preferred meeting partners. Our goal is to assign ~5 meeting partners per employee, maximizing the number of high-priority preferences that are satisfied. This is a classic weighted bipartite b-matching problem where each node (employee) has a "demand" of 5 matches, and edges are weighted by preference rank (higher weight = more preferred).

Step 1: Reshape Your Excel Data #

First, convert your wide-format data (each row = employee + 8 choices) into a long-format table that’s easier to work with for optimization:

• Use Power Query (Data > Get & Transform Data > From Table/Range) to unpivot the preference columns (B through I).
• Add a Weight column: Assign 8 to first-choice matches, 7 to second, ..., 1 to eighth-choice. This weights higher preferences more heavily in our objective.
• Remove any rows where the preferred partner is the same as the employee (no self-meetings).

Your final table should look like this:

Step 2: Solve Using Excel Solver (For Smaller Datasets) #

If you prefer staying within Excel, you can use the built-in Solver add-in. Note: For 140 employees, this might be slow due to the number of variables, but it’s doable with some optimizations.

Set Up the Model #

1. Create a binary decision matrix: A 140x140 grid where cell X[i][j] is 1 if employee i is matched with employee j, 0 otherwise.
2. Objective Function: Calculate the total weighted satisfaction by summing X[i][j] * Weight[i][j] for all pairs. Use SUMPRODUCT for this.
3. Constraints:
   • For each row i, SUM(X[i][*]) = 5 (or allow 4-6 if you need flexibility on the "约5" requirement).
   • X[i][j] = X[j][i] (matches are mutual—if Alice is matched with Bob, Bob must be matched with Alice).
   • X[i][i] = 0 (no self-meetings).
   • All X[i][j] are binary (0 or 1).

Run Solver #

• Go to Data > Solver.
• Set the objective to maximize the total weighted satisfaction.
• Add the constraints listed above.
• Choose the Evolutionary solver (best for integer programming problems with large variable counts).
• Click Solve.

Step 3: Solve Using Python (For Larger/Smoother Performance) #

For 140 employees, Python with a linear programming library will be much faster and more reliable. Here’s a solution using the PuLP library:

Install PuLP #

First, install the library via pip:

pip install pulp

Code Snippet #

import pulp
import pandas as pd

# Load your reshaped Excel data (from Step 1)
df = pd.read_excel("employee_preferences.xlsx")

# Get unique employees and map to indices for easier handling
employees = df["Employee"].unique()
emp_idx = {emp: idx for idx, emp in enumerate(employees)}
num_emps = len(employees)

# Initialize the maximization problem
prob = pulp.LpProblem("EmployeeMeetingMatcher", pulp.LpMaximize)

# Create binary decision variables (only i < j to avoid duplicate pairs)
matches = pulp.LpVariable.dicts(
    "Match",
    [(i, j) for i in range(num_emps) for j in range(i+1, num_emps)],
    cat="Binary"
)

# Define objective: Maximize total weighted preference satisfaction
total_weight = pulp.lpSum(
    df[(df["Employee"] == employees[i]) & (df["Preferred Partner"] == employees[j])]["Weight"].values[0] * matches[(i,j)]
    for i in range(num_emps)
    for j in range(i+1, num_emps)
    if not df[(df["Employee"] == employees[i]) & (df["Preferred Partner"] == employees[j])].empty
)
prob += total_weight

# Add constraint: Each employee gets exactly 5 matches
for i in range(num_emps):
    emp_matches = []
    # Sum all pairs involving employee i
    for j in range(num_emps):
        if i < j:
            emp_matches.append(matches[(i,j)])
        elif j < i:
            emp_matches.append(matches[(j,i)])
    prob += pulp.lpSum(emp_matches) == 5, f"MatchCount_{employees[i]}"

# Solve the problem (suppress verbose output)
prob.solve(pulp.PULP_CBC_CMD(msg=False))

# Generate and save the final match list
final_matches = []
for (i,j) in matches:
    if pulp.value(matches[(i,j)]) == 1:
        final_matches.append((employees[i], employees[j]))

pd.DataFrame(final_matches, columns=["Employee A", "Employee B"]).to_excel("final_meeting_matches.xlsx", index=False)

Validation & Adjustments #

• After solving, verify that each employee has exactly (or approximately) 5 matches.
• Check the distribution of preference ranks in the final matches—most should be from the top 3-4 choices if the model worked correctly.
• If you need more flexibility (e.g., allowing 4-6 matches instead of exactly 5), adjust the constraint values in either Excel Solver or the Python code.

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