An adaptive multiphase approach for large unconditional and conditional p-median problems

A multiphase approach that incorporates demand points aggregation, Variable Neighbourhood Search (VNS) and an exact method is proposed for the solution of large-scale unconditional and conditional p-median problems. The method consists of four phases. In the first phase several aggregated problems are solved with a “Local Search with Shaking” procedure to generate promising facility sites which are then used to solve a reduced problem in Phase 2 using VNS or an exact method. The new solution is then fed into an iterative learning process which tackles the aggregated problem (Phase 3). Phase 4 is a post optimisation phase applied to the original (disaggregated) problem. For the p-median problem, the method is tested on three types of datasets which consist of up to 89,600 demand points. The first two datasets are the BIRCH and the TSP datasets whereas the third is our newly geometrically constructed dataset that has guaranteed optimal solutions. The computational experiments show that the proposed approach produces very competitive results. The proposed approach is also adapted to cater for the conditional p-median problem with interesting results.     

Relaxation-based algorithms for minimax optimization problems with resource allocation applications

We consider minimax optimization problems where each term in the objective function is a continuous, strictly decreasing function of a single variable and the constraints are linear. We develop relaxation-based algorithms to solve such problems. At each iteration, a relaxed minimax problem is solved, providing either an optimal solution or a better lower bound. We develop a general methodology for such relaxation schemes for the minimax optimization problem. The feasibility tests and formulation of subsequent relaxed problems can be done by using Phase I of the Simplex method and the Farkas multipliers provided by the final Simplex tableau when the corresponding problem is infeasible. Such relaxation-based algorithms are particularly attractive when the minimax optimization problem exhibits additional structure. We explore special structures for which the relaxed problem is formulated as a minimax problem with knapsack type constraints; efficient algorithms exist to solve such problems. The relaxation schemes are also adapted to solve certain resource allocation problems with substitutable resources. There, instead of Phase I of the Simplex method, a max-flow algorithm is used to test feasibility and formulate new relaxed problems.Corresponding author.Work was partially done while visiting AT&T Bell Laboratories.     

Assigning students to course sections using tabu search

In this paper we describe a new student registration system which has been developed at the University of Valencia, Spain. The system has two steps. First, the students make a computer-aided course selection from the courses available at the University. Thereafter, an assignment procedure allocates students to sections in order to respect two criteria: to provide the students with satisfactory schedules and to get balanced section enrollments. The assignment process has two phases. In Phase I, we obtain a set of the best solutions for each student. The algorithm is based on the construction of maximum cardinality independent sets. In Phase II, these solution sets are put together and a tabu search algorithm looks for a satisfactory balance between course sections without causing the solution obtained for each student to worsen significantly. The system was used at the beginning of the academic year 1996/97 in the Faculty of Mathematics and could be extended in the near future to the rest of the University. This revised version was published online in June 2006 with corrections to the Cover Date.     

Convergence results and numerical experiments on a linear programming hybrid algorithm

A modification of Karmarkar's algorithm for linear programming successively generates column-scaled equivalents of the original linear program, and in the scaled coordinates obtains improvements according to steepest descent directions. As an interior-feasible-preserving algorithm, termination requires a purification algorithm to obtain a dual basic optimal solution. Together the two algorithms comprise a ‘hybrid’ procedure for solving linear programs.In this paper we present some convergence results on the Phase II and Phase I portions of the scaling algorithm. We also present results of numerical experiments on examples of Klee—Minty type which show sensitivity to the starting interior-feasible point and steepest descent step size.     

Highly efficient parallel algorithm for finite difference solution to Navier–Stoke''s equation on a hypercube

It has been shown in [Nuclear Science and Engineering 93 (1986) 6799] that the finite difference discretization of Navier–Stoke's equation leads to the solution of N×N system written in the matrix form as My=B, where M is a quasi-tridiagonal having non-zero elements at the top right and bottom left corners. We present an efficient parallel algorithm on a p-processor hypercube implemented in two phases. In phase I a generalization of an algorithm due to Kowalik [High Speed Computation, Springer, New York] is developed which decomposes the above matrix system into smaller quasi-tridiagonal (p+1)×(p+1) subsystem, which is then solved in Phase II using an odd–even reduction method.     

A restriction and feasible direction algorithm for a capacity expansion problem

This paper examines the problem of optimally expanding existing capacity in order to meet an expected load in the context of an electric utility. A pre-optimization (Phase I) analysis is presented in order to easily determine (a) the capacities of existing equipments which will be used at an optimal solution; (b) the optimal (nonnegative) capacities of a subset of the new equipments to be purchased, and (c) a good quality starting solution. Having thus restricted a part of the solution to its optimal value, the problem is transformed into one of minimizing a convex, differentiable function, subject to a single generalized upper bounding constraint along with nonnegativity restrictions. An efficient specialization of a feasible directions algorithm (Phase II) is presented to solve this problem. The algorithm is versatile in that it provides a preview of whether or not all existing equipment capacity will be used in the light of available equipments, and which new equipments may be used in the optimal expansion plan. The algorithm can also solve the problem which enforces the use of all existing equipment capacity. Furhtermore, Phase I, which is the principal part of this algorithm, provides the user with insightful information. A numerical problem is analyzed to illustrate the effectiveness of the procedure.     

