Using min/max within an Integer Linear Program

Question

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

SashaZd · Accepted Answer · 2017-01-10 21:52:18Z

53

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

x4 >= c1*x1
x4 >= c2*x2
x4 >= c3*x3  
Objective += c4*x4

edited Jan 10, 2017 at 21:52

SashaZd

3,3291 gold badge30 silver badges48 bronze badges

answered May 29, 2012 at 4:23

fairidox

3,4482 gold badges31 silver badges30 bronze badges

Sign up to request clarification or add additional context in comments.

10 Comments

Ram Narasimhan Over a year ago

Very nicely done, @justaname. OP should note that the new variable x4 need not be an integer.

Greg Glockner Over a year ago

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.

solvingPuzzles Over a year ago

@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?"

Greg Glockner Over a year ago

@solvingPuzzles You need to use big-M coefficients.

Greg Glockner Over a year ago

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.

|

Collectives™ on Stack Overflow

Using min/max within an Integer Linear Program

1 Answer 1

10 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

10 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related