Printer Friendly

Solving the nonlinear discrete transportation problem by MINLP optimization.

Introduction

The Transportation Problem (TP) can be set among network optimization problems that are well-known in the research community. The objective of the TP is to minimize the total transportation cost for a shipment of a single commodity from a number of sources to a number of destinations without exceeding the capacities of each source and by satisfying the requirements of each destination. When the transportation cost on a given route is nonlinearly dependent on the discrete number of units transported, the TP becomes the nonlinear discrete optimization problem. Despite its ease of formulation, the Nonlinear Discrete Transportation Problem (NDTP) belongs to the class of the optimization problems that are hard to solve.

Applications of different NDTPs extend over several fields in industry including transportation, logistics, operational research, engineering, etc. That is because the adoption of a decision support system to help performing the correct selection of shipping mode minimizing transportation costs proves to be highly beneficial, owing to the complexity of the problem, the large number of variables involved and the number of possible options to be compared (Caputo et al. 2006). For this reason, the cost effective transportation scheduling has received substantial attention among researchers and a number of different variations and extensions of the NDTP have been discussed in literature.

The most recent progress in this field can be found in several research works. For instance, Ozsen et al. (2009) introduced a capacitated location-inventory problem that minimizes the sum of the fixed warehouse location costs, the transportation costs, and the inventory costs. The optimization problem was formulated as a nonlinear integer-programming problem, solved by using a Lagrangian relaxation method. Monteiro et al. (2010) discussed the nonlinear discrete optimization problem of designing a one-period planning horizon supply chain with integrated and flexible decisions on location of plants and warehouses, on levels of production and inventory, and on transportation models, considering stochastic demand and the ABC classification for finished goods. In addition, the outer approximation method was used to solve the optimization problem. Agrali et al. (2012) presented a nonlinear discrete facility location problem with safety stock costs and applied a generalized Benders decomposition method to obtain the optimum solution. Romeijn and Sargut (2011) proposed a branch-and-price method for solving a class of stochastic transportation problems with single-sourcing constraints which included both continuous and discrete decision variables as well as the nonlinear cost functions. Carrizosa et al. (2012) addressed a discrete location problem with nonlinear cost objective function and developed a heuristic approach for its solution. The objective in their work was to minimize the total transportation cost between clients and plants, plus an increasing nonlinear function of number of plants.

From the viewpoint of the mathematical formulation, the NDTP represents a Mixed-Integer Nonlinear Programming (MINLP) optimization problem. The NDTP can be highly combinatorial and non-convex optimization problem. The optimum solution of a complex and non-convex MINLP problem with a high number of discrete decisions is in general very difficult to obtain. Although the MINLP methods are expected to solve the NDTP to optimality, it is of little use if the optimum solutions are not available in time when decisions should be made. Therefore, a MINLP method which provides a good result within reasonable solution time, can be more useful in some cases (Lastusilta 2011). In this way, the selection of a suitable MINLP method, by which a specific NDTP can be appropriately solved, is frequently a critical issue in obtaining valuable results.

In recent paper by Klansek and Psunder (2012), the capability of the MINLP optimization to solve a specific nonlinear discrete network problem was shown on the nonlinear discrete time-cost trade-off problem. The implemented research presents a natural continuation of the work introduced in reference (Klansek, Psunder 2010), where the performance of different global nonlinear programming (NLP) optimization techniques was tested on a set of nonlinear (continuous) transportation problems. In a view of previous research, the aim of this paper is to present the suitability of five different MINLP methods for specifically the exact optimum solution of the NDTP. The evaluated MINLP methods include the extended cutting plane method (ECP) by Westerlund and Pettersson (1995), the branch and reduce method (BR) by Ryoo and Sahinidis (1996), the augmented penalty/outer-approximation/equality-relaxation method (AP/OA/ER) by Viswanathan and Grossmann (1990), the branch and cut (BC) method by Lin and Schrage (2009), and the simple branch and bound (SBB) method by Leyffer (2001). The MINLP methods were applied to solve the NDTPs from the literature. The gained solutions were compared and a correlative evaluation of the MINLP methods is shown to demonstrate their suitability for solving the NDTPs.

1. MINLP Optimization Approach

The MINLP represents a mathematical programming technique which executes the discrete optimization of discrete variables simultaneously with the continuous optimization of continuous variables. Since the MINLP

can manage nonlinear relationships between the variables, it was selected to solve the NDTP. The general nonlinear continuous/discrete optimization problem can be presented as a MINLP problem by following formulation:

Minimize z = [c.sup.T] y + f(x),

subject to:

h(x) = 0;

g(x) [less than or equal to] 0; (MINLP-G)

By + Cx [less than or equal to] b;

x [member of] X = {x [member of] [R.sup.n]: [x.sup.LO] [less than or equal to] x [less than or equal to] [x.sup.UP]}; y [member of] Y = [{0, 1}.sup.m],

where: x denotes the vector of the continuous variables defined in compact set X, and y represents the vector of the binary variables. While the continuous variables x may appear linearly or nonlinearly in the objective function and constraints, the binary variables y can only appear linearly. Functions f(x), h(x) and g(x) are nonlinear functions contained in the objective function z, equality and inequality constraints, respectively. Finally, By + Cx [less than or equal to] b is a subset of mixed linear equality and inequality conditions. Note that functions f(x), h(x) and g(x) must be continuous and differentiable.

The MINLP formulation of the NDTP contains the nonlinear objective function subjected to the various constraints with continuous and binary variables. The continuous variables are used for continuous optimization, while the discrete binary variables are used for discrete decision optimization. The objective function is proposed to minimize the total transportation cost. The continuous variables define the transporting flows from sources to destinations. The binary variables represent the potential selection of integer solutions for continuous variables inside the determined superstructure of different discrete solution alternatives. The system of equality and inequality constraints as well as the bounds on variables defines a supply, demand and transporting flow conditions.

