7
$\begingroup$

I wrote a profit maximization LP with inventory, component usage, production, and machine hours constraints. When I optimize the model, it solves as expected. When applied towards a business case, however, the end user will generally look to make a handful of production changes rather than the several hundred the model suggests at once. I would like to modify the LP so that when a handful of recommendations from the optimal solution are applied to the baseline (i.e. increase maximum production qty of 5 products), the model only makes changes to the decision variables required to solve feasibly (i.e. reduction in production of a low or negative margin product, reduction in production to free up machine hours, etc.), rather than solving everything as optimal and making hundreds of changes.

Is there a way to incentivize the model to maintain baseline conditions and to only make the changes needed to solve feasibly?

Here's the objective:

enter image description here enter image description here

$\endgroup$
1
  • $\begingroup$ This is called persistence: don't change more than needed (or profitable). $\endgroup$ Nov 26, 2022 at 19:48

3 Answers 3

5
$\begingroup$

One approach is to introduce binary variables. Let $p_i$ be the variable determining production of item $i$ and $\bar{p}_i$ the planned/baseline production volume. We also need known lower and upper bounds $L_i$ (possibly 0) and $U_i$ for the volume of item $i$. Let binary variable $y_i$ indicate whether we are deviating from baseline on item $i$ or not. Add constraints $$p_i \le \bar{p_i} + (U_i - \bar{p}_i)y_i$$ and $$p_i \ge \bar{p_i} + (L_i - \bar{p}_i)y_i$$to define $y_i.$ One option is to set a fixed limit for the number of items changed, adding the constraint $$\sum_i y_i \le C$$ for some constant $C.$ Another is to subtract $\alpha \sum_i y_i$ from the objective function for some value $\alpha > 0.$ If your solver supports lexicographically ordered multiple objectives, a third possibility is to maximize profit and secondarily minimize $\sum_i y_i.$ Note that the choice of $C$ or $\alpha$ is arbitrary and may require some experimentation to produce results that make the boss happy (although you might be able to get a hard limit $C$ on changes from the Powers That Be).

$\endgroup$
4
  • $\begingroup$ This is exactly what I am looking for, what an interesting solution. Thank you so much! $\endgroup$
    – TroyE219
    Nov 27, 2022 at 14:19
  • $\begingroup$ But Prof Rubin, @prubin, wouldn't the solver make all Y's as 0, forcing no change from baseline if $\alpha \sum y_i$ is being minimized? Either there has to be a lower bound for Y or I am (thinking loud) bi-level optimization may help. $\endgroup$
    – Sutanu
    Nov 27, 2022 at 16:18
  • $\begingroup$ @Sutanu: You are not minimizing $\alpha \sum y_i,$ you are maximizing $\sum (p_i r_i - \alpha y_i)$ where $p$ is the production quantity and $r$ is the unit profit. If you make $\alpha$ too large, then yes, the solver will freeze the schedule, but not if you are careful in your choice of $\alpha.$ $\endgroup$
    – prubin
    Nov 27, 2022 at 16:53
  • $\begingroup$ Thanks prof. Makes sense. $\endgroup$
    – Sutanu
    Nov 27, 2022 at 17:00
5
$\begingroup$

This is indeed often an issue when dealing with an industrial/real-life problem.

One way of handling this is as follows. First, create a baseline which reproduces the existing system. So when you solve your optimization problem, it is constrained so as to maintain baseline conditions. You can, for example, only define the variables with values equal to the existing baseline.

Then, gradually, add new variables to allow the solver some diversification. You can control the amount of new variables that you put in the system, and this way, you can "keep close" to the baseline if you wish to.

As an example, in a logistics problem, for your baseline, you only define existing flows. Then, you can gradually add non existing flows and see how the solver reacts, and how far off you end up from the baseline. You can iteratively constrain the model in order to identify some optimizations, while maintaining (constraining) some variables to their value in the baseline.

Note that in this case, you are not trying to find the global optimal solution. You are looking for a local optimal solution, which is better than your baseline, and which satisfies your customer. This is an iterative process.

$\endgroup$
1
  • $\begingroup$ Thank you for the quick reply! The iterative approach that you suggest would certainly work, though it's a bit more manual of a process than I was hoping for. I was thinking along the lines of a multi-objective LP, with production qty as the primary and profit as the secondary though I don't think this would work exactly. Anything in terms of the model that I can tweak? If I modify a production variables quantity and the model came back infeasible, I could of course change the equality sign on the lowest margin product to free up machine hours or raw material...though this wouldn't be ideal. $\endgroup$
    – TroyE219
    Nov 26, 2022 at 16:14
2
$\begingroup$

Couple of ways to keep the model close to the baseline:
1> Define something like $d^+$ and $d^-$ as deviations from the baseline objective and try to solve by minimizing the sum of deviations. You can put baseline objective as a constraint.
2> Sensitivity analysis will identify the slacks/surpluses which can imply certain changes need not be implemented while maintaining feasibility/optimality.
3> Constrained programming: No objective, just solves to feasibility.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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