[ Home | Support | Sales | Solvers | Documentation | Model Libraries | Search | Contact Us ]

trnspwl.gms : A Transportation Problem with discretized economies of scale

This problem finds a least cost shipping schedule that meets
requirements at markets and supplies at factories. This instance
applies economies of scale which results in a non-convex
objective. This is an extension of the trnsport model in the GAMS
Model Library.

The original nonlinear term is "sum((i,j), c(i,j)*sqrt(x(i,j)))". We
use the following discretization f(x) of sqrt(x)

  For x<=50:  f(x) = 1/sqrt(50)*x,
  for x>=400: f(x) = (sqrt(600)-sqrt(400))/200*(x-400) + sqrt(400)
  in between we discretize with linear interpolation between points

This discretization has some good properties:
  0) f(x) is a continuous function
  1) f(0)=0, otherwise we would pick up a fixed cost even for unused connections
  2) a fine representation in the reasonable range of shipments (between 50 and 400)
  3) f(x) underestimates sqrt in the area of x=0 to 600. Past that is overestimates sqrt.

The model is organized as follows:
  1) We set a starting point for the NLP solver so it will get stuck
     in local optimum that is not the global optimum.

  2) We use three formulations for representing piecewise linear
     functions all based on the same discretization.

     a) a formulation with SOS2 variables. This formulation mainly is
        based on the convex combination of neighboring
        points. Moreover, the domain of the discretization can be
        unbounded: we can assign a slope in the (potentially
        unbounded) first and last segment.

     b) a formulation with SOS2 variables based on convex combinations
        of neighboring points. This formulation requires a bounded
        region for the discretization. Here we discretize between 0 and
        600.

     c) a formuation with binary variables. This also requires the
        domain to be bounded, but it does not rely on the convex
        combination of neighboring points. There are examples, where
        this formulation solves much faster than the formulation b).

     In this example x is clearly bounded by 0 from below and
     min(smax(i,a(i),smax(j,b(j)) from above, so formulation b and c
     are sufficient and perform better on this particular model and
     instance. We added the formulation a to demonstrate how to model
     an unbounded discretization, in case there are no derived
     bounds. The formulation a can be easily adjusted to accommodate
     problems where only one end of the discretization is unbounded.

  3) We restart the non-convex NLP from the solution of the discretized
     model and hope that the NLP solver finds the global solution.

• Dantzig, G B, Chapter 3.3. In Linear Programming and Extensions. Princeton University Press, Princeton, New Jersey, 1963.