I'm trying to set up a linear program in which the objective function adds extra weight to the max
out of the decision variables multiplied by their respective coefficients.
With this in mind, is there a way to use min
or max
operators within the objective function of a linear program?
Example:
Minimize (c1 * x1) + (c2 * x2) + (c3 * x3) + (c4 * max(c1*x1, c2*x2, c3*x3)) subject to #some arbitrary integer constraints: x1 >= ... x1 + 2*x2 <= ... x3 >= ... x1 + x3 == ...
Note that (c4 * max(c1*x1, c2*x2, c3*x3))
is the "extra weight" term that I'm concerned about. We let c4
denote the "extra weight" coefficient. Also, note that x1
, x2
, and x3
are integers in this particular example.
I think the above might be outside the scope of what linear programming offers. However, perhaps there's a way to hack/reformat this into a valid linear program?
If this problem is completely out of the scope of linear programming, perhaps someone can recommend an optimization paradigm that is more suitable to this type of problem? (Anything that allows me to avoid manually enumerating and checking all possible solutions would be helpful.)
The min function can be linearized as: First, we decompose the min function into a max and a modulus. Then we get rid of the max. such that only one of them will be different from zero in any solution.
A minimax problem seeks to minimize the maximum value of a number of decision variables. It is sometimes applied to minimize the possible loss for a worst case (maximum loss) scenario. A maximin problem maximizes the minimum value.
Add in an auxiliary variable, say x4, with constraints:
x4 >= c1*x1 x4 >= c2*x2 x4 >= c3*x3 Objective += c4*x4
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With