3

I am trying to easily formulate a LP using a minimum function within the objective function. The objective function proceeds similar to as follows:

maximize sum( R(dvf * Df) ) - sum( min( tsp, ts'p ) * Csp - max(tsp-ts'p,0) * bsp )

R --> Revenue function (I'm not concerned about this part for this question)

tsp indicates how many trucks I'm sending on orgin-destination combinaton s on path p. ts'p is the reverse route. I'm summing here on s and p.

What I need to know from this is how to set it up as part of an LP, as LP's do not accept minimization and maximization functions within their objective statements. According to this question, big-M formulations with additional variables are required, but it doesn't say really how to do it.

Thanks for your help in advance!

Community
  • 1
  • 1
panoptical
  • 782
  • 1
  • 8
  • 22
  • 1
    In [this](http://www.aimms.com/aimms/download/manuals/aimms3om_linearprogrammingtricks.pdf) book chapter you could find a few neat LP tricks, for example how to minimize the maximum. Maybe it can be of some help. – Anders Gustafsson Oct 25 '13 at 07:01
  • Turn the min inside the objective function into it's dual linear program wich is a max problem. Then solve it by solving one max problem. See the duality theorem. – Chris Pillen Jan 07 '16 at 18:59

1 Answers1

2

Here's how you'd do it with Big-M and a set of indicator variables.

Let me just use one pair of routes for illustration, and you can do the same for all pairs of routes (s,p). Let's call them Tsp and the reverse to be Tps.

Linearizing the Minimum of two decision variables in an IP

Let's focus just on the piece of the Objective Function that reads Min(Tsp, Tps) * Cost_sp

First rewrite the objective function to be Min Xsp * Csp So we have introduced a new variable Xsp for route sp such that:

Xsp = Tsp if Tsp is the minimum of Tsp and Tps
Xsp = Tps if Tps is the minumum of the two values

That can be enforced via extra constraints.

Xsp = Tsp * Y + Tps * (1-Y) where Y is a 0-1 indicator variable.

We want Y to be 1 if Tsp is greater, and Y to be 0 if Tsp is the smaller value.

To get that to happen, we add the constraint: Tsp - Tps + M*y > 0 Working out that logic, if Tsp is big, then the condition is automatically satisfied. But if Tps is bigger than Tsp, then Y has to take on the value 1 for the constraint to be satisfied.

By adding a small price in the objective function, we can ensure that Y is one only if has to take on that value.

Putting it all together:

Objective Maximize Sum(p,s) Xsp * Csp - epsilon.Y

s.t.
     Xsp = Tsp * Y + Tps * (1-Y)
     Tsp - Tps + M*y > 0
     Y = {0,1}

will ensure that the objective function takes the minimum of the two values Tsp and Tps.

Hope that helps you move forward with the rest.

Community
  • 1
  • 1
Ram Narasimhan
  • 22,341
  • 5
  • 49
  • 55