Convex optimization problems with arbitrary right-hand side perturbations

The problem of finding a solution to a system of mixed variational inequalities, which can be interpreted as a generalization of a primal–dual formulation of an optimization problem under arbitrary right-hand side perturbations, is considered. A number of various equilibrium type problems are particular cases of this problem. We suggest the problem to be reduced to a class of variational inequalities and propose a general descent type method to find its solution. If the primal cost function does not possess strengthened convexity properties, this descent method can be combined with a partial regularization method.     

Solitary waves and a stability analysis of an equation of short and long dispersive waves

A universal model for the interaction of long nonlinear waves and packets of short waves with long linear carrier waves is given by a system in which an equation of Korteweg–de Vries (KdV) type is coupled to an equation of nonlinear Schrödinger (NLS) type. The system has solutions of steady form in which one component is like a solitary-wave solution of the KdV equation and the other component is like a ground-state solution of the NLS equation. We study the stability of solitary-wave solutions to an equation of short and long waves by using variational methods based on the use of energy–momentum functionals and the techniques of convexity type. We use the concentration compactness method to prove the existence of solitary waves. We prove that the stability of solitary waves is determined by the convexity or concavity of a function of the wave speed.     

Regularity for Certain Nonlinear Parabolic Systems

Abstract

By means of an inequality of Poincaré type, a weak Harnack inequality for the gradient of a solution and an integral inequality of Campanato type, it is shown that a solution to certain degenerate parabolic system is locally Hölder continuous. The system is a generalization of p-Laplacian system. Using a difference quotient method and Moser type iteration it is then proved that the gradient of a solution is locally bounded. Finally using the iteration and scaling it is shown that the gradient of the solution satisfies a Campanato type integral inequality and is locally Hölder continuous.     

Interval solution of nonlinear equations using linear programming

A new computational test is proposed for nonexistence of a solution to a system of nonlinear equations in a convex polyhedral regionX. The basic idea proposed here is to formulate a linear programming problem whose feasible region contains all solutions inX. Therefore, if the feasible region is empty (which can be easily checked by Phase I of the simplex method), then the system of nonlinear equations has no solution inX. The linear programming problem is formulated by surrounding the component nonlinear functions by rectangles using interval extensions. This test is much more powerful than the conventional test if the system of nonlinear equations consists of many linear terms and a relatively small number of nonlinear terms. By introducing the proposed test to interval analysis, all solutions of nonlinear equations can be found very efficently. This work was partially supported by the Japanese Ministry of Education.     

Modeling and analysis of system reliability using phase‐type distribution closure properties

Phase‐type distribution closure properties are utilized to devise algorithms for generating reliability functions of systems with basic structures. These structures include series, parallel, K‐out‐of‐N, and standby structures with perfect/imperfect switch. The algorithms form a method for system reliability modeling and analysis based on the relationship between the system lifetime and component lifetimes for general structures. The proposed method is suitable for functional system reliability analysis, which can produce reliability functions of systems with independent components instead of only system reliability values. Once the system reliability function is obtained, other reliability measures such as the system's hazard function and mean time to failure can be obtained efficiently using only matrix algebra. Dimensional and numerical comparisons with computerized symbolic processing are also presented to show the superiority of the proposed method.     

Constructing Good Solutions for the Spanish School Timetabling Problem

In the school timetabling problem a set of lessons (combinations of classes, teachers, subjects and rooms) has to be scheduled within the school week. Considering classes, teachers and rooms as resources for the lessons, the problem may be viewed as the scheduling of a project subject to resource constraints. We have developed an algorithm with three phases. In Phase I an initial solution is built by using the scheme of parallel heuristic algorithm with priority rules, but imbedding at each period the construction of a maximum cardinality independent set on a resource graph. In Phase II a tabu search procedure starts from the solution of Phase I and obtains a feasible solution to the problem. The solution obtained is improved in Phase III. Several procedures based on the calculation of negative cost cycles and shortest paths in a solution graph are used to get more compact timetables.The algorithms have been imbedded in a package designed to solve the problem for Spanish secondary schools. The computational results show its performance on a set of real problems. Nevertheless, it can be applied to more general problems and results on a set of large random problems are also provided.     

A two-phase method for selecting IMRT treatment beam angles: Branch-and-Prune and local neighborhood search

