A Pseudo-Global Optimization Approach with Application to the Design of Containerships

In this paper, we present a new class of pseudo-global optimization procedures for solving formidable optimization problems in which the objective and/or constraints might be analytically complex and expensive to evaluate, or available only as black-box functions. The proposed approach employs a sequence of polynomial programming approximations that are constructed using the Response Surface Methodology (RSM), and embeds these within a branch-and-bound framework in concert with a suitable global optimization technique. The lower bounds constructed in this process might only be heuristic in nature, and hence, this is called a pseudo-global optimization approach. We develop two such procedures, each employing two alternative branching techniques, and apply these methods to the problem of designing containerships. The model involves five design variables given by the design draft, the depth at side, the speed, the overall length, and the maximum beam. The constraints imposed enforce the balance between the weight and the displacement, a required acceptable length to depth ratio, a restriction on the metacentric height to ensure that the design satisfies the Coast Guard wind heel criterion, a minimum freeboard level as governed by the code of federal regulations (46 CFR 42), and a lower bound on the rolling period to ensure sea-worthiness. The objective function seeks to minimize the required freight rate that is induced by the design in order to recover capital and operating costs, expressed in dollars per metric ton per nautical mile. The model formulation also accommodates various practical issues in improving the representation of the foregoing considerations, and turns out to be highly nonlinear and nonconvex. A practical test case is solved using the proposed methodology, and the results obtained are compared with those derived using a contemporary commercialized design optimization tool. The prescribed solution yields an improved design that translates to an estimated increase in profits of about $18.45 million, and an estimated 27% increase in the return on investment, over the life of the ship.     

Tightening concise linear reformulations of 0-1 cubic programs

A common strategy for solving 0-1 cubic programs is to reformulate the non-linear problem into an equivalent linear representation, which can then be submitted directly to a standard mixed-integer programming solver. Both the size and the strength of the continuous relaxation of the reformulation determine the success of this method. One of the most compact linear representations of 0-1 cubic programs is based on a repeated application of the linearization technique for 0-1 quadratic programs introduced by Glover. In this paper, we develop a pre-processing step that serves to strengthen the linear programming bound provided by this concise linear form of a 0-1 cubic program. The proposed scheme involves using optimal dual multipliers of a partial level-2 RLT formulation to rewrite the objective function of the cubic program before applying the linearization. We perform extensive computational tests on the 0-1 cubic multidimensional knapsack problem to show the advantage of our approach.     

A Branch-and-Bound Algorithm to Solve a Multi-level Network Optimization Problem

Multi-level network optimization problems arise in many contexts such as telecommunication, transportation, and electric power systems. A model for multi-level network design is formulated as a mixed-integer program. The approach is innovative because it integrates in the same model aspects of discrete facility location, topological network design, and dimensioning. We propose a branch-and-bound algorithm based on Lagrangian relaxation to solve the model. Computational results for randomly generated problems are presented showing the quality of our approach. We also present and discuss a real world problem of designing a two-level local access urban telecommunication network and solving it with the proposed methodology.     

Global optimization of nonconvex factorable programming problems

In this paper, we consider a special class of nonconvex programming problems for which the objective function and constraints are defined in terms of general nonconvex factorable functions. We propose a branch-and-bound approach based on linear programming relaxations generated through various approximation schemes that utilize, for example, the Mean-Value Theorem and Chebyshev interpolation polynomials coordinated with a Reformulation-Linearization Technique (RLT). A suitable partitioning process is proposed that induces convergence to a global optimum. The algorithm has been implemented in C++ and some preliminary computational results are reported on a set of fifteen engineering process control and design test problems from various sources in the literature. The results indicate that the proposed procedure generates tight relaxations, even via the initial node linear program itself. Furthermore, for nine of these fifteen problems, the application of a local search method that is initialized at the LP relaxation solution produced the actual global optimum at the initial node of the enumeration tree. Moreover, for two test cases, the global optimum found improves upon the solutions previously reported in the source literature. Received: January 14, 1998 / Accepted: June 7, 1999?Published online December 15, 2000     

随机需求收益最大化分销网络设计问题

研究随机需求的供应链分销网络设计问题。考虑供应商可以选择所服务的零售商,且供应商通过定价决策确定所服务的零售商。针对此问题,建立了一个非线性整数规划模型和一个等价的集合包裹模型,并利用列生成算法求解集合包裹模型,同时提出一种O（ n3 logn）时间的算法求解列生成算法中产生的子问题。数值计算表明,本文所提出的算法具有很好的最优性和可行性。     

Heuristics for Distribution Network Design in Telecommunication

