Linear programming: Can objective variable have a constraint?

Question

I am having an issue with a LP problem. I'll first try to explain the problem in a simplified way, before explaining the issues.

Basic problem

Suppose I have three types of machines, all of which can only be operational for two periods of times (T1, T2, T3, or T4), as is indicated by the ones in the below matrix.

Machine T1    T2    T3   T4    Amount 
M1      0     1     1    0     x1     
M2      1     1     0    0     x2     
M3      0     0     1    1     x3

Each machine can produce any amount of items (x1 to x3; the variables). This is needed to achieve a MIMINUM required production per time period:

            T1  T2  T3  T4
Required    2   3   1   1

To solve this problem, we need:

M2 to produce 2,
M3 to produce 1,
either M1 or M2 to produce 1, with the effect that one too many is produced at T3 or T1 respectively.

which may result in:

Machine T1    T2    T3   T4    Amount 
M1      0     0     0    0     0     
M2      3     3     0    0     3     
M3      0     0     1    1     1      

prod    3     3     1    1
Requ    2     3     1    1

Constraints

Production during T1 and T4 is not preferrable and should be punished. In the above example, this would mean that M1 should be used to produce.

In simple wording, the problem states to produce at least the required amount, but minimize any excess (especially in T1 and T4).

This can be done in two ways:

The machines operational during these periods are punished (Punishment by M; M2 and M3).
The production per time period is punished (Punished by T; T1 and T4)

This would look as follows:

Machine T1    T2    T3   T4    Amount   Pm
M1      0     1     1    0     x1       0
M2      1     1     0    0     x2       0.5
M3      0     0     1    1     x3       0.5

Pt      0.5   0     0    0.5

Issue: I can only get the punishment per machine to work properly. Punishment by time is not infeasible, but gives incorrect output (way too many redundant machines).

Attempt and outcome

I first programmed the solver with a punishment by m (Pm). The objective function (in Python pulp) here is:

amount = LpVariable.dicts("amount_",Machine,0,100000,LpInteger)
product_t = LpVariable.dicts("product_",time,0,100000,LpInteger)


prob += lpSum([amount[m]*(1+Pm[m]) for m in Machine]) # minimize

# constraint
for t in time:
    # production per time period; matrix[m,t] is the matrix with ones shown above
    product_t[t] = lpSum([amount[m] * matrix[m,t] for m in machine])
    # production must be higher than required. 
    prob += product_t[t] >= req[t]

The outcome in this situation would be (Machine, production, punishment): M1 * 1 * (0+1) + M2 * 2 * (0.5+1) + M3 * 1 * (0.5+1) = 5.5 compared to the suboptimal solution: M1 * 0 * (0+1) + M2 * 3 * (0.5+1) + M3 * 1 * (0.5+1) = 6

Following, because this approach has some downsides in the real situation, I wanted to calculate it with punishment by t (Pt).

prob += lpSum([product_t[t]*(1+Pt[t]) for t in time]) #minimize

for t in time:  # same calculation of product_t and constraint as above
    product_t[t] = lpSum([amount[m] * matrix[m,t] for m in machine])
    prob += inzet_t[t] >= nodig[t]

This approach, however, gives me a feasible but incorrect output (production = 0.0).

Question

How is it possible that, with exactly the same constraints, the punishment by time does not work? Is it not allowed that the objective function contains a variable (product_t) with a constraint?

Robin Kramer Robin Kramer · Accepted Answer · 2017-11-21T08:17:51

I was starting to disect the code more and more and found out the following: amount and product_t were defined in the same way. However, saying amount[m].varValue is possible, but saying product_t[t].varValue was not (LpAffineExpression has no attribute called varValue). Instead, I had to say value(product_t[t]). I think this is because amount is used to calculate product_t, and product_t is thus a different kind of variable. So I knew I had to look at the use of product_t in the objective formula

Attempt 1: failed but it was a longshot

prob +=  lpSum([value(product_t[t])*Pt[t] for t in time  ]) #added value() 
# Error: Unsupported operant * for NoneType and float`

Attempt 2: was a success.

In the goal function prob += lpSum([product_t[t]*(1+Pt[t]) for t in time]) #minimize I replaced product_t with the formula to calculate it. So, the objective function was:

prob += lpSum([product_t[t]*(1+Pt[t]) for t in time]) #OLD

and became

prob += lpSum([lpSum([amount[i] * timeblock_matrix[i,t] for i in dienst])*Pt[t] for t in time]) #NEW, minimize

If one could explain why it works like, why it cannot have an intermediate LpVariable, that would be greatly appreciated.

Linear programming: Can objective variable have a constraint?

Question

2 Answers