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.

Answer 1

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

Answer 2

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?!