A distribution network problem arises in a lower level of an hierarchical modeling approach for telecommunication network planning. This paper describes a model and proposes a lagrangian heuristic for designing a distribution network. Our model is a complex extension of a capacitated single commodity network design problem. We are given a network containing a set of sources with maximum available supply, a set of sinks with required demands, and a set of transshipment points. We need to install adequate capacities on the arcs to route the required flow to each sink, that may be an intermediate or a terminal node of an arborescence. Capacity can only be installed in discrete levels, i.e., cables are available only in certain standard capacities. Economies of scale induce the use of a unique higher capacity cable instead of an equivalent set of lower capacity cables to cover the flow requirements of any link. A path from a source to a terminal node requires a lower flow in the measure that we are closer to the terminal node, since many nodes in the path may be intermediate sinks. On the other hand, the reduction of cable capacity levels across any path is inhibited by splicing costs. The objective is to minimize the total cost of the network, given by the sum of the arc capacity (cables) costs plus the splicing costs along the nodes. In addition to the limited supply and the node demand requirements, the model incorporates constraints on the number of cables installed on each edge and the maximum number of splices at each node. The model is a NP-hard combinatorial optimization problem because it is an extension of the Steiner problem in graphs. Moreover, the discrete levels of cable capacity and the need to consider splicing costs increase the complexity of the problem. We include some computational results of the lagrangian heuristics that works well in the practice of computer aided distribution network design.     

考虑中断风险与库存成本的分销网络设计模型

分销网络可能面临各种中断风险,而分销网络设计属于战略决策问题,短期内难以改变,因而有必要在选址设计阶段就考虑中断风险。考虑中断风险,对传统的分销网络设计问题进行扩展,基于非线性0－1整数规划方法建立了一个有容量约束的设施定位-库存模型。采用遗传算法予以求解。算例分析证明了遗传算法的有效性。结果表明：在网络设计阶段就考虑中断风险可以显著降低将来可能发生的应急成本;系统对中断风险、惩罚成本因子等因素的反应敏感。     

A Hierarchy of Relaxations Leading to the Convex Hull Representation for General Discrete Optimization Problems

We consider linear mixed-integer programs where a subset of the variables are restricted to take on a finite number of general discrete values. For this class of problems, we develop a reformulation-linearization technique (RLT) to generate a hierarchy of linear programming relaxations that spans the spectrum from the continuous relaxation to the convex hull representation. This process involves a reformulation phase in which suitable products using a defined set of Lagrange interpolating polynomials (LIPs) are constructed, accompanied by the application of an identity that generalizes x(1−x) for the special case of a binary variable x. This is followed by a linearization phase that is based on variable substitutions. The constructs and arguments are distinct from those for the mixed 0-1 RLT, yet they encompass these earlier results. We illustrate the approach through some examples, emphasizing the polyhedral structure afforded by the linearized LIPs. We also consider polynomial mixed-integer programs, exploitation of structure, and conditional-logic enhancements, and provide insight into relationships with a special-structure RLT implementation.     

Effective Relaxations and Partitioning Schemes for Solving Water Distribution Network Design Problems to Global Optimality

In this paper, we address the development of a global optimization procedure for the problem of designing a water distribution network, including the case of expanding an already existing system, that satisfies specified flow demands at stated pressure head requirements. The proposed approach significantly improves upon a previous method of Sherali et al. (1998) by way of adopting tighter polyhedral relaxations, and more effective partitioning strategies in concert with a maximal spanning tree-based branching variable selection procedure. Computational experience on three standard test problems from the literature is provided to evaluate the proposed procedure. For all these problems, proven global optimal solutions within a tolerance of 10^–4% and/or within 1$ of optimality are obtained. In particular, the two larger instances of the Hanoi and the New York test networks are solved to global optimality for the very first time in the literature. A new real network design test problem based on the Town of Blacksburg Water Distribution System is also offered to be included in the available library of test cases, and related computational results are presented.     

产品回收逆向物流网络设计问题的两阶段启发式算法

针对产品回收逆向物流网络设计问题,设计了一种嵌套了模拟退火算法的两阶段启发式算法。第一阶段确定回收点的选址-分配-存储的联合决策;第二阶段确定回收中心的选址-运输的联合决策,两个阶段相互迭代,从而实现最优解的搜索。通过与遗传算法比较,证明了两阶段启发式算法是一种有效的算法。     

Interactive Solution Approach to a Multiobjective Optimization Problem in a Paper Machine Headbox Design

A successful application of the interactive multiobjective optimization method NIMBUS to a design problem in papermaking technology is described. Namely, an optimal shape design problem related to the paper machine headbox is studied. First, the NIMBUS method, the numerical headbox model, and the associated multiobjective optimization problem are described. Then, the results of numerical experiments are presented.     

Global Optimization using a Dynamical Systems Approach

We develop new algorithms for global optimization by combining well known branch and bound methods with multilevel subdivision techniques for the computation of invariant sets of dynamical systems. The basic idea is to view iteration schemes for local optimization problems – e.g. Newton’s method or conjugate gradient methods – as dynamical systems and to compute set coverings of their fixed points. The combination with bounding techniques allow for the computation of coverings of the global optima only. We show convergence of the new algorithms and present a particular implementation. Michael Dellnitz - Research of the authors is partially supported by the Deutsche Forschungsgemeinschaft within the Sonderforschungsbereich 376     

Scatter Search for Network Design Problem