The MINLP approach can be executed in three steps (Klansek, Psunder 2012). The first one comprises the generation of a superstructure with different alternatives for discrete solutions of continuous variables, the second one includes the development of the MINLP model formulation and the last one consists of a solution for the stated MINLP problem. Generating a suitable superstructure of discrete alternatives represents an important phase in the MINLP optimization (Kravanja et al. 2005). The quality of the gained optimum result directly depends on the quality and quantity of the discrete solution alternatives accounted for in the superstructure. The MINLP superstructure for the NDTP is to be generated as a transportation problem superstructure consisting of various discrete alternatives for the transporting flows from which an optimum discrete solution is obtained within all variations. Selection of the optimum discrete solution from the developed superstructure of alternatives requires a discrete decision optimization.

When the superstructure of discrete solution alternatives for transporting flows is generated, the MINLP optimization is followed by the development of a MINLP model formulation for the NDTP. As soon as the MINLP model formulation for the NDTP is finished, the defined MINLP problem can be solved using a suitable MINLP method. Since the NDTPs can be highly combinatorial and non-convex optimization problems, the selection of a suitable MINLP method for a specific NDTP should be done attentively to achieve valuable results.

2. MINLP Optimization Model Formulation

Considering the formulation of the general MINLP optimization problem (MINLP-G), the MINLP optimization model formulation for the NDTP is more specific, especially in terms of decision variables and constraints. In this way, the MINLP model formulation for the NDTP includes the objective function, the supply constraints, the demand constraints and the logical constraints for the discrete transporting flows. Thus, the objective of the NDTP is to minimize the nonlinear total transportation cost while meeting the supply, the demand and the transporting flow constraints. The MINLP model formulation for the NDTP is given in the following form:

Minimize Cost = [summation over (i [member of] I)] [summation over (j [member of] I)] [f.sub.i, j]([x.sub.i, j]), (1)

subject to:

[summation over (j [member of] J)] [x.sub.i, j] = [s.sub.i], i [member of] I; (2)

[summation over (i [member of] I)] [x.sub.i, j] = [d.sub.j], j [member of] J; (3)

[summation over (k [member of] K)(i, j)] [y.sub.i, j, k] [q.sub.k] = [x.sub.i, j], i [member of] I; j [member of] J; (4)

[summation over (k [member of] K)(i, j)] [y.sub.i, j, k] = 1, i [member of] I; j [member of] J; (5)

[x.sub.i, j] [greater than or equal to] 0, i [member of] I; j [member of] J; (6)

[y.sub.i, j, k] = [{0, 1}.sup.m], i [member of] I; j [member of] J; k [member of] K(i, j), (7)

where: the Cost denotes the total transportation cost for a shipment of a single commodity from sources to destinations, [f.sub.i, j]([x.sub.i, j]) represents the cost function of transporting flow from source i to destination j, [s.sub.i] and [d.sub.j] are the capacities of each source i and each destination j, respectively. The objective function given in Eq. (1) denotes the sum of the individual cost contributions [f.sub.i, j]([x.sub.i, j]) of the transporting flows [x.sub.i, j]. Formulations in Eq. (2) and Eq. (3) define the supply and the demand constraints, respectively. The constraints presented in Eq. (2) require that the sum of the shipments from a source equals its supply, while the constraints given by Eq. (3) ensure that the sum of the shipments to a destination satisfy its demand.

Logical constraints in Eq. (4) and Eq. (5) must be fulfilled for the selection of discrete solutions for the continuous variables [x.sub.i, j] inside the superstructure of discrete alternatives. For this purpose, the set K is defined to include discrete solution alternatives k, k [member of] K(i, j), into the superstructure of the NDTP. Discrete constants [q.sub.k] in Eq. (4) are defined for the discrete transporting flow solution alternatives. Since each defined discrete constant represents the potential discrete solution of its corresponding continuous variable, the binary variables [y.sub.i, j, k] are used to execute the selection of the discrete solutions. In this way, the binary variables [y.sub.i, j, k] are used for the selection of the discrete solutions for transporting flows [x.sub.i, j].

Each discrete constant alternative is selected to be the discrete solution of the corresponding continuous variable only if the calculated value of the assigned binary variable is equal to 1. The discrete constant alternative is rejected if the calculated value of the assigned binary variable is equal to 0. Eq. (5) is defined to assure that only one discrete value is selected for each continuous variable. Finally, Eq. (6) and Eq. (7) represent the required non-negativity conditions for the transportation flows and the domain of the binary variables, respectively. The presented model formulation defines the balanced NDTP. The structure of the NDTP model implies that the total supply [summation over (i [member of] I)] [s.sub.i] must be equal to the total demand [summation over (j [member of] J)] [d.sub.j].

3. MINLP Optimization Methods

The field of MINLP optimization has not yet attained the state of maturity and reliability as linear, integer or nonlinear programming. For this reason, the comparisons between different MINLP optimization methods hold information for decision-makers about which one of them is good at solving a particular type of MINLP optimization problem. In this paper, the suitability of five different state-of-the-art MINLP optimization methods for solving the NDTP was investigated. The evaluated MINLP optimization methods include the ECP method by Westerlund and Pettersson (1995), the BR method by Ryoo and Sahinidis (1996), the AP/OA/ER method by Viswanathan and Grossmann (1990), the BC method by Lin and Schrage (2009), and the SBB method by Leyffer (2001).

The ECP method (Westerlund, Pettersson 1995) within the computer implementation AlphaECP by Westerlund and Porn (2002) was the first MINLP technique applied to solve the test NDTPs. The ECP method represents an extension of Kelley's cutting plane method (Kelley 1960) which was originally proposed for solving convex NLP problems. It requires only the solution of a Mixed-Integer Linear Programming (MILP) master problem in each iteration. The MILP master-problems can be optimally solved, but may also be solved to feasibility or only to an integer relaxed solution in intermediate iterations. Initially the nonlinear constraints are excluded from the original MINLP problem and the MILP part of the problem is solved (Lastusilta 2011). After the MILP solution is gained, the NLP algorithm is called with mixed-integer levels from the MILP solution with the intention of finding an MINLP solution. When the gained result satisfies all the constraints, a MINLP solution is found. If some of the nonlinear conditions are not fulfilled, at least one unsatisfied nonlinear constraint is linearized and the resulting MILP problem is solved. The search continues until the found optimum MILP solution is also an optimum MINLP solution and all linearizations are valid under-estimators of the nonlinear constraints.

