36

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.)

solvingPuzzles
  • 8,541
  • 16
  • 69
  • 112

1 Answers1

52

Add in an auxiliary variable, say x4, with constraints: 

x4 >= c1*x1
x4 >= c2*x2
x4 >= c3*x3  
Objective += c4*x4
SashaZd
  • 3,315
  • 1
  • 26
  • 48
fairidox
  • 3,358
  • 2
  • 28
  • 29
  • 3
    Very nicely done, @justaname. OP should note that the new variable x4 need not be an integer. – Ram Narasimhan May 29 '12 at 06:58
  • 17
    This technique only works if you are minimizing over a maximum function -- or maximizing over a minimum function. If you need to minimize over a minimum function or maximize over a maximum function, then you need to add additional binary variables and big-M coefficients. – Greg Glockner May 29 '12 at 21:53
  • @Greg Glockner Thanks for pointing this out! Any chance you could give an example of how to handle "maximizing over a max function" or "minimizing over a min function?" – solvingPuzzles Jun 01 '12 at 08:22
  • @solvingPuzzles You need to use big-M coefficients. – Greg Glockner Aug 23 '12 at 17:10
  • @GregGlockner - Can you provide a small example about using big-M coefficients for "minimizing over a min function"? – statBeginner Jan 14 '16 at 07:25
  • Hi @statBeginner, do you find a solution to the min over min /max over max problem? I happen to have to cross that bridge, any information will be appreciated. – daydayup Jul 15 '16 at 20:05
  • @GregGlockner Hi Dr. Glockner, could you give us a little more information on how to use the big-M and adding new binary variables to solve min over min /max over max problem? Thank you so much for your help! A lot of respect for your knowledge! – daydayup Jul 15 '16 at 20:06
  • 9
    A simple example for min/min: if you have: min z where z = min(x1,x2,x3), then write: min z where z >= x1-M b1, z >= x2-M b2, z >= x3-M b3, b1+b2+b3=2 and b1,b2,b3 binary. – Greg Glockner Jul 16 '16 at 02:15
  • @GregGlockner. Thank you Dr. Glockner! You are the master. – daydayup Jul 16 '16 at 23:52
  • An answer going into more details about this is here: https://math.stackexchange.com/a/2447498/518032 – M. Volf Aug 21 '21 at 22:21