This paper presents a new two-phase solution approach to the beam angle and fluence map optimization problem in Intensity Modulated Radiation Therapy (IMRT) planning. We introduce Branch-and-Prune (B&P) to generate a robust feasible solution in the first phase. A local neighborhood search algorithm is developed to find a local optimal solution from the Phase I starting point in the second phase. The goal of the first phase is to generate a clinically acceptable feasible solution in a fast manner based on a Branch-and-Bound tree. In this approach, a substantially reduced search tree is iteratively constructed. In each iteration, a merit score based branching rule is used to select a pool of promising child nodes. Then pruning rules are applied to select one child node as the branching node for the next iteration. The algorithm terminates when we obtain a desired number of angles in the current node. Although Phase I generates quality feasible solutions, it does not guarantee optimality. Therefore, the second phase is designed to converge Phase I starting solutions to local optimality. Our methods are tested on two sets of real patient data. Results show that not only can B&P alone generate clinically acceptable solutions, but the two-phase method consistently generates local optimal solutions, some of which are shown to be globally optimal.     

Numerical solution of the Cauchy problem for Painlevé III

We suggest a numerical method for solving the Cauchy problem for the third Painlevé equation. The solution of this problem is complicated by the fact that the unknown function can have movable singular points of the pole type, and in addition, the equation has a singularity at the points where the solution vanishes. The position of poles and zeros of the function is not given and is specified in the course of the solution. The method is based on the passage, in a neighborhood of these points, to an auxiliary system of differential equations for which the equation and the corresponding solution has no singularity in that neighborhood and at the pole or zero itself. We present the results of numerical experiments, which justify the efficiency of the suggested method.     

Reconstruction families of possibilistic structure systems

A method is presented for characterizing the family of overall systems reconstructable from a given possibilistic structure system. The technique is elaborated in terms of fuzzy relation equations.It is demonstrated that the reconstruction family of a given structure system is equivalent to the set of solutions of a special type of fuzzy relation equation. The solution set is partially ordered, and contains both minimal solutions and a unique maximum solution. When these elements are identified, all members of the reconstruction family are determined.Another characteristic of the reconstruction family is its reconstruction uncertainty, a measure of which is also developed in this paper. This measure is used to define an identifiability quotient that expresses the degree of confidence with which we may identify a single overall system given a particular structure system.     

Elliptic regularization for the semi-linear telegraph system

The solution of the semi-linear telegraph system is compared with the solution of an elliptic regularization, to which one associates two-point boundary conditions. An asymptotic approximation for the solution of the elliptic regularization is constructed. The method employed here is the boundary function method due to Vishik and Lyusternik. The problem is singularly perturbed of elliptic-hyperbolic type. To conduct this analysis, high regularity with respect to t for the solutions of both problems is required. Finally, the order of this approximation is found in different spaces of functions.     

关于耦合型对流-扩散方程组的奇异摄动边值问题

本文考虑下述耦合型对流-扩散方程组的奇异摄动边值问题:本文提出两种方法:一种是初值化解法,用这种方法,原始问题转化成一系列没有扰动的一阶微分方程或方程组的初值问题,从而得到一个渐近展开式;第二种是边值化解法,用这种方法,原始问题转化成一组没有边界层现象的边值问题,从而可以得到精确解和使用经典的数值方法去得到具有关于摄动参数ε一致的高精度数值解.     

Application of Sinc-collocation method for solving an inverse problem

In this article, the identification of an unknown time-dependent source term in an inverse problem of parabolic type with nonlocal boundary conditions is considered. The main approach is to change the inverse problem to a system of Volterra integral equations. The resulting integral equations are convolution-type, which by using Sinc-collocation method, are replaced by a system of linear algebraic equations. The convergence analysis is included, and it is shown that the error in the approximate solution is bounded in the infinity norm by the norm of the inverse of the coefficient matrix multiplied by a factor that decays exponentially with the size of the system. To show the efficiency of the present method, an example is presented. The method is easy to implement and yields very accurate results.     

A multigrid method for constrained optimal control problems

We consider the fast and efficient numerical solution of linear-quadratic optimal control problems with additional constraints on the control. Discretization of the first-order conditions leads to an indefinite linear system of saddle point type with additional complementarity conditions due to the control constraints. The complementarity conditions are treated by a primal-dual active set strategy that serves as outer iteration. At each iteration step, a KKT system has to be solved. Here, we develop a multigrid method for its fast solution. To this end, we use a smoother which is based on an inexact constraint preconditioner.We present numerical results which show that the proposed multigrid method possesses convergence rates of the same order as for the underlying (elliptic) PDE problem. Furthermore, when combined with a nested iteration, the solver is of optimal complexity and achieves the solution of the optimization problem at only a small multiple of the cost for the PDE solution.     

An efficient method to determine the optimal configuration of a flexible manufacturing system

A frequently encountered design issue for a flexible manufacturing system (FMS) is to find the lowest cost configuration, i.e. the number of resources of each type (machines, pallets, ...), which achieves a given production rate. In this paper, an efficient method to determine this optimal configuration is presented. The FMS is modelled as a closed queueing network. The proposed procedure first derives a heuristic solution and then the optimal solution. The computational complexity for finding the optimal solution is very reasonable even for large systems, except in some extreme cases. Moreover, the heuristic solution can always be determined and is very close (and often equal) to the optimal solution. A comparison with the previous method of Vinod and Solberg shows that our method performs very well.