Description: book example autogenerated using nltransd.mod, nltrans.dat, and nltrans.run
Nonlinear transportation model
This is a variation of the linear transportation model presented on the Chapter 3 of the AMPL book, containing a nonlinear objective. There are a set of origin nodes, and a set of destination nodes (net model).
$$\sum \limits_{\substack{i \in ORIG \ j \in DEST}} rate[i,j] \cdot \frac{Trans[i,j]}{1 - \frac{Trans[i,j]}{limit[i,j]}}$$
The bigger the Trans[i,j]
value, the closer to limit[i,j]
(upper bound) so denominator tends to $1-1=0$ implying high costs.
Constraints:
$$\sum \limits_{j \in DEST} Trans[i,j] = supply[i]$$
$$\sum \limits_{i \in ORIG} Trans[i,j] = demand[j]$$
Ipopt 3.12.13: outlev=0
******************************************************************************
This program contains Ipopt, a library for large-scale nonlinear optimization.
Ipopt is released as open source code under the Eclipse Public License (EPL).
For more information visit http://projects.coin-or.org/Ipopt
******************************************************************************
Ipopt 3.12.13: Maximum Number of Iterations Exceeded.
suffix ipopt_zU_out OUT;
suffix ipopt_zL_out OUT;
Total_Cost = -22681400000
Trans [*,*] (tr)
: CLEV GARY PITT :=
DET 518.41 279.922 401.668
FRA 326.573 153.849 419.579
FRE 377.651 371.911 350.438
LAF 409.194 173.889 416.917
LAN 284.738 34.4686 280.794
STL 500 372.77 827.229
WIN 183.433 13.1917 203.375
;
The previous problem is unbounded, however, this is not what we expect for this problem. This is due to the highly nonlinear objective function.
Because the behavior of a nonlinear optimization algorithm can be sensitive to the choice of starting guess, we might hope that the solver will have greater success from a different start. To ensure that the comparison is meaningful, we first set
So that status information about variables that was returned by the previous solve will not be sent back to help determine a starting point for the next solve. We can use the let
command to suggest a new initial value for each variable. For example, say that Trans[i,j]
is half of limit[i,j]
.
Ipopt 3.12.13: outlev=0
******************************************************************************
This program contains Ipopt, a library for large-scale nonlinear optimization.
Ipopt is released as open source code under the Eclipse Public License (EPL).
For more information visit http://projects.coin-or.org/Ipopt
******************************************************************************
Ipopt 3.12.13: Optimal Solution Found
Total_Cost = 1212120
Trans[i,j]/limit[i,j] [*,*] (tr)
: CLEV GARY PITT :=
DET 0.732965 0.187385 0.710404
FRA 0.589986 0.162441 0.654733
FRE 0.731 0.739444 0.729557
LAF 0.490537 0 0.56607
LAN 0.367685 0 0.509753
STL 0.939382 0.95209 0.937274
WIN 0.123449 0 0.502068
;
Now the solver gives a right solution. However, we could have had trouble in case any Trans
variable get closer to the limit
, what we could check by calling
display {i in ORIG, j in DEST} Trans[i,j]/limit[i,j];
We could implement a more robust formulation by giving more explicit bounds to the variables to avoid numerical issues. With the following bounds, Trans
will be smaller that limit
.
var Trans {i in ORIG, j in DEST} >= 0, <= .9999 * limit[i,j];
Multiple local optima
Let’s change to a concave objective function by adding a power of 0.8:
$$\sum \limits_{\substack{i \in ORIG \ j \in DEST}} rate[i,j] \cdot \frac{Trans[i,j]^{0.8}}{1 - \frac{Trans[i,j]}{limit[i,j]}}$$
Ipopt 3.12.13: outlev=0
******************************************************************************
This program contains Ipopt, a library for large-scale nonlinear optimization.
Ipopt is released as open source code under the Eclipse Public License (EPL).
For more information visit http://projects.coin-or.org/Ipopt
******************************************************************************
Error evaluating "var =" definition -1: can't evaluate pow'(0,0.8).
exit value 1
<BREAK>
We got the error
Error evaluating “var =” definition -1: can’t evaluate pow’(0,0.8).
This is due to the fact that the derivative of the exponential function at zero is infinity. We could just give an starting point away from zero, and tighten the lower bound too:
var Trans {i in ORIG, j in DEST} >= 1e-10, <= .9999 * limit[i,j], := limit[i,j]/2;
Ipopt 3.12.13: outlev=0
******************************************************************************
This program contains Ipopt, a library for large-scale nonlinear optimization.
Ipopt is released as open source code under the Eclipse Public License (EPL).
For more information visit http://projects.coin-or.org/Ipopt
******************************************************************************
Ipopt 3.12.13: Restoration Phase Failed.
suffix ipopt_zU_out OUT;
suffix ipopt_zL_out OUT;
Total_Cost = 354279
Trans [*,*] (tr)
: CLEV GARY PITT :=
DET 586.429 191.805 421.765
FRA 292.089 75.1764 532.735
FRE 365.333 370.173 364.494
LAF 488.914 0.0937081 510.992
LAN 298.74 0.000276411 301.26
STL 469.177 762.751 468.072
WIN 99.318 9.99922e-05 300.682
;
By adding a new parameter alpha
that ponders the lower bound for Trans
, we may solve the problem from different initial guesses, providing potential different solutions.
Ipopt 3.12.13: outlev=0
******************************************************************************
This program contains Ipopt, a library for large-scale nonlinear optimization.
Ipopt is released as open source code under the Eclipse Public License (EPL).
For more information visit http://projects.coin-or.org/Ipopt
******************************************************************************
Ipopt 3.12.13: Search Direction becomes Too Small.
suffix ipopt_zU_out OUT;
suffix ipopt_zL_out OUT;
## Iteration 1
alpha = 0.1
Total_Cost = 354281
Ipopt 3.12.13: outlev=0
******************************************************************************
This program contains Ipopt, a library for large-scale nonlinear optimization.
Ipopt is released as open source code under the Eclipse Public License (EPL).
For more information visit http://projects.coin-or.org/Ipopt
******************************************************************************
Ipopt 3.12.13: Search Direction becomes Too Small.
## Iteration 2
alpha = 0.2
Total_Cost = 354277
Ipopt 3.12.13: outlev=0
******************************************************************************
This program contains Ipopt, a library for large-scale nonlinear optimization.
Ipopt is released as open source code under the Eclipse Public License (EPL).
For more information visit http://projects.coin-or.org/Ipopt
******************************************************************************
Ipopt 3.12.13: Search Direction becomes Too Small.
## Iteration 3
alpha = 0.3
Total_Cost = 354277
Ipopt 3.12.13: outlev=0
******************************************************************************
This program contains Ipopt, a library for large-scale nonlinear optimization.
Ipopt is released as open source code under the Eclipse Public License (EPL).
For more information visit http://projects.coin-or.org/Ipopt
******************************************************************************
Ipopt 3.12.13: Restoration Phase Failed.
## Iteration 4
alpha = 0.4
Total_Cost = 354277
Ipopt 3.12.13: outlev=0
******************************************************************************
This program contains Ipopt, a library for large-scale nonlinear optimization.
Ipopt is released as open source code under the Eclipse Public License (EPL).
For more information visit http://projects.coin-or.org/Ipopt
******************************************************************************
Ipopt 3.12.13: Search Direction becomes Too Small.
## Iteration 5
alpha = 0.5
Total_Cost = 354278
Ipopt 3.12.13: outlev=0
******************************************************************************
This program contains Ipopt, a library for large-scale nonlinear optimization.
Ipopt is released as open source code under the Eclipse Public License (EPL).
For more information visit http://projects.coin-or.org/Ipopt
******************************************************************************
Ipopt 3.12.13: Restoration Phase Failed.
## Iteration 6
alpha = 0.6
Total_Cost = 354278
Ipopt 3.12.13: outlev=0
******************************************************************************
This program contains Ipopt, a library for large-scale nonlinear optimization.
Ipopt is released as open source code under the Eclipse Public License (EPL).
For more information visit http://projects.coin-or.org/Ipopt
******************************************************************************
Ipopt 3.12.13: Search Direction becomes Too Small.
## Iteration 7
alpha = 0.7
Total_Cost = 354277
Ipopt 3.12.13: outlev=0
******************************************************************************
This program contains Ipopt, a library for large-scale nonlinear optimization.
Ipopt is released as open source code under the Eclipse Public License (EPL).
For more information visit http://projects.coin-or.org/Ipopt
******************************************************************************
Ipopt 3.12.13: Search Direction becomes Too Small.
## Iteration 8
alpha = 0.8
Total_Cost = 354278
Ipopt 3.12.13: outlev=0
******************************************************************************
This program contains Ipopt, a library for large-scale nonlinear optimization.
Ipopt is released as open source code under the Eclipse Public License (EPL).
For more information visit http://projects.coin-or.org/Ipopt
******************************************************************************
Ipopt 3.12.13: Restoration Phase Failed.
## Iteration 9
alpha = 0.9
Total_Cost = 354278
Ipopt 3.12.13: outlev=0
******************************************************************************
This program contains Ipopt, a library for large-scale nonlinear optimization.
Ipopt is released as open source code under the Eclipse Public License (EPL).
For more information visit http://projects.coin-or.org/Ipopt
******************************************************************************
Ipopt 3.12.13: Search Direction becomes Too Small.
## Iteration 10
alpha = 1
Total_Cost = 354277