Global Optimization of the Nonconvex Containership Design Problem Using the Reformulation-Linearization Technique

TR Number



Journal Title

Journal ISSN

Volume Title


Virginia Tech


The containership design problem involves optimizing a nonconvex objective function over a design space that is restricted by a set of constraints defined in terms of nonconvex functions. An application of standard nonlinear optimization methods to such a problem can at best attain a local optimum that need not be a global optimum. This thesis investigates the application of alternative modeling, approximation, and global optimization techniques for developing a multidisciplinary approach to the containership design problem.

The problem involves five design variables, which prioritized according to their relative importance in the model are: design draft, depth at side, speed, overall length, and maximum beam. Five constraints are imposed on the design, viz., an equality constraint to enforce the balance between the weight and the displacement, a linear inequality constraint on the length to depth ratio that is implied by the lightship weight formulation for the design to be acceptable, an inequality constraint on the metacentric height to ensure that the design satisfies the Coast Guard wind heel criterion, an inequality on the freeboard to ensure the minimum required freeboard governed by the code of federal regulations for freeboard (46 CFR 42), and an inequality constraint on the rolling period to ensure that the design satisfies the minimum required rolling period criterion. The objective function employed is the required freight rate, expressed in dollars per metric ton per nautical mile in order to recover annualized construction and operational costs. The model also accommodates various practical issues in a manner suitable to improve its representability. For example, it takes into account the discrete container stowage issue. The carrying capacity (number of containers) is expressed as a continuous function of the principal dimensions by using a linear response surface fit that in turn makes the objective function continuous. The weight-displacement balance is maintained by including draft as a design variable and imposing an equality constraint on the weight and displacement rather than introducing an internal loop to calculate draft at each iteration. This speeds up the optimization process. Also, the weight is formulated independent of the draft to ensure independence of the weight and the displacement, which simplifies the optimization process. The time for loading and unloading containers at a given port is a function of the number of cranes available. The number of cranes is formulated as a function of the length of the ship, and the resulting expression is made continuous through a linear response surface fit.

To solve this problem, we design two approaches based on employing a sequence of polynomial programming approximations, each within two alternative branch-and-bound frameworks. In the first approach, we construct a polynomial programming approximation to the containership design problem using the Response Surface Methodology (RSM) and solve this model to global optimality using the software package BARON (Branch-and-Reduce Optimization Navigator - see Sahinidis, 1996), although the Reformulation-Linearization Technique (RLT)-based procedure of Sherali and Tuncbilek (1992, 1997) offers a viable alternative (BARON itself incorporates some elements of the latter approach). The resulting solution is refined by the application of a local search method. This procedure is integrated into two alternative branch-and-bound frameworks. The motivation is that the solution of the nonconvex polynomial approximations is likely to yield solutions in the near vicinity of the true underlying global optimum, and hence, the application of a local search method initiated at such a solution has a greater prospect of detecting such a global optimum.

In the second approach, we utilize a continuous-space branch-and-bound procedure based on linear programming (LP) relaxations. These relaxations are generated through an approximation scheme that first utilizes RSM to derive polynomial approximations to the objective function and the constraints, and then applies the RLT to obtain an LP relaxation. The initial stage of this lower bounding step generates a tight, nonconvex polynomial programming relaxation for the problem, and the subsequent step constructs an LP relaxation to the resulting polynomial program via a suitable RLT procedure. The underlying motivation for these two steps is to generate a tight outer approximation of the convex envelope of the objective function over the convex hull of the feasible region. The solution obtained using the polynomial approximations is treated as a lower bound. A local search method is applied to this solution to compute an upper bound. This bounding step is then integrated into two alternative branch-and-bound frameworks. The node partitioning schemes are especially designed so that the gaps resulting from these two levels of approximations are induced to approach zero in the limit, thereby ensuring convergence to a (near) global optimum.

A comparison of the containership design obtained from the designed algorithmic approaches with that obtained from the application of the nonlinear optimization methods as in previous research, exhibits a significant improvement in the design parameters translating to a significant amount of annual cost savings. For a typical containership of the size pertaining to a test case addressed in this work, having a gross weight of 90,000 metric tons, an annual transportation capacity of 99,000 containers corresponding to an annual deadweight of 1,188,000 metric tons, and logging 119,000 nautical miles annually, the improvement in the prescribed design translates to an annual estimated savings of $ 1,862,784 (or approximately $ 1.86 million) and an estimated 27 % increase in the return on investment over the life of the ship.

The main contribution of this research is that it develops a detailed formulation and a more precise model of the containership design problem, along with suitable response surface and global optimization methodologies for prescribing an improved modeling and algorithmic approach for the highly nonconvex containership design problem.



Reformulation-Linearization Technique, Containership Design Problem., Global Optimization