The second MINLP technique used was the BR method (Ryoo, Sahinidis 1996), which is implemented in a computational system BARON (Branch And Reduce Optimization Navigator) by Sahinidis and Tawar-malani (2008). The BR method combines conventional branch and Bound Method (BB) with a broad variety of range reduction tests. The reduction tests are applied to every sub-problem of the search tree within pre- and post-processing phases to contract the search space and reduce the relaxation gap. Number of the reduction tests rest on duality and are employed in cases when the relaxation is convex and solved by an algorithm that provides the dual, in addition to the primal, solution of the relaxed problem. The BR method comprehends many compound branching schemes that accelerate the convergence of standard branching strategies. Currently, the BR method can manage nonlinear functions that include exp(x), ln(x), [x.sup.[alpha]] for real [alpha], [[beta].sup.x] for real [beta], [x.sup.y] and [absolute value of x]. On the contrary, there is lack of support for other nonlinear functions, including the trigonometric functions like sin(x), cos(x), arctan(x), etc.

The AP/OA/ER method (Viswanathan, Grossmann 1990) inside the MINLP computer package DICOPT (DIscrete and Continuous OPTimizer) solves series of NLP sub-problems and MILP master problems. First the MINLP problem is decomposed into a continuous NLP sub-problem and a discrete MILP master problem. The NLP sub-problem corresponds to the continuous optimization of parameters with binary variables, which are temporarily fixed, and yields an upper bound to the MINLP objective function to be minimized. The MILP master problem represents a linear approximation of the MINLP optimization problem, where the MINLP approximation is improved during the iteration procedure.

So, the MILP master problem involves a global linear approximation to the superstructure of alternatives and predicts a lower bound for the MINLP, where a new vector of binary variables is identified. The predicted lower bound increases as the cycle of major MINLP iterations (MILP plus NLP) proceeds. The NLP sub-problems and the MILP master problems are sequentially solved until the convergence of the AP/OA/ER method is reached.

The BC method (Lin, Schrage 2009) included in computational software LINDOGlobal converts the original nonlinear/non-convex optimization problem down into a list of linear/convex sub-problems. Each sub-problem is analysed and either (a) is shown not to have a feasible or optimum solution, or (b) an optimum solution to the sub-problem is found, or (c) the sub-problem is further split into two or more sub-problems, which are then put on the list. The optimization begins with a presolving step, where the MINLP problem is solved using local search procedures by starting the search from a number of intelligently generated points. A solution found in presolving step may be used in the next step or it can be returned as the optimum solution. The next step is the solution of the outer-approximation of the MINLP problem. If the gained solution to the outer-approximation of the MINLP problem also represents the optimum solution to the original problem, the search may terminate, otherwise the BC procedure is used. The BC method subdivides the feasible region into more accurate approximations and places the new sub-problems on the list. When all sub-problems on the list are solved or fathomed, the solution process stops.

The last MINLP optimization approach employed was the SBB method (Leyffer 2001). The SBB method combines the BB method known from MILP and local search NLP procedures. First the relaxed MINLP problem is solved using the provided starting point. If the obtained solution fulfils the integer condition, the search process stops, otherwise the optimization is continued using the BB procedure. The feasible space of the discrete variables is subdivided in the BB procedure. The bounds on the discrete variables are tightened to new integer values to cut off the current non-integer results. Each time the bounds are tightened, a new, tighter NLP sub-problem is solved starting from the precedent NLP solution. The obtained objective function value from the solution of the NLP sub-problem is considered as lower bound on the objective in the contracted feasible space. If the NLP process reports a local infeasibility of a sub-problem, it is presumed that there is no feasible solution to the sub-problem, although the infeasibility has been determined locally. When the optimization problem is convex, these presumptions will be fulfilled and the SBB procedure will provide proper bounds. The SBB method terminates when all sub-problems on the list are solved or fathomed.

4. Comparative Tests

4.1. Input Data

The set of test problems applied in this research was originally proposed by Michalewicz et al. (1991). The considered test problems comprehend the 7 x 7 and the 10 x 0 node problems with six different nonlinear continuous cost functions. The input values for the capacities of the sources [s.sub.i], the capacities of the destinations [d.sub.j] and the cost parameters [c.sub.i, j] of the 7 x 7 problem are given in Table 1.

Considering the data given in Table 1, it can be stated that the 7x7 cost matrix is a symmetrical matrix with zero cost parameters on the diagonal and six cost parameters with large value of 1000 in comparison with the values of the rest cost parameters. The cost matrix and source/destination capacities of the 10x10 problem are introduced in Table 2.

The cost functions f([x.sub.i, j]) applied in the tests were defined as proposed by Michalewicz et al. (1991) and they are formulated in Table 3, and presented in Fig. 1.

[FIGURE 1 OMITTED]

Both input values of the parameters PA and PB were set to 1000. For 7 x 7 test problems, the input value for the parameter S was set to 2, while for 10 x 10 test problems an input value of 5 was applied. The total transportation cost objective function of each considered 7 x 7 and 10x10 test optimization problem was formulated as follows:

Cost = [m.summation over (i = 1)] [n.summation over (j = 1)] [c.sub.i, j] f([x.sub.i, j]). (8)

It should be noted that the shape of the cost function f([x.sub.i, j]) within the objective function was the same on all arcs, while the variation between arcs was obtained by using the cost parameters [c.sub.i, j].

The MINLP superstructure of discrete solution alternatives for the transporting flows was generated using the set of integer constants. All possible discrete solution options for the transporting flows are included into the MINLP optimization model. For example, alternative discrete solutions for transporting flow [x.sub.1, 2] for the 7 x 7 problem are defined with integers 0, 1, 2,..., 20 taking into account the feasible space for this variable 0 [less than or equal to] [x.sub.12] [less than or equal to] min {[s.sub.1], [d.sub.2]}. The initial points for the MINLP solution of the test problems were generated using the classical north-west corner rule.

4.2. Optimization Setup

The MINLP optimization model formulation for the NDTP was applied to solve the test problems. A high-level language GAMS (General Algebraic Modelling System) by Brooke et al. (2012) was used for modelling and for the data inputs/outputs. GAMS/CPLEX (2012) was selected to perform the MILP solution procedures for AlphaECP, BARON and DICOPT, while LINDOGlobal and SBB required no particular selection of an MILP algorithm. CONOPT (generalized reduced-gradient algorithm) by Drud (1994) was selected to solve the

