I have a linear model which simulates a production system over a time horizon. The system is composed of production units with on/off state and minimum up/down constraints, i.e. a unit cannot change state after switching for a given number of periods. The objective is to minimize the total production cost over the horizon. Production levels can vary continuously between a minimum and a maximum specific to each unit.

I compute a heuristic solution in the following way: first I approximate optimal production levels with a continuous relaxation, then I compute values for integer variables by solving integer subproblems.

The continuous relaxation, on which the quality of the heuristic solution depends, doesn't account for minimum up/down constraints.

Furthermore, in practice, the units and the rest of the system expect production levels with low variance, defined as the difference between production levels of the same unit in subsequent periods. This requirement is hard to formalize and is not included into the model yet, thus I'm looking for a "soft" representation.

I'd like to have the continuous relaxation account for the low variance requirement in order to improve the quality of the heuristic solution, and, perhaps, improve the gap between the two solutions w.r.t. minimum up/down constraints.

One possible way of obtaining this is to model the problem as a 2-objective program and optimize hierarchically first the original objective, the total cost of production over the horizon, and then, bounding changes to the first objective value, the variance of production levels, either as a total or maximum over units.

I was looking for some ideas in the literature but there are lots of false positives due to the overloaded terms as "variance", "difference", "variation"....

Can you suggest some references, ideas or considerations on minimizing variance of continuous variable values in LP solutions?


Thanks to both Philipp and Paul for the answers. I need to clarify a couple of details. The model is large so we're already using IPM and Philipp's answer may explain why the gap we got with the heuristic was lower than expected, based on an "on-the-fly"/"rule-of-thumb" consideration .

I don't think Paul's solution could be easily applied to my case since it requires some tuning by either me or the users and it is hard to decide the trade-off between variance and global costs. It is a scenario simulation problem so we don't work with real data, only on some statistics and forecasting, and variance's actual costs are hard to measure.

However I'm going to try the two-objective approach and use some penalizing terms determined by the minimum up/down costraints of each unit, so that the most inflexible plants end up having less variance. Just for curiosity's sake, does someone know any reference in the literature for this kind of problem or Paul's and mine approach?

asked 06 Oct '14, 09:46

Andrea%20T's gravatar image

Andrea T
accept rate: 0%

edited 09 Oct '14, 05:51

Maybe you can solve your linear problems using an IPM (without crossover) thus getting a naturally less "extreme" solution. The result of an IPM solve tends to have more variables in between their bounds instead of on them, for variables with the same bounds that will reduce the variance in a natural way.

One way to do this would be to solve your mixed integer problem using a standard MILP solver, then take the solution and fix the integer variables, resolve with an IPM (without crossover). The (unfixed) continuous variables from the IPM solve will have less extreme values than the ones coming from the MILP solve, since the MILP solution will most likely come from a simplex solve or some heuristic. This maintains optimality, you just get a different (degenerate) continous part of your solution. If your integer variables force continuous variables to their bounds, which happens a lot, then you are out of luck with this.

Here something I wrote about the IPM that might explain this a bit more: https://www.or-exchange.org/questions/9720/when-should-i-use-interior-point-methods


answered 06 Oct '14, 10:06

Philipp%20Christophel's gravatar image

Philipp Chri...
accept rate: 22%

Good answer!

Actually since it's a large MILP we're already using IPM for the continuous relaxation and without the crossover step to save time, but yours is a pretty good point!

I'll look deeper in our current solution then!

(06 Oct '14, 10:24) Andrea T

What about adding a variable to the continuous relaxation representing the maximum variation in consecutive output levels of any unit in consecutive periods (easy to enforce via linear constraints), and then adding that variable to the objective function of the relaxation with a penalty multiplier? One option is to do some experimentation and then fix a penalty value that seems to fit your needs. Another, if the relaxation solves quickly, might be to solve the relaxation for a range of penalty values and then pick one solution based on some criterion.


answered 06 Oct '14, 16:59

Paul%20Rubin's gravatar image

Paul Rubin ♦♦
accept rate: 19%

See my edit above

(09 Oct '14, 05:25) Andrea T

Since you are already using an IPM, you might want to consider adding one or more quadratic constraints to the model. If \(x_{i,t}\) is production of item \(i\) at time \(t\), you could either constrain \(\left(x_{i,t}-x_{i,t+1}\right)^2 \le K_{i} \ \forall i,t\) or \(\sum_{t}\left(x_{i,t}-x_{i,t+1}\right)^2 \le K_{i} \ \forall i\).


answered 09 Oct '14, 10:54

Paul%20Rubin's gravatar image

Paul Rubin ♦♦
accept rate: 19%

Your answer
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here



Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "Title")
  • image?![alt text](/path/img.jpg "Title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported



Asked: 06 Oct '14, 09:46

Seen: 1,627 times

Last updated: 09 Oct '14, 10:54

OR-Exchange! Your site for questions, answers, and announcements about operations research.