1
$\begingroup$

I'm running into an issue with a Linear Optimization Problem. The ultimate goal is to come back with an optimal production quantity (prod_qty) across several items and weeks.

Now, the problem is the following: As part of the optimization problem I know the demand per item and week. When solving for prod_qty, I want to minimize both excess (prod_qty - demand > 0) and unmet demand (demand- prod_qty > 0).

Here's why this becomes difficult: For some items, I don't want my solver to meet any unmet demand in a given week later in my solve horizon. Essentially, when in a week $w$ I cannot meet demand, I just want to forget about that in the next week. So in the next week, I would not include last week's unmet demand when calculating the new unmet demand or excess. However, if I have created excess in a given week - in the next week the optimizer has to "remember" that excess was available, hence include that in the calculation of the next week's excess or unmet demand. There are other items for which this is not the case and any unmet demand can be carried forward. I can have a situation where two items are produced concurrently, but for one of them, the demand can be carried forward, for the other it cannot.

I can't seem to find a way to specify the excess and unmet demand variables correctly and wonder if it's even possible in a convex optimization framework?

I have tried several things along the lines of the code below. Interestingly, the excess (balance_pos) and unmet demand come out in a sensible way with objective function 1 below. Note how for items that can't carry unmet demand forward this objective function does not try to minimize the penalties due to unmet demand. As soon as I activate that piece in objective function 2, the obtained excess and unmet go all over the place even though the obtained optimal prod_qty seems to be the same as before:

balance_pos = cp.Variable(prod_qts.shape, nonneg=True)
unmet_pos = cp.Variable(prod_qts.shape, nonneg=True)

balance_dummy = cp.Variable(prod_qts.shape, boolean = True)

M = 1000000

constraints.extend([balance_pos >=  0])
constraints.extend([unmet_pos >=  0])

for dte in range(prod_qts.shape[0]):
    if dte == 0: 
        constraints.extend([prod_qts[0,:] - dmd_mtrx[0,:] <= M *  balance_dummy[0,:]])
        constraints.extend([dmd_mtrx[0,:] - prod_qts[0,:] <= M * (1 - balance_dummy[0,:]) -1])
        constraints.extend([balance_pos[0,:] >= (prod_qts[0,:] - dmd_mtrx[0, :]) - M * (1-balance_dummy[0,:])])
        constraints.extend([unmet_pos[0,:] == (dmd_mtrx[0, :] - prod_qts[0,:]) - M * balance_dummy[0,:]])

    else:  
        constraints.extend([balance_pos[dte-1,:] + prod_qts[dte,:] - dmd_mtrx[dte,:] <= M *  balance_dummy[dte,:]])
        constraints.extend([dmd_mtrx[dte,:] - prod_qts[dte,:] - balance_pos[dte-1,:] <= M * (1 - balance_dummy[dte,:]) -1])
        constraints.extend([balance_pos[dte,:] >= (balance_pos[dte-1,:] + prod_qts[dte,:] - dmd_mtrx[dte, :]) - M * (1-balance_dummy[dte,:])])
        constraints.extend([unmet_pos[dte,:] >= (dmd_mtrx[dte, :] - balance_pos[dte-1,:] - prod_qts[dte,:])- M * balance_dummy[dte,:]])

objective_1 = cp.Minimize(

       cp.sum(balance_pos) + cp.sum(unmet_pos)

        +


        cp.sum(

            cp.multiply(

                cp.atoms.elementwise.maximum.maximum(

                    (cp.atoms.affine.cumsum.cumsum(prod_qts[:,carry_forward_idx], axis=0) - cum_item_day_demand[:,carry_forward_idx]),  0),

                            storage_costs[:, carry_forward_idx])

        ) +

        cp.sum(

            cp.multiply(balance_pos[:,no_carry_forward_idx],

                        storage_costs[:, no_carry_forward_idx])

        ) +               

        cp.sum(

            cp.multiply(cp.atoms.elementwise.maximum.maximum(

                (cum_item_day_demand[:,carry_forward_idx] - cp.atoms.affine.cumsum.cumsum(prod_qts[:, carry_forward_idx], axis=0)),

                0), ind_dmd_panalties_mtrx[:, carry_forward_idx])

        ) 

        # +
        # cp.sum(
        #     cp.multiply(unmet_pos[:, no_carry_forward_idx], 
        #                 ind_dmd_panalties_mtrx[:, no_carry_forward_idx])
        # ) 

    )