NLP sub-problems for AlphaECP, DICOPT and LIN DOGlobal. MINOS (reduced gradient algorithm combined with a quasi-Newton algorithm) by Murtagh and Saunders (1983) was selected to perform the NLP search processes for BARON and SBB. A time limit of 1000 CPU seconds (~17 minutes) per test problem was set for the considered MINLP methods to perform the optimization.

The applied set of the test NDTPs was solved on a 64-bit operating system using the personal computer: Intel Core i7, 2.93 GHz, 8 GB RAM and 1 TB hard disc. The 7 x 7 test problems included 49 continuous variables (e.g. transporting flows [x.sub.i, j]), 1087 binary variables (e.g. discrete decision variables [y.sub.i, j, y, k]), an objective variable (e.g. variable Cost) and 112 constraints (e.g. 7 supply constraints, 7 demand constraints, 98 logical constraints). Similarly, the 10 x 10 test problems contained 100 continuous variables, 616 binary variables, an objective variable and 220 constraints. The solution processes were finished within the given time limit and the best obtained discrete solutions for the test problems were reported by the MINLP algorithms.

4.3. Computational Results and Comparisons

Cost function A is a nonlinear continuous arc-tangent approximation of a five-step piece-wise linear function, see Fig. 1A. The discrete solutions of the test NDTPs with cost function A were achieved only by AlphaECP, DICOPT, LINDOGlobal and SBB since BARON could not handle the trigonometric function arctan(x) within the MINLP model. The obtained objective function values for the test problems with cost function A are given in Fig. 2.

Fig. 2 shows that the best objective function values for both the 7 x 7 and 10 x 10 test problems with cost function A were found by AlphaECP. The best objective function value for the 7 x 7 test problem was 171.59 while the best discrete solution of the 10x10 test problem contains the objective function value of 66.89. AlphaECP obtained the discrete solution for the 7 x 7 test problem with cost function A which shows smaller objective function value in comparison with those gained by DICOPT (-10.11%), LINDOGlobal (-46.86%) and SBB (-29.71%). The discrete solution of the 10x10 test problem with cost function A found by AlphaECP indicates smaller objective function value than the solutions reached by DICOPT (-27.59%), LINDOGlobal (-22.99%) and SBB (-26.79%). The achieved best discrete solutions for the 7 x 7 and 10 x 10 test problems with cost function A are presented in Tables 4 and 5.

Cost function B is a nonlinear continuous arc-tangent approximation of a piece-wise linear function with three gradients, see Fig. 1B. Similarly as before, the discrete solutions of the test problems with function B were reached only by AlphaECP, DICOPT, LINDOGlobal and SBB while BARON could not handle the arc-tangent functions in the MINLP model. The calculated objective function values for the test NDTPs with cost function B are shown in Fig. 3.

The best objective function values for both the 7 x 7 and 10 x 10 test problems with cost function B were gained by SBB algorithm, see Fig. 3. The best discrete solution for the 7 x 7 test problem with cost function B indicates the objective function value of 349.98. The objective function value of the best found discrete solution for the 10x10 test problem with cost function B was 169.59. Comparison between the achieved results for the 7 x 7 test problem shows that the objective function value obtained by SBB was smaller than those calculated by AlphaECP (-3.58%), DICOPT (-0.28%) and LINDOGlobal (-11.95%). For the 10x10 test problem, the value of the objective with cost function B reached by SBB was smaller in comparison with those found by AlphaECP (-3.96%), DICOPT (-3.96%) and LINDO Global (-4.72%). The attained best solutions for the 7x7 and 10x10 test NDTPs with cost function B are shown in Tables 6 and 7.

Cost function C represents a regular quadratic function, see Fig. 1C. The discrete solutions for the test NDTPs with cost function C were obtained by Alpha ECP, BARON, DICOPT, LINDOGlobal and SBB algorithms, see Fig. 4.

Fig. 4 demonstrates that all five considered MINLP methods found the identical discrete solution for the 7x7 test problem with cost function C which contains the objective function value of 2648.00, see Table 8. On the other hand, the SBB method gained better discrete solution for the 10 x 10 test problem with cost function C than all the other tested MINLP methods. The best discrete solution of the 10x10 test problem with cost function C includes the objective function value of 4466.00, see Table 9.

SBB optimization algorithm achieved the discrete solution for the 10 x 10 test problem with cost function C with a smaller objective function value in comparison to those found by AlphaECP (-1.41%), BARON (-1.59%), DICOPT (-12.82%) and LINDOGlobal (-6.14%).

Cost function D denotes a square root function, see Fig. 1D. This nonlinear concave cost function gives large contribution to the overall objective function value even for small values of decision variables. The objective function values of the test NDTPs with cost function D found by AlphaECP, BARON, DICOPT, LINDOGlobal and SBB are presented in Fig. 5.

BARON and LINDOGlobal algorithms achieved the best solution for the 7 x 7 test NDTP with function D which indicates the objective function value of 480.16, see Table 10. Considering the 10x10 test problem with cost function D, the best discrete solution with the objective function value of 377.25 was obtained by BARON, see Table 11.

BARON and LINDOGlobal calculated the identical discrete solution for the 7 x 7 test problem with cost function D which indicates smaller objective function value in comparison with those attained by AlphaECP (-13.67%), DICOPT (-20.21%) and SBB (-13.91%). For the 10x10 test NDTP with cost function D, the objective function value of the discrete solution found by BARON was smaller than those gained by AlphaECP (-6.66%), DICOPT (-14.95%), LINDOGlobal (-22.63%) and SBB (-11.75%).

Cost function E is rarely applied in the objective functions of practical NDTPs, see Fig. 1E. However, this non-convex cost function with peak was proposed by Michalewicz et al. (1991) in order to provide a severe test for optimization methods. AlphaECP, BARON,

DICOPT, LINDOGlobal and SBB solved the test problems with peak cost function E within a given solution time, but found different discrete solutions. Fig. 6 presents the objective function values attained in the performed tests with peak cost function E.

The best solutions for both the 7 x 7 and 10 x 10 test NDTPs with peak cost function E were reached by BARON. For the 7 x 7 test problem, the gained best value of the objective function was 589.42. The best discrete solution found for the 10x10 test problem includes the objective function value of 71.79. The obtained best discrete solutions of both test problems with peak cost function E are presented in Tables 12 and 13.

