如何借助IBM CPLEX Python API实现符合团队容量与前置依赖约束的迭代需求筛选方案

Hey there, let's break down your problem and fix those core pain points you're facing with CPLEX. The two main issues—optional variables not selecting any stories, and mandatory variables causing infeasibility—stem from missing key model components: a clear objective function, incorrect capacity constraint logic, and improper handling of optional variables in constraints.

1. Why Optional Variables Aren't Selecting Stories #

Right now, your model has no objective function to guide its decisions. CPLEX needs a goal to optimize—like maximizing the number of stories selected, or prioritizing higher story point values—otherwise, it has no incentive to pick any optional variables. The default behavior in this case is to select nothing, which trivially satisfies all constraints.

2. Fixing the Capacity Constraint Logic #

Your current capacity constraint approach is flawed. Instead of manually subtracting step functions, use CPLEX's cumul_function to track resource usage properly, and tie it to whether an optional story is selected. Since you need the total selected story points to exactly match the team's sprint capacity, we'll structure constraints to enforce this per iteration.

3. Properly Handling Optional Variables & Dependencies #

For optional interval variables, use presence_of() to check if a story is selected. When adding predecessor-successor dependencies, only enforce them if both the parent and child stories are included in the final selection.

Step-by-Step Implementation Fixes #

Let's rewrite your code with these corrections:

First, Add an Objective Function

Choose an objective that aligns with your priorities. For example, maximize the number of selected stories:

# Objective: Maximize the count of selected stories
mdl0.maximize(sum(presence_of(var) for var in dictIntrvalVars.values()))

Or if you want to prioritize higher story points (while still hitting capacity targets):

# Objective: Maximize total story points of selected stories
total_points = sum(
    presence_of(var) * int(dfAnalyzerOrg.loc[dfAnalyzerOrg['Stories'] == name, 'Story Points'].iloc[0]) 
    for name, var in dictIntrvalVars.items()
)
mdl0.maximize(total_points)

Correct the Capacity Constraint

Use cumul_function to track team capacity usage, and constrain total usage to exactly match each sprint's capacity:

NB_SPRINTS = 2
SPRINT_INTERVAL = 20  # Ensure this matches your time unit consistency (e.g., days)

for team, lst_team in dictTeamWise.items():
    # Get the team's capacity per sprint
    sprint_capacities = [
        dfTeamCapacity.loc[dfTeamCapacity['Team'] == team, s+1].iloc[0] 
        for s in range(NB_SPRINTS)
    ]
    
    # Create a cumulative function to track the team's capacity consumption
    team_usage = mdl0.cumul_function()
    
    # Add usage for each story only if it's selected
    for story_name, interval_var in lst_team:
        story_points = int(dfAnalyzerOrg.loc[dfAnalyzerOrg['Stories'] == story_name, 'Story Points'].iloc[0])
        # Tie story point usage to the presence of the interval variable
        team_usage += step_at_start(interval_var, story_points)
    
    # Enforce that total usage in each sprint exactly matches the capacity
    for sprint_idx in range(NB_SPRINTS):
        sprint_start = sprint_idx * SPRINT_INTERVAL
        sprint_end = (sprint_idx + 1) * SPRINT_INTERVAL
        mdl0.add(
            team_usage.at(sprint_end) - team_usage.at(sprint_start) == sprint_capacities[sprint_idx]
        )

Add Predecessor-Successor Dependencies

If you have a list of dependencies (e.g., a dataframe with Predecessor and Successor columns), enforce constraints only when both stories are selected:

# Example: Assume dfDependencies has columns 'Predecessor' and 'Successor'
for idx, dep_row in dfDependencies.iterrows():
    pred_story = dep_row['Predecessor']
    succ_story = dep_row['Successor']
    
    if pred_story in dictIntrvalVars and succ_story in dictIntrvalVars:
        pred_var = dictIntrvalVars[pred_story]
        succ_var = dictIntrvalVars[succ_story]
        
        # Only enforce end_before_start if both stories are selected
        mdl0.add(
            mdl0.implies(
                presence_of(pred_var) & presence_of(succ_var),
                end_before_start(pred_var, succ_var)
            )
        )

Fix Optional Variable Initialization

Ensure your optional variable logic is intentional. If you want all stories to be eligible for selection, set optional=True for all:

dictIntrvalVars = {}
for idx, row in dfAnalyzerOrg.iterrows():
    # Set all stories as optional (adjust if some are mandatory)
    is_optional = True  # Replace with your original logic if needed
    dictIntrvalVars[row['Stories']] = mdl0.interval_var(
        name=row['Stories'],
        size=int(row['Story Points']),
        optional=is_optional
    )

Additional Troubleshooting Tips #

• Infeasibility Checks: If the model remains infeasible, use CPLEX's conflict detection to identify problematic constraints:

  if not mdl0.solve():
      print("Model is infeasible. Running conflict detection...")
      mdl0.conflict_refine()
      print(mdl0.conflict())
  

• Relax Strict Capacity Rules: If "exact match" is too rigid, allow a small tolerance (e.g., >= capacity * 0.95 and <= capacity) if your business rules permit it.
• Time Unit Consistency: Ensure SPRINT_INTERVAL and interval variable size use the same time units (e.g., story points mapped to hours, or days).

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