Linear programming with minimum and maximum fixed cost

Question

I need your help in the following optimisation problem. I have a maximisation Mixed Integer linear programming problem. I would like to consider the minimum & maximum fixed fee.

I've done it in this way..

cost = max(minimum fixed cost , cost rate * x)
cost >= minimum fixed cost
cost >= cost rate * x
cost = min(maximum fixed cost , cost rate * x)
cost <= maximum fixed cost
cost <= cost rate * x

But, This turns infeasible solution. Would you please help me in optimising such a problem.

Erwin Kalvelagen · Accepted Answer · 2017-04-06 22:24:00Z

2

piecewise linear functions

I think what you mean is the following:

Let

A = minimum fixed cost / cost rate
B = maximum fixed cost / cost rate

Then you want to model the piecewise linear function:

cost = minimum fixed cost   if x < A
       cost rate * x        if A <= x <= B 
       maximum fixed cost   if x > B

Using piecewise linear functions inside a MIP model is not a problem. You can do this by different approaches:

using extra binary variables (see (1))
using SOS2 variables (see (1))
systems like AMPL and Gurobi have special facilities to express piecewise linear functions.

Example formulation

A formulation with SOS2 variables can look as follows:

Introduce data points px and py

  px     py
  --------------------------
  0      minimum fixed cost
  A      minimum fixed cost
  B      maximum fixed cost
  C      maximum fixed cost

where we assume 0<=x<=C. I.e. C is an upper bound on x.

Then do:

  set p = {1,2,3,4}
  sos2 variables lambda(p)
  sum(p, lambda(p)) = 1
  x = sum(p, lambda(p)*px(p))
  cost = sum(p, lambda(p)*py(p))

See e.g. (2)

What is wrong with your approach

Note that your approach (shown in the question) is incorrect:

cost >= minimum fixed cost
cost >= cost rate * x
cost <= maximum fixed cost
cost <= cost rate * x

is really

minimum fixed cost <= cost <= maximum fixed cost
cost = cost rate * x

which limits x to A <= x <= B.

References

(1) H.Paul Williams, "Model Building in Mathematical Programming", Wiley

(2) GAMS: Piecewise linear functions with SOS2 variables

edited Apr 6, 2017 at 22:24

answered Apr 6, 2017 at 0:51

Erwin Kalvelagen

16.9k3 gold badges17 silver badges42 bronze badges

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

3 Comments

user7090205 Over a year ago

Thank you very much for your answer. However, I don't want to limit x. x can be greater than B or smaller than A. If x is greater than B, maximum fixed cost should apply. If x is less than A, minimum fixed cost should apply. I went through the problems presented in chapter 9 in the book but still I can relate them to my problem. Would you please provide me with an example of how such a problem is solved.I would greatly appreciate it.

Erwin Kalvelagen Over a year ago

You formulation imposes these limits on x. It is disappointing you don't understand the Williams book. It is considered a very good and quite accessible. I have added a SOS2 example.

user7090205 Over a year ago

Thank you again @Erwin Kalvelagen. I've grasped the concept of SOS2. However, I'm still getting an unfeasible solution in my model :( Actually, my variable X looks like this x(a, b, c, d, e). So for each x(a, b, c, d, e) I've created variables x1(a, b, c, d, e), x2(a, b, c, d, e), x3(a, b, c, d, e), x4(a, b, c, d, e). Similarly, for the binary variables for each line segment y1(a, b, c, d, e), y2(a, b, c, d, e), y3(a, b, c, d, e) to control adjacent x.

user7090205 · Accepted Answer · 2017-04-07 19:53:22Z

1

Piecewise linear function:

cost = 0.02 x  if 0   <= x <= 500
       0.03 x  if 500 <= x <= 1500 
       0.04 x  if 1500<= x <= 10000

SOS2 Solution:

x[a, b, c, d, e] = (x1[a, b, c, d, e] * 0)    + 
                   (x2[a, b, c, d, e] * 500)  + 
                   (x3[a, b, c, d, e] * 1500) +
                   (x4[a, b, c, d, e] * 10000) 

cost[a, b, c, d, e] = (x1[a, b, c, d, e] * 0       * 0   )+ 
                      (x2[a, b, c, d, e] * 500     * 0.02)+
                      (x3[a, b, c, d, e] * 1500    * 0.03)+
                      (x4[a, b, c, d, e] * 10000   * 0.04)

x1[a, b, c, d, e] + x2[a, b, c, d, e] + x3[a, b, c, d, e] + x4[a, b, c, d, e]>= 0

x1[a, b, c, d, e] <= y1[a, b, c, d, e]
x2[a, b, c, d, e] <= y1[a, b, c, d, e] + y2[a, b, c, d, e]
x3[a, b, c, d, e] <= y2[a, b, c, d, e] + y3[a, b, c, d, e]
x4[a, b, c, d, e] <= y3[a, b, c, d, e]    

y1[a, b, c, d, e] + y2[a, b, c, d, e] + y3[a, b, c, d, e]  = 1

I've done it in this way. However, the solver still shows unfeasible solution. Can you see something wrong in this formulation?!

answered Apr 7, 2017 at 19:53

user7090205

212 bronze badges

1 Comment

Erwin Kalvelagen Over a year ago

This is not a SOS2 approach but rather using binary variables. SOS2 uses SOS2 sets..

Collectives™ on Stack Overflow

Linear programming with minimum and maximum fixed cost

2 Answers 2

piecewise linear functions

Example formulation

What is wrong with your approach

References

3 Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

piecewise linear functions

Example formulation

What is wrong with your approach

References

3 Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related