Comparison of the results for the 7 x 7 test problem with peak cost function E demonstrates that the objective function value found by BARON was smaller than those achieved by AlphaECP (-42.22%), DICOPT (-45.61%), LINDOGlobal (-46.37%) and SBB (-31.58%). BARON also attained better objective function value for the 10x10 test NDTPs with peak cost function E than AlphaECP (-11.85%), DICOPT (-10.78%), LINDOGlobal (-10.62%) and SBB (-2.62%).

Cost function F is a highly non-convex function with multiple valleys and peaks, see Fig. 1F. This function with multiple sub-optimal points often causes difficulties for gradient-based methods to find the global optimum solution. The discrete solutions of the test problems with function F were achieved by AlphaECP, DICOPT, LINDOGlobal and SBB. BARON was not able to manage the sinus functions in the MINLP models of the test NDTPs. The objective function values found for the test problems with cost function F are shown in Fig. 7. The best values of the objective functions for both test NDTPs with cost function F were calculated by SBB method, see Tables 14 and 15. For the cost function F, Table 14 indicates the best discrete solution of the 7 x 7 test problem with the objective function value of 444.58 while Table 15 demonstrates the best discrete solution of the 10 x 10 test problem with the objective function value of 246.24.

SBB found the discrete solution for the 7 x 7 test problem with cost function F which shows better objective function value than those obtained by AlphaECP (-55.98%), DICOPT (-27.23%) and LINDOGlobal (-50.63%). The objective function value gained by SBB for the 10x10 test problem was also smaller than those reached by AlphaECP (-67.97%), DICOPT (-21.94%) and LINDOGlobal (-72.15%).

5. Discussion

The following discussion is addressed to the suitability of the tested MINLP optimization methods for solving the NDTPs with different types of nonlinear cost functions. At the beginning it should be noted that the applied test problems represent combinatorial and, in most of the considered cases, non-convex MINLP problems, for which the global optimum solution is, in general, difficult to be obtained. Taking into account the complexity of the test problems and the obtained results, all five compared MINLP methods demonstrated the most favourable individual performance and found acceptable exact solutions.

The ECP method implemented in a computational system AlphaECP was found to be a very suitable MINLP optimization technique for solving NDTPs, which contain continuous arc-tangent approximations of a step piece-wise linear cost functions or quadratic cost function. Furthermore, the test results showed that the ECP method is also an applicable tool for the NDTPs with continuous arc-tangent approximation of a piece-wise linear cost function with gradients and for those with square root cost functions. However, the non-convex cost functions with valleys and peaks defined inside the NDTP model may cause difficulties for the ECP method to find high quality result in reasonable solution time.

The BR method, within the optimization software BARON, appears to be the more robust of the MINLP solution techniques. The BR optimization method was found to be very efficient MINLP search procedure for solving the NDTPs, with convex quadratic cost functions, concave square root cost functions and even for non-convex cost functions, such as the peak cost function. For the majority of executed tests with these types of cost functions, the BR method found the best solutions. On the other hand, the lack of the support for trigonometric functions reduces the applicability of the BR optimization method for solving the NDTPs.

The AP/OA/ER method of the DICOPT software was determined to be a reliable MINLP technique for solving the NDTPs that can contain a wide variety of nonlinear functions. When the searches for the optimum solutions of the test NDTPs were launched, the AP/OA/ER method usually found reasonably good solutions already in a first few major iterations and had continued to report better solutions until the time limit was reached. The AP/OA/ER method was ascertained to be suitable MINLP search procedure for the NDTPs with continuous arc-tangent approximation of a piecewise linear functions with gradients. The gained results for the test problems with quadratic cost function have indicated that the search for the global optimum of convex NDTPs may not necessarily be finished in a short solution time. On the other hand, the performed tests showed that AP/OA/ER method can obtain moderate and acceptable results even for the NDTPs with highly non-convex functions.

The BC method inside the computer package LINDOGlobal is appropriate MINLP technique for solving the NDTPs, which include convex quadratic functions. The NDTPs with concave square root functions can be solved by BC method, although, in some cases, the convergence of a high quality solution may not be easily reached. The BC method showed moderate performance for the solution of the NDTPs, with continuous arc-tangent approximation of a piece-wise linear functions with gradients. Finding high quality solutions for the NDTPs, with continuous non-convex functions such as arc-tangent approximations of a step piece-wise linear functions or functions with valleys and peaks were found to be tougher task for the BC method, which may require longer solution time.

The SBB method was stated to be a very convenient MINLP optimization method for solving the NDTPs, which comprise continuous arc-tangent approximations of piece-wise linear cost functions with gradients, quadratic cost functions or non-convex cost functions with multiple valleys and peaks. The SBB reached the best solutions for the test NDTPs with these types of cost functions. The executed tests indicated that the SBB can found acceptable results in reasonable solution time also for the NDTPs with square root cost functions. However, the non-convexities, within the NDTP model, may sometimes also cause difficulties for the SBB method to achieve the high quality solution fast enough, as it can be seen from the gained results for test problems with continuous arc-tangent approximations of a step piece-wise linear cost functions and those with peak cost functions.

The final findings are related to the MINLP solution of the convex NDTP. The test NDTPs, with quadratic cost function C, represents the convex optimization problems, for which gradient-based MINLP techniques can find the global optimum solutions, provided that the solution time limit is large enough. Gained results, for the 10 x 10 test problem with cost function C, show that tightly set solution time limit may prevent the MINLP methods to obtain the global optimum solution even for convex NDTPs. Since the 7 x 7 test problem included larger number of decision variables and smaller number of constraints than the 10 x 10 test problem, the optimization results also showed that the number of constraints had larger influence on the MINLP solution of the test NDTPs, with cost function C, than the number of decision variables.

Conclusions

The aim of this paper was to present the suitability of five different state-of-the-art MINLP methods, specifically for the exact optimum solution of the NDTP. The evaluated MINLP methods included the extended cutting plane method, the branch and reduce method, the augmented penalty/outer-approximation/equality-relaxation method, the branch and cut method, and the simple branch and bound method. The MINLP methods were tested on a set of NDTPs from the literature.

