GLPK使用变量限制求和时的约束定义问题

Let's walk through what's wrong with your current constraint and how to fix it to correctly calculate the total cumulative time up to each task's completion.

What's Wrong with the Original Constraint? #

Your accumulative_times constraint has a critical issue that makes it incompatible with integer/linear programming solvers:

s.t. accumulative_times{i in JOBS}: actimes[i] = sum{j in PLACES,k in JOBS : j <= placing[i] } t[k,j]*time[k];

The core problem is that you're using a variable (placing[i]) as part of the summation's filter condition (j <= placing[i]). In mathematical programming, summation ranges must be fixed (based on predefined sets, not variables) to keep constraints linear. When you use a variable to define which terms are included in the sum, the constraint becomes non-linear and non-convex—standard solvers can't process this.

To align on your variable logic:

• t[j,k] is binary: t[j,k] = 1 means task k is assigned to position j
• placing[k] gives the position of task k (via placing[k] = sum{j} j*t[j,k])
• Your goal is to calculate actimes[i] as the total time of all tasks scheduled at or before the position of task i (i.e., cumulative time up to when task i finishes).

A Linear, Solver-Friendly Solution #

The cleanest way to model this is to use a recursive cumulative time variable for each position, then map that to each task's completion time. Here's how to adjust your model:

Step 1: Add a Cumulative Time Variable #

Define a variable cum_time[j] that represents the total cumulative time up to and including position j:

var cum_time{PLACES} integer;

Step 2: Define Recursive Constraints for Cumulative Time #

Calculate the cumulative time for each position using linear constraints:

• For the first position, cumulative time is just the time of the task assigned there
• For subsequent positions, add the current task's time to the previous position's cumulative time

# Cumulative time for the first position
s.t. cum_time_first: cum_time[1] = sum{k in JOBS} t[1,k] * time[k];

# Cumulative time for positions 2 to n (recursive step)
s.t. cum_time_recursive{j in PLACES where j > 1}:
    cum_time[j] = cum_time[j-1] + sum{k in JOBS} t[j,k] * time[k];

Step 3: Map Cumulative Time to Each Task's actimes #

Since t[j,i] = 1 when task i is in position j, we can set actimes[i] equal to the cumulative time of the position where task i is scheduled:

s.t. actimes_def{i in JOBS}:
    actimes[i] = sum{j in PLACES} cum_time[j] * t[j,i];

Alternative: Calculate Start Time Instead of Completion Time #

If you wanted actimes[i] to be the start time of task i (total wait time before the task begins), just adjust the final constraint to subtract the task's own time:

s.t. start_time_def{i in JOBS}:
    actimes[i] = sum{j in PLACES} (cum_time[j] - time[i]) * t[j,i];

Why This Works #

All constraints here are linear, which integer programming solvers can handle efficiently. The recursive cum_time approach avoids variable-dependent summation ranges and directly models the cumulative time flow through the schedule positions.

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