A fixed charge capacitated multicommodity network design problem on undirected networks is addressed. At the present time, there exists no algorithm that can solve large instances, common in several applications, in a reasonable period of time. This paper presents an efficient procedure using a scatter search framework. Computational experiments on a large set of randomly generated problems show that this procedure is capable of finding good solutions to large-scale problems within a reasonable amount of time.     

A New Approach to a Multicriteria Optimization Problem

We present a new approach to a multicriteria optimization problem, where the objective and the constraints are linear functions. From an equivalent equilibrium problem, first suggested in [5,6,8], we show new characterizations of weakly efficient points based on the partial order induced by a nonempty closed convex cone in a finite-dimensional linear space, as in [7]. Thus, we are able to apply the analytic center cutting plane algorithm that finds equilibrium points approximately, by Raupp and Sosa [10], in order to find approximate weakly efficient solutions of MOP.     

A Network Approach to a Geometric Packing Problem

We investigate a geometric packing problem (derived from an industrial setting) that involves fitting patterns of regularly spaced disks without overlap. We first derive conditions for achieving a feasible placement of a given set of patterns and then construct a network formulation that facilitates the calculation of such a placement. A heuristic utilizing this network representation is also outlined. Additionally, we show a connection to the well-known Periodic Scheduling Problem.     

Global Solution Approach for a Nonconvex MINLP Problem in Product Portfolio Optimization

The rigorous and efficient determination of the global solution of a nonconvex MINLP problem arising from product portfolio optimization introduced by Kallrath (2003) is addressed. The objective of the optimization problem is to determine the optimal number and capacity of reactors satisfying the demand and leading to a minimal total cost. Based on the model developed by Kallrath (2003), an improved formulation is proposed, which consists of a concave objective function and linear constraints with binary and continuous variables. A variety of techniques are developed to tighten the model and accelerate the convergence to the optimal solution. A customized branch and bound approach that exploits the special mathematical structure is proposed to solve the model to global optimality. Computational results for two case studies are presented. In both case studies, the global solutions are obtained and proved optimal very efficiently in contrast to available commercial MINLP solvers.     

A Geometric Approach to Global Optimization

In this paper we consider the problem of optimizing a piecewise-linear objective function over a non-convex domain. In particular we do not allow the solution to lie in the interior of a prespecified region R. We discuss the geometrical properties of this problems and present algorithms based on combinatorial arguments. In addition we show how we can construct quite complicated shaped sets R while maintaining the combinatorial properties.     

基于时间的随机需求二级分销网络物流系统集成优化研究

分销网络设计包括设施选址、库存控制、运输等方面的设计与优化,但以往只是从战略层、战术层、运作层来分别进行各自的研究。实际上,这三个层次的决策要素之间存在着复杂的互动关系,并存在着广泛的效益悖反关系,这些在变化的环境下显得尤为突出。本文充分考虑时间因素的重要性,从物流系统的集成优化高度出发,研究建立需求随机的多分销中心多顾客的设施选址———运输路线安排———库存控制问题(ILRIP)的模型,对此设计了一个两层粒子群优化(PSO)算法,并给出了计算实例。研究结果有助于供应链分销网络的集成优化,缩短商品流转周期,提高顾客服务水平,提升竞争力。     

基于BP神经网络的动态稳健参数设计

传统的动态稳健参数设计方法(田口方法)虽然在工业生产实践中展现了极大的方便,但是其本身也存在较大的改进空间.当调节变量不存在时,传统的田口方法难以实现;此外,田口方法只能根据所选取的参数水平得到最优参数组合,而这种所谓的最优结果有时并不符合实际的需要.首先构建BP神经网络模型,利用训练后的BP神经网络获得参数设计中质量特性、噪声因子以及各参数间的动态关系;然后,利用超拉丁方抽样,计算信号与特性参数间的斜率,并由此将动态稳健参数设计的寻优问题转化为相应的非线性规划问题;最后,利用次序二次规划(SQP)算法解决并优化动态稳健参数的设计。此外,我们选取了一个简单的数据案例对本文提出的方法的有效性进行了说明.     

A Zoom-In Approach to Design SDH Mesh Restorable Networks

Mesh restorable networks based on SONET (Synchronous Optical Network, standard optical transmission technology widely accepted and implemented in North America) or SDH (Synchronous Digital Hierarchy, the European standard currently adopted by the major European telecom operators) are an economically attractive solution in areas where high demand and high connectivity are involved (Wu, 1995). In these networks, the reconfiguration capability of the digital cross connect systems (DCS) allows to reroute the demand affected by network failures. The degree of sharing of spare capacity in networks based on this architecture is high.This paper presents a heuristic algorithm for solving the near-optimal design of SDH mesh-type link restorable networks, i.e. determining the network topology and assigning the capacity to transport the demand in normal situations and to allow full link restorability in case of single link failures. The algorithm is based on a Zoom-In technique, a novel approach which forms a compromise between sequential and integrated techniques. The different building blocks of the algorithm are tested extensively and compared with other results mentioned in literature. Comparison of the simulation results for the overall design problem with other solution techniques indicates that the Zoom-In method is a quite promising approach, able to combine the accuracy of integrated approaches with the calculation speed of sequential approaches.