The considered test problems comprehend the 7 x 7 and the 10 x 10 node problems with six different nonlinear continuous cost functions. A solution time limit per test problem was determined for the MINLP methods to perform the optimization. The gained solutions were compared and a correlative evaluation of the considered MINLP methods was shown to demonstrate their suitability for solving the NDTPs.

Based on the presented results, the most performed tests show that each MINLP method was able to solve a specific NDTP within determined solution time to a better solution than the other considered MINLP techniques. Such differences between the gained results were expected to a certain degree since the applied test problems represent combinatorial and, in most of the considered cases, non-convex MINLP problems for which the global optimum solution is, in general, difficult to be obtained. Nevertheless, all five compared MINLP methods demonstrated the most favourable individual performance and found acceptable exact solutions for the applied test NDTPs. None of the evaluated MINLP methods was found to be generally better than the others.

Caption: Fig. 1. Cost functions

Acknowledgements

This research was supported by the Slovenian Research Agency through research programme P2-0129 'Development, modelling and optimization of structures and processes in civil engineering and traffic'.

References

Agrali, S.; Geunes, J.; Taskin, Z. C. 2012. A facility location model with safety stock costs: analysis of the cost of single-sourcing requirements, Journal of Global Optimization 54(3): 551-581. http://dx.doi.org/10.1007/s10898-011-9777-z

Brooke, A.; Kendrick, D.; Meeraus, A.; Raman, R. 2012. GAMS--A User's Guide: Monograph. GAMS Development Corporation, Washington. 316 p.

Caputo, A. C.; Fratocchi, L.; Pelagagge, P. M. 2006. A genetic approach for freight transportation planning, Industrial Management & Data Systems 106(5): 719-738. http://dx.doi.org/10.1108/02635570610666467

Carrizosa, E.; Ushakov, A.; Vasilyev, I. 2012. A computational study of a nonlinear minsum facility location problem, Computers & Operations Research 39(11): 2625-2633. http://dx.doi.org/10.1016/j.cor.2012.01.009

Drud, A. S. 1994. CONOPT--a large-scale GRG code, ORSA Journal on Computing 6(2): 207-216. http://dx.doi.org/10.1287/ijoc.6.2.207

GAMS/CPLEX 12.0 User Notes. 2012. ILOG Inc. Kelley, J. E. 1960. The cutting-plane method for solving convex programs, Journal of the Society for Industrial and Applied Mathematics 8(4): 703-712. http://dx.doi.org/10.1137/0108053

Klansek, U.; Psunder, M. 2012. MINLP optimization model for the nonlinear discrete time-cost trade-off problem, Advances in Engineering Software 48(1): 6-16. http://dx.doi.org/10.1016/j.advengsoft.2012.01.006

Klansek, U.; Psunder, M. 2010. Solving the nonlinear transportation problem by global optimization, Transport 25(3): 314-324. http://dx.doi.org/10.3846/transport.2010.39

Kravanja, S.; Silih, S.; Kravanja, Z. 2005. The multilevel MINLP optimization approach to structural synthesis: the simultaneous topology, material, standard and rounded dimension optimization, Advances in Engineering Software 36(9): 568583. http://dx.doi.org/10.1016/j.advengsoft.2005.03.004

Lastusilta, T. 2011. GAMS MINLP solver comparisons and some improvements to the AlphaECP algorithm. Process Design and Systems Engineering Laboratory, Department of Chemical Engineering Division for Natural Sciences and Technology, Abo Akademi University, Abo, Finland. 96 p. Available from Internet: http://users.abo.fi/tlastusi/ Lastusilta2011c.pdf

Leyffer, S. 2001. Integrating SQP and branch-and-bound for mixed integer nonlinear programming, Computational Optimization and Applications 18(3): 295-309. http://dx.doi.org/10.1023/A:1011241421041

Lin, Y.; Schrage, L. 2009. The global solver in the LINDO API, Optimization Methods and Software 24(4-5): 657-668. http://dx.doi.org/10.1080/10556780902753221

Michalewicz, Z.; Vignaux, G. A.; Hobbs, M. 1991. A nonstandard genetic algorithm for the nonlinear transportation problem, ORSA Journal on Computing 3(4): 307-316. http://dx.doi.org/10.1287/ijoc.3.4.307

Monteiro, M. M.; Leal, J. E.; Raupp, F. M. P. 2010. A four-type decision-variable MINLP model for a supply chain network design, Mathematical Problems in Engineering 2010: 1-16. http://dx.doi.org/10.1155/2010/450612

Murtagh, B. A.; Saunders, M. A. 1983. MINOS 5.0 User's Guide. Systems Optimization Laboratory, Department of Operations Research, Stanford University. 118 p.

Ozsen, L.; Daskin, M. S.; Coullard, C. R. 2009. Facility location modeling and inventory management with multisourcing, Transportation Science 43(4): 455-472. http://dx.doi.org/10.1287/trsc.1090.0268

Romeijn, H. E.; Sargut, F. Z. 2011. The stochastic transportation problem with single sourcing, European Journal of Operational Research 214(2): 262-272. http://dx.doi.org/10.1016/j.ejor.2011.04.040

Ryoo, H. S.; Sahinidis, N. V. 1996. A branch-and-reduce approach to global optimization, Journal of Global Optimization 8(2): 107-138. http://dx.doi.org/10.1007/BF00138689

Sahinidis, N.; Tawarmalani, M. 2008. BARON, in GAMS--The Solver Manuals. GAMS Development Corporation, Washington, 19-32. Available from Internet: http://faculty.ses. wsu.edu/LaFrance/Linux-Server/GAMS-All-Solvers.pdf

Viswanathan, J.; Grossmann, I. E. 1990. A combined penalty function and outer-approximation method for MINLP optimization, Computers & Chemical Engineering 14(7): 769-782. http://dx.doi.org/10.1016/0098-1354(90)87085-4

Westerlund, T.; Pettersson, F. 1995. An extended cutting plane method for solving convex MINLP problems, Computers and Chemical Engineering 19(Suppl. 1): 131-136. http://dx.doi.org/10.1016/0098-1354(95)87027-X

