Efficient algorithms for buffer space allocation

This paper describes efficient algorithms for determining how buffer space should be allocated in a flow line. We analyze two problems: a primal problem, which minimizes total buffer space subject to a production rate constraint; and a dual problem, which maximizes production rate subject to a total buffer space constraint. The dual problem is solved by means of a gradient method, and the primal problem is solved using the dual solution. Numerical results are presented. Profit optimization problems are natural generalizations of the primal and dual problems, and we show how they can be solved using essentially the same algorithms.     

Topology and Geometry Optimization of Branched Sheet Metal Products

In order to optimize branched sheet metal profiles consisting of several chambers, decisions concerning topology and geometry have to be made. This leads to a problem entailing discrete and nonlinear features. We describe an integrated approach combining both aspects. The underlying idea is to use a branch-and-bound algorithm. In each node of the branch-and-bound tree, a nonlinear optimization problem has to be solved. We describe how the branch-and-bound tree is constructed, i.e., how the topology decision can be classified in a meaningful way. Moreover, we explain how to approach the nonlinear optimization problem arising in the nodes of the tree. We conclude by presenting a numerical example. (© 2011 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Averaged Subgradient Methods for Constrained Convex Optimization and Nash Equilibria Computation

We consider the problem of finding minima of convex functions under convex inequality constraints as well as the problem of finding Nash equilibria in n -person constant sum games. We prove that both problems can be solved by algorithms whose basic principles consist of representing the original problems as infinite systems of convex inequalities which, in turn, can be approached by outer projection techniques. Experiments showing how one of these algorithms behaves in test cases are presented and, in context, we describe a numerical method for computing subgradients of convex functions.     

Analytic solutions for infinite horizon stochastic optimal control problems via finite horizon approximation: A practical guide

We show how infinite horizon stochastic optimal control problems can be solved via studying their finite horizon approximations. This often leads to analytical solutions for the infinite horizon problem by studying phase diagrams, even in cases where the complexity of the finite horizon case does not permit analytic solutions. Our approach can be applied to many problems in dynamic economics.     

Mode matching analysis for wave scattering in triple and pentafurcated spaced ducts

We present solutions to both trifurcated and pentafurcated spaced waveguides using the mode matching (or eigenfunction expansion) method. While the trifurcated problem with mean fluid flow has been solved previously using the Wiener–Hopf technique, we solve this problem to validate and demonstrate our method. We then show how we can easily generalize the method to the pentafurcated problem that has not been solved previously. We observe that mode matching method is easier to derive and generalize than the Wiener–Hopf technique. We also investigate the numerical solution in detail for various geometries to model practical exhaust systems. Copyright © 2015 John Wiley & Sons, Ltd.     

On the Stability of Sizing Optimization Problems for a Class of Nonlinearly Elastic Materials

In this work we deal with a stability aspect of sizing optimization problems for a class of nonlinearly elastic materials, where the underlying state problem is nonlinear in both the displacements and the stresses. In [14] it is shown under which conditions there exists a unique solution of discrete design problems for a body made of the considered nonlinear material, if the nonlinear state problem is solved exactly. In numerical examples the nonlinear state problem has to be solved iteratively, and therefore it can be solved only up to some small error \eps . The question of interest is how this affects the optimal solution, respectively the set of solutions, of the design problem. We show with the theory of point-to-set mappings that if the material is not too nonlinear, then the optimal design depends continuously on the error \eps . Accepted 15 March 2001. Online publication 14 August 2001.     

INITIAL VALUE TECHNIQUES FOR THE HELMHOLTZ AND MAXWELL EQUATIONS

We study the initial value problem of the Helmholtz equation with spatially variable wave number. We show that it can be stabilized by suppressing the evanescent waves. The stabilized Helmholtz equation can be solved numerically by a marching scheme combined with FFT. The resulting algorithm has complexity n^2 log n on a n x n grid. We demonstrate the efficacy of the method by numerical examples with caustics. For the Maxwell equation the same treatment is possible after reducing it to a second order system. We show how the method can be used for inverse problems arising in acoustic tomography and microwave imaging.     

Propagation of sound in a duct with mean flow

We have considered the problem of radiation of sound from a semi-infinite soft duct. This duct is symmetrically located inside a hard but infinite duct. The problem is solved when the whole fluid region inside these ducts is in motion with a constant fluid velocity. We obtained a closed form solution by using the integral transform and Wiener–Hopf technique. The graphical results are also presented which show that how effectively the unwanted noise can be reduced by proper selection of different parameters.     

A branch-and-price algorithm to solve the integrated berth allocation and yard assignment problem in bulk ports

In this research, two crucial optimization problems of berth allocation and yard assignment in the context of bulk ports are studied. We discuss how these problems are interrelated and can be combined and solved as a single large scale optimization problem. More importantly we highlight the differences in operations between bulk ports and container terminals which highlights the need to devise specific solutions for bulk ports. The objective is to minimize the total service time of vessels berthing at the port. We propose an exact solution algorithm based on a branch and price framework to solve the integrated problem. In the proposed model, the master problem is formulated as a set-partitioning problem, and subproblems to identify columns with negative reduced costs are solved using mixed integer programming. To obtain sub-optimal solutions quickly, a metaheuristic approach based on critical-shaking neighborhood search is presented. The proposed algorithms are tested and validated through numerical experiments based on instances inspired from real bulk port data. The results indicate that the algorithms can be successfully used to solve instances containing up to 40 vessels within reasonable computational time.     

A linear program for the two-hub location problem

This paper considers the discrete two-hub location problem. We need to choose two hubs from a set of nodes. The remaining nodes are to be connected to one of the two hubs which act as switching points for internodal flows. A configuration which minimizes the total flow cost needs to be found. We show that the problem can be solved in polynomial time when the hub locations are fixed. Since there are at most ways to choose the hub locations, the two-hub location problem can be solved in polynomial time. We transform the quadratic 0–1 integer program of the single allocation problem in the fixed two-hub system into a linear program and show that all extreme points of the polytope defined by the LP are integral. Also, the problem can be transformed into a minimum cut problem which can be solved efficiently by any polynomial time algorithm.     

Optimal variance stopping with linear diffusions

We study the optimal stopping problem of maximizing the variance of an unkilled linear diffusion. Especially, we demonstrate how the problem can be solved as a convex two-player zero-sum game, and reveal quite surprising application of game theory by doing so. Our main result shows that an optimal solution can, in a general case, be found among stopping times that are mixtures of two hitting times. This and other revealed phenomena together with suggested solution methods could be helpful when facing more complex non-linear optimal stopping problems. The results are illustrated by a few examples.     

Design of electricity supply networks

The problem of designing a secure electricity supply network at minimal cost is formulated as a mathematical program. It is also shown how computationally convenient new constraints may be derived and these are added to the original set. The problem is dualized and solved approximately. It is indicated how this approach can be built into a Branch-and-Bound scheme for solving the original design problem, and an illustrative example is given.     

Robust optimal feedback for terminal linear-quadratic control problems under disturbances

We consider a linear dynamic system in the presence of an unknown but bounded perturbation and study how to control the system in order to get into a prescribed neighborhood of a zero at a given final moment. The quality of a control is estimated by the quadratic functional. We define optimal guaranteed program controls as controls that are allowed to be corrected at one intermediate time moment. We show that an infinite dimensional problem of constructing such controls is equivalent to a special bilevel problem of mathematical programming which can be solved explicitely. An easy implementable algorithm for solving the bilevel optimization problem is derived. Based on this algorithm we propose an algorithm of constructing a guaranteed feedback control with one correction moment. We describe the rules of computing feedback which can be implemented in real time mode. The results of illustrative tests are given.     

The Budget Constrained Multi-Product Newsboy Problem with Reactive Production: A Problem from Entrepreneurial Network Construction

This paper develops an extended newsboy model and presents a formulation for this model. This new model has solved the budget contained multi-product newsboy problem with the reactive production. This model can be used to describe the status of entrepreneurial network construction. We use the Lagrange multiplier procedure to deal with our problem, but it is too complicated to get the exact solution. So we introduce the homotopy method to deal with it. We give the flow chart to describe how to get the solution via the homotopy method. We also illustrate our model in both the classical procedure and the homotopy method. Comparing the two methods, we can see that the homotopy method is more exact and efficient.     

On the acyclic subgraph polytope

The acyclic subgraph problem can be formulated as follows. Given a digraph with arc weights, find a set of arcs containing no directed cycle and having maximum total weight. We investigate this problem from a polyhedral point of view and determine several classes of facets for the associated acyclic subgraph polytope. We also show that the separation problem for the facet defining dicycle inequalities can be solved in polynomial time. This implies that the acyclic subgraph problem can be solved in polynomial time for weakly acyclic digraphs. This generalizes a result of Lucchesi for planar digraphs.     

Parametric global optimisation for bilevel programming

We propose a global optimisation approach for the solution of various classes of bilevel programming problems (BLPP) based on recently developed parametric programming algorithms. We first describe how we can recast and solve the inner (follower’s) problem of the bilevel formulation as a multi-parametric programming problem, with parameters being the (unknown) variables of the outer (leader’s) problem. By inserting the obtained rational reaction sets in the upper level problem the overall problem is transformed into a set of independent quadratic, linear or mixed integer linear programming problems, which can be solved to global optimality. In particular, we solve bilevel quadratic and bilevel mixed integer linear problems, with or without right-hand-side uncertainty. A number of examples are presented to illustrate the steps and details of the proposed global optimisation strategy.     

A network solution to a general vehicle scheduling problem

Dantzig and Fulkerson and later Bellmore et al. have shown that certain vehicle (tanker) scheduling problems can be formulated as minimum cost flow problems on a network. In this paper, the results of Dantzig and Fulkerson are extended to the case where more than one type of vehicle can be used in the determination of an optimal fleet. (In tanker scheduling terminology; how many small, medium and large tankers would form an optical fleet.) It is seen how the problem can be formulated as a modified transportation problem where flow in some arcs is conditioned to there being flow on certain other arcs. These “conditional” transportation problems were solved directly as linear programs and showed the peculiarity of terminating all integer in spite of having a constraint matrix, which does not satisfy the well known sufficient conditions for urimodularity. We discuss the implementation of the model and its empirical results.     

Polynomial Algorithms for a Class of Discrete Minmax Linear Programming Problems

We consider the problem of obtaining integer solutions to a minmax linear programming problem. Although this general problem is NP-complete, it is shown that a restricted version of this problem can be solved in polynomial time. For this restricted class of problems two polynomial time algorithms are suggested, one of which is strongly polynomial whenever its continuous analogue and an associated linear programming problem can be solved by a strongly polynomial algorithm. Our algorithms can also be used to obtain integer solutions for the minmax transportation problem with an inequality budget constraint. The equality constrained version of this problem is shown to be NP-complete. We also provide some new insights into the solution procedures for the continuous minmax linear programming problem.     

Shape from Shadows: A Hilbert Space Setting

We study the problem of recovering a surface from the shadows it casts on itself when lighted by the sun at various times of the day. Shadows can create both linear and nonlinear information. We will show how to incorporate both types of information in the solution. The problem is formulated and solved in a Hilbert space setting and the spline algorithm interpolating the data that result from the shadows is constructed. This algorithm is optimal in terms of the approximation error and has low cost. We furthermore derive optimal information for this problem.     

Parametric linear programming and cluster analysis

In the cluster analysis problem one seeks to partition a finite set of objects into disjoint groups (or clusters) such that each group contains relatively similar objects and, relatively dissimilar objects are placed in different groups. For certain classes of the problem or, under certain assumptions, the partitioning exercise can be formulated as a sequence of linear programs (LPs), each with a parametric objective function. Such LPs can be solved using the parametric linear programming procedure developed by Gass and Saaty [(Gass, S., Saaty, T. (1955), Naval Research Logistics Quarterly 2, 39–45)]. In this paper, a parametric linear programming model for solving cluster analysis problems is presented. We show how this model can be used to find optimal solutions for certain variations of the clustering problem or, in other cases, for an approximation of the general clustering problem.