problem = cp.Problem(objective_1, constraints)
problem.solve()

res_1 = pd.DataFrame({"excess": balance_pos.value[:,0],

                      "unmet": unmet_pos.value[:,0],

                      "prod":prod_qts.value[:,0]})

res_1

>>> res_1
     excess         unmet          prod
0       0.0     -0.000000      0.000000
1       0.0   4852.224000      0.000000
2       0.0  71570.304000      0.000000
3       0.0  67793.792204  18333.183796
4       0.0  92192.256000      0.000000
..      ...           ...           ...
102     0.0      0.000000  62472.384000
103     0.0      0.000000  67931.136000
104     0.0      0.000000  75816.000000
105     0.0      0.000000  50341.824000
106     0.0      0.000000      0.000000

objective_2 = cp.Minimize(

       cp.sum(balance_pos) + cp.sum(unmet_pos)

        +

        cp.sum(

            cp.multiply(

                cp.atoms.elementwise.maximum.maximum(

                    (cp.atoms.affine.cumsum.cumsum(prod_qts[:,carry_forward_idx], axis=0) - cum_item_day_demand[:,carry_forward_idx]),  0),

                            storage_costs[:, carry_forward_idx])

        ) +

        cp.sum(

            cp.multiply(balance_pos[:,no_carry_forward_idx],

                        storage_costs[:, no_carry_forward_idx])

        ) +               

        cp.sum(

            cp.multiply(cp.atoms.elementwise.maximum.maximum(

                (cum_item_day_demand[:,carry_forward_idx] - cp.atoms.affine.cumsum.cumsum(prod_qts[:, carry_forward_idx], axis=0)),

                0), ind_dmd_panalties_mtrx[:, carry_forward_idx])

        ) 

        +

        cp.sum(

            cp.multiply(unmet_pos[:, no_carry_forward_idx], 

                        ind_dmd_panalties_mtrx[:, no_carry_forward_idx])

        ) 

    )

# create problem and solve

problem = cp.Problem(objective_2, constraints)
problem.solve()

res_2 = pd.DataFrame({"excess": balance_pos.value[:,0],
                      "unmet": unmet_pos.value[:,0],
                      "prod":prod_qts.value[:,0]})
res_2

>>> res_2
           excess  unmet          prod
0     4852.224000   -0.0      0.000000
1    71570.304000    0.0      0.000000
2    67793.792204    0.0      0.000000
3    92192.256000    0.0  18333.183796
4    72783.360000    0.0      0.000000
..            ...    ...           ...
102      0.000000    0.0  62472.384000
103      0.000000    0.0  67931.136000
104      0.000000    0.0  75816.000000
105      0.000000    0.0  50341.824000
106      0.000000    0.0      0.000000

Any advice on how to correctly specify this problem to arrive at reliable results would be welcome.

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ Is it possible to share the whole mathematical model you have tried to formulate? (I mean in the Mathjax format) $\endgroup$
    – A.Omidi
    Commented Nov 9, 2021 at 14:15
  • $\begingroup$ Your last two constraints in each part of the loop, define the relationship between the excess and unmet of the next period, but what is the purpose of the first two? Also, this is related to your question on StackOverflow $\endgroup$
    – EhsanK ♦
    Commented Nov 9, 2021 at 14:25

1 Answer 1

Reset to default
2
$\begingroup$

If your costs are linear, there is no need to introduce binary variables or big-M constraints here. Define three sets of nonnegative decision variables:

  • $I_t$ is the inventory at the end of period $t$
  • $P_t$ is the production in period $t$
  • $B_t$ is the unmet demand in period $t$

Let $d_t$ be the demand in period $t$. The inventory balance constraints are $$I_{t-1}+P_t+B_t=d_t+I_t+B_{t-1}$$ In periods where you don’t allow previously unmet demand to be satisfied, just omit the $B_{t-1}$ term.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.