Westerlund, T.; Porn, R. 2002. Solving pseudo-convex mixed integer optimization problems by cutting plane techniques, Optimization and Engineering 3(3): 253-280. http://dx.doi.org/10.1023/A:1021091110342

Uros Klansek

Faculty of Civil Engineering, University of Maribor, Slovenia

Submitted 20 February 2013; accepted 9 April 2013; first published online 16 October 2013

Corresponding author: Uros Klansek

E-mail: uros.klansek@um.si
Table 1. 7x7 cost matrix and source/destination capacities

Source [s.sub.i]:         27     28    25    20    20    20     20
Destination [d.sub.j]:    20     20    20    23    26    25     26
Cost [c.sub.i,j]:         0      21    50    62    93    77    1000
                          21     0     17    54    67   1000    48
                          50     17    0     60    98    67     25
                          62     54    60    0     27   1000    38
                          93     67    98    27    0     47     42
                          77    1000   67   1000   47    0      35
                         1000    48    25    38    42    35     0

Table 2. 10x10 cost matrix and source/destination capacities

Source [s.sub.i]:   8    8    2    26   12   1    6    18   18   1
Destination         19   2    33   5    11   11   2    14   2    1
  [d.sub.j]:
Cost [c.sub.i,j]:   15   3    23   1    19   14   6    16   41   33
                    13   17   30   36   20   17   26   19   3    33
                    37   17   30   5    48   27   8    25   36   21
                    13   13   31   7    35   11   20   41   34   3
                    31   24   8    30   28   33   2    8    1    8
                    32   36   12   9    18   1    44   49   11   11
                    49   6    17   0    42   45   22   9    10   47
                    2    21   18   40   47   27   27   40   19   42
                    13   16   25   21   19   0    32   20   32   35
                    23   42   2    0    9    30   5    29   31   29

Table 3. Cost functions

Function

A: f ([x.sub.i, j]) = arctan(PA ([x.sub.i, j] - S))/[pi] + 0.5 +
  arctan(PA ([x.sub.i, j] - 2 S))/[pi] + 0.5 +
  arctan(PA ([x.sub.i, j] - 3 S))/[pi] + 0.5 +
  arctan(PA ([x.sub.i, j] - 4 S))/[pi] + 0.5 +
  arctan(PA ([x.sub.i, j] - 5 S))/[pi] + 0.5

Function

B:f([x.sub.i, j]) = ([x.sub.i, j]/S) (arctan(PB
    [x.sub.i, j])/ [pi] + 0.5) +
  (1 - [x.sub.i, j]/S) (arctan(PB
    ([x.sub.i, j] - S))/[pi] + 0.5) +
  ([x.sub.i, j]/S - 2) (arctan(PB
    ([x.sub.i, j] - 2 S))/[pi] + 0.5)

Function

C: f([x.sub.i, j]) = [x.sub.i, j.sup.2]

Function

D: f([x.sub.i, j]) = [x.sub.i, j.sup.0.5]

Function

E: f([x.sub.i, j]) = [(1 + [([x.sub.i, j] - 2 S).sup.2]).sup.-1] +
  [(1 + [([x.sub.i, j] - 2.25 S).sup.2]).sup.-1] +
  [(1 + [([x.sub.i, j] - 1.75 S).sup.2]).sup.-1]

Function

F: f([x.sub.i, j]) = [x.sub.i, j](sin(5 [pi] [x.sub.i, j]/4 S) + 1)

Table 4. Best obtained discrete solution for the 7x7 test
problem with cost function A

Discrete transporting flow [x.sub.i,j]

20   1    1    2    1    1    1
0    19   3    1    2    1    2
0    0    16   1    1    1    6
0    0    0    18   1    1    0
0    0    0    0    20   0    0
0    0    0    0    0    20   0
0    0    0    1    1    1    17

Objective function: 171.59

Table 5. Best obtained discrete solution for the 10x10 test
problem with cost function A

Discrete transporting flow [x.sub.i,j]

2   0   3    0   3   0    0   0   0   0
4   0   4    0   0   0    0   0   0   0
0   0   2    0   0   0    0   0   0   0
3   2   4    4   4   0    2   4   2   1
0   0   12   0   0   0    0   0   0   0
0   0   1    0   0   0    0   0   0   0
1   0   5    0   0   0    0   0   0   0
9   0   0    0   0   0    0   9   0   0
0   0   1    1   4   11   0   1   0   0
0   0   1    0   0   0    0   0   0   0

Objective function: 66.89

Table 6. Best obtained discrete solution for the 7x7 test
problem with cost function B

Discrete transporting flow [x.sub.i,y]

19   0    0    4    0    4    0
1    19   0    0    4    0    4
0    1    20   0    0    0    4
0    0    0    19   1    0    0
0    0    0    0    20   0    0
0    0    0    0    0    20   0
0    0    0    0    1    1    18

Objective function: 349.98

Table 7. Best obtained discrete solution for the 10x10 test
problem with cost function B

Discrete transporting flow [x.sub.i, j]

0    0   0    0   8   0    0   0   0   0
1    0   0    0   3   0    0   2   2   0
0    0   0    0   0   0    2   0   0   0
0    2   10   3   0   10   0   0   0   1
0    0   12   0   0   0    0   0   0   0
0    0   0    0   0   1    0   0   0   0
0    0   0    2   0   0    0   4   0   0
8    0   10   0   0   0    0   0   0   0
10   0   0    0   0   0    0   8   0   0
0    0   1    0   0   0    0   0   0   0

Objective function: 169.59

Table 8. Best obtained discrete solution for the 7x7 test
problem with cost function C

Discrete transporting flow [x.sub.i, j]

20   0    1    2    2    2    0
0    20   2    2    2    0    2
0    0    17   1    1    2    4
0    0    0    18   1    0    1
0    0    0    0    20   0    0
0    0    0    0    0    20   0
0    0    0    0    0    1    19

Objective function: 2,648.00

Table 9. Best obtained discrete solution for the 10x10 test
problem with cost function C

Discrete transporting flow [x.sub.i, j]

1    0   3   0   2   0   0   2   0   0
1    0   2   0   2   0   0   2   1   0
0    0   2   0   0   0   0   0   0   0
4    2   4   5   2   3   2   2   1   1
0    0   8   0   1   0   0   3   0   0
0    0   1   0   0   0   0   0   0   0
0    0   4   0   0   0   0   2   0   0
11   0   5   0   1   0   0   1   0   0
2    0   3   0   3   8   0   2   0   0
0    0   1   0   0   0   0   0   0   0

Objective function: 4,466.00

Table 10. Best obtained discrete solution for the 7x7 test
problem with cost function D

Discrete transporting flow [x.sub.i, j]

20   7    0    0    0    0    0
0    13   15   0    0    0    0
0    0    5    0    0    0    20
0    0    0    20   0    0    0
0    0    0    0    20   0    0
0    0    0    0    0    20   0
0    0    0    3    6    5    6

Objective function: 480.16

Table 11. Best obtained discrete solution for the 10x10 test
problem with cost function D

Discrete transporting flow [x.sub.i, j]

1    2   0    5   0    0   0   0   0   0
0    0   0    0   0    0   0   8   0   0
0    0   0    0   0    0   2   0   0   0
0    0   22   0   0    3   0   0   0   1
0    0   10   0   0    0   0   0   2   0
0    0   0    0   0    1   0   0   0   0
0    0   0    0   0    0   0   6   0   0
18   0   0    0   0    0   0   0   0   0
0    0   0    0   11   7   0   0   0   0
0    0   1    0   0    0   0   0   0   0

Objective function: 377.25

Table 12. Best obtained discrete solution for the 7x7 test
problem with cost function E

Discrete transporting flow [x.sub.i, j]

1    0    0    0    0    0    26
0    0    0    0    15   13   0
0    0    0    14   11   0    0
0    0    0    8    0    12   0
0    0    20   0    0    0    0
0    20   0    0    0    0    0
19   0    0    1    0    0    0

Objective function: 589.42

Table 13. Best obtained discrete solution for the 10x10 test
problem with cost function E

Discrete transporting flow [x.sub.i, j]

0    1   0    3   2   0    0   2   0   0
1    0   1    0   2   0    0   2   2   0
0    0   0    1   0   0    0   1   0   0
0    0   26   0   0   0    0   0   0   0
0    0   3    0   2   0    2   4   0   1
0    0   0    0   1   0    0   0   0   0
0    1   1    1   0   0    0   3   0   0
17   0   1    0   0   0    0   0   0   0
1    0   1    0   3   11   0   2   0   0
0    0   0    0   1   0    0   0   0   0

Objective function: 71.79

Table 14. Best obtained discrete solution for the 7x7 test
problem with cost function F

Discrete transporting flow [x.sub.i, j]

20   1    0    0    6    0    0
0    19   9    0    0    0    0
0    0    11   0    0    2    12
0    0    0    20   0    0    0
0    0    0    0    18   2    0
0    0    0    0    0    20   0
0    0    0    3    2    1    14

Objective function: 444.58

Table 15. Best obtained discrete solution for the 10x10 test
problem with cost function F

Discrete transporting flow [x.sub.i, j]

6   1   0    1   0   0    0   0   0   0
6   0   0    0   0   0    0   0   2   0
0   0   0    1   0   0    1   0   0   0
0   1   22   3   0   0    0   0   0   0
0   0   0    0   5   0    0   7   0   0
0   0   0    0   0   0    0   0   0   1
0   0   5    0   0   0    0   1   0   0
6   0   6    0   6   0    0   0   0   0
1   0   0    0   0   11   0   6   0   0
0   0   0    0   0   0    1   0   0   0

Objective function: 246.24

Fig. 2. Objective function values for test problems with
cost function A

Test problems with cost function A

             Objective function value

              7 x 7     10 x
              test      10 test
              problem   problem

AlphaECP      171.59    66.89
DICOPT        190.89    92.38
LINDOGlobal   322.87    86.86
SBB           244.13    91.37

Note: Table made from bar graph.

Fig. 3. Objective function values for test problems
with cost function B

Test problems with cost function B

            Objective function value

              7 x 7     10 x
              test      10 test
              problem   problem

AlphaECP      362.96    176.59
DICOPT        350.97    176.59
LINDOGlobal   397.46    177.99
SBB           349.98    169.59

Note: Table made from bar graph.

Fig. 4. Objective function values for test problems
with cost function C

Test problems with cost function C

            Objective function value

              7 x 7     10 x
              test      10 test
              problem   problem

AlphaECP      2648      4530
BARON         2648      4538
DICOPT        2648      5123
LINDOGlobal   2648      4758
SBB           2648      4466

Note: Table made from bar graph.

Fig. 5. Objective function values for test problems
with cost function D

Test problems with cost function D

            Objective function value

              7 x 7     10 x
              test      10 test
              problem   problem

AlphaECP      556.21    404.18
BARON         480.16    377.25
DICOPT        601.78    443.55
LINDOGlobal   480.16    487.58
SBB           557.81    427.50

Note: Table made from bar graph.

Fig. 6. Objective function values for test problems
with cost function E

Test problems with cost function E

            Objective function value

              7 x 7     10 x
              test      10 test
              problem   problem

AlphaECP      1020.12   81.45
BARON         598.42    71.79
DICOPT        1083.68   80.47
LINDOGlobal   1099.15   80.33
SBB           861.45    73.73

Note: Table made from bar graph.

Fig. 7. Objective function values for test problems
with cost function F

Test problems with cost function F

            Objective function value

              7 x 7     10 x
              test      10 test
              problem   problem

AlphaECP      1009.95   768.78
DICOPT        610.89    315.44
LINDOGlobal   900.58    884.01
SBB           444.58    246.24

Note: Table made from bar graph.
COPYRIGHT 2014 Taylor & Francis Ltd.
No portion of this article can be reproduced without the express written permission from the copyright holder.
Copyright 2014 Gale, Cengage Learning. All rights reserved.

Article Details
Printer friendly Cite/link Email Feedback
Author:Klansek, Uros
Publication:Transport
Article Type:Author abstract
Date:Mar 1, 2014
Words:8912
Previous Article:The research journal transport: peer-reviewing process in 2013.
Next Article:Theoretical investigation of environmental development pathways in the road transport sector in the European region.
Topics:

Terms of use | Privacy policy | Copyright © 2019 Farlex, Inc. | Feedback | For webmasters