Order Reduction of General Nonlinear DAE Systems by Automatic Tearing

The object-oriented approach to modelling has recently made possible to build models of large-scale real systems. However, the resulting system of equations is generally a nonlinear DAE (Differential Algebraic Equations) system of large dimension, which must be reduced in some way to make it tractable for numerical solutions. A way to do this is automatic symbolic tearing, which aims at splitting the DAE system into two parts: a core consisting of a reduced implicit DAE system and a set of explicit assignments. The problem is here dealt with by a graph theoretic approach, first proving the NP-completeness in the general case, then formulating the problem with reference to a bipartite graph and finally defining an efficient and flexible algorithm for automatic tearing. It is also shown how the proposed algorithm can easily incorporate both general and domain-specific heuristic rules, and can also be used to deal with equations in vector form. The application to serial multibody systems is considered as a significant example.     

Parametric Ghost Image Processes for Fixed-Charge Problems: A Study of Transportation Networks

We present a parametric approach for solving fixed-charge problems first sketched in Glover (1994). Our implementation is specialized to handle the most prominently occurring types of fixed-charge problems, which arise in the area of network applications. The network models treated by our method include the most general members of the network flow class, consisting of generalized networks that accommodate flows with gains and losses. Our new parametric method is evaluated by reference to transportation networks, which are the network structures most extensively examined, and for which the most thorough comparative testing has been performed. The test set of fixed-charge transportation problems used in our study constitutes the most comprehensive randomly generated collection available in the literature. Computational comparisons reveal that our approach performs exceedingly well. On a set of a dozen small problems we obtain ten solutions that match or beat solutions found by CPLEX 9.0 and that beat the solutions found by the previously best heuristic on 11 out of 12 problems. On a more challenging set of 120 larger problems we uniformly obtain solutions superior to those found by CPLEX 9.0 and, in 114 out of 120 instances, superior to those found by the previously best approach. At the same time, our method finds these solutions while on average consuming 100 to 250 times less CPU time than CPLEX 9.0 and a roughly equivalent amount of CPU time as taken by the previously best method.     

A specialized primal-dual interior point method for the plastic truss layout optimization

We are concerned with solving linear programming problems arising in the plastic truss layout optimization. We follow the ground structure approach with all possible connections between the nodal points. For very dense ground structures, the solutions of such problems converge to the so-called generalized Michell trusses. Clearly, solving the problems for large nodal densities can be computationally prohibitive due to the resulting huge size of the optimization problems. A technique called member adding that has correspondence to column generation is used to produce a sequence of smaller sub-problems that ultimately approximate the original problem. Although these sub-problems are significantly smaller than the full formulation, they still remain large and require computationally efficient solution techniques. In this article, we present a special purpose primal-dual interior point method tuned to such problems. It exploits the algebraic structure of the problems to reduce the normal equations originating from the algorithm to much smaller linear equation systems. Moreover, these systems are solved using iterative methods. Finally, due to high degree of similarity among the sub-problems after preforming few member adding iterations, the method uses a warm-start strategy and achieves convergence within fewer interior point iterations. The efficiency and robustness of the method are demonstrated with several numerical experiments.     

An Eulerian–Lagrangian method for optimization problems governed by multidimensional nonlinear hyperbolic PDEs

We present a numerical method for solving tracking-type optimal control problems subject to scalar nonlinear hyperbolic balance laws in one and two space dimensions. Our approach is based on the formal optimality system and requires numerical solutions of the hyperbolic balance law forward in time and its nonconservative adjoint equation backward in time. To this end, we develop a hybrid method, which utilizes advantages of both the Eulerian finite-volume central-upwind scheme (for solving the balance law) and the Lagrangian discrete characteristics method (for solving the adjoint transport equation). Experimental convergence rates as well as numerical results for optimization problems with both linear and nonlinear constraints and a duct design problem are presented.     

Solving Linear Systems Whose Elements Are Nonlinear Functions of Intervals

The paper addresses the problem of solving linear algebraic systems the elements of which are, in the general case, nonlinear functions of a given set of independent parameters taking on their values within prescribed intervals. Three kinds of solutions are considered: (i) outer solution, (ii) interval hull solution, and (iii) inner solution. A simple direct method for computing a tight outer solution to such systems is suggested. It reduces, essentially, to inverting a real matrix and solving a system of real linear equations whose size n is the size of the original system. The interval hull solution (which is a NP-hard problem) can be easily determined if certain monotonicity conditions are fulfilled. The resulting method involves solving n+1 interval outer solution problems as well as 2n real linear systems of size n. A simple iterative method for computing an inner solution is also given. A numerical example illustrating the applicability of the methods suggested is solved.     

Numerical Solution of Hamilton-Jacobi-Bellman Equations by an Upwind Finite Volume Method

In this paper we present a finite volume method for solving Hamilton-Jacobi-Bellman(HJB) equations governing a class of optimal feedback control problems. This method is based on a finite volume discretization in state space coupled with an upwind finite difference technique, and on an implicit backward Euler finite differencing in time, which is absolutely stable. It is shown that the system matrix of the resulting discrete equation is an M-matrix. To show the effectiveness of this approach, numerical experiments on test problems with up to three states and two control variables were performed. The numerical results show that the method yields accurate approximate solutions to both the control and the state variables.     

Piecewise finite series solution of nonlinear initial value differential problem

In this paper, we apply a piecewise finite series as a hybrid analytical-numerical technique for solving some nonlinear systems of ordinary differential equations. The finite series is generated by using the Adomian decomposition method, which is an analytical method that gives the solution based on a power series and has been successfully used in a wide range of problems in applied mathematics. We study the influence of the step size and the truncation order of the piecewise finite series Adomian (PFSA) method on the accuracy of the solutions when applied to nonlinear ODEs. Numerical comparisons between the PFSA method with different time steps and truncation orders against Runge-Kutta type methods are presented. Based on the numerical results we propose a low value truncation order approach with small time step size. The numerical results show that the PFSA method is accurate and easy to implement with the proposed approach.     

Multi-objective integer programming: A general approach for generating all non-dominated solutions

In this paper we develop a general approach to generate all non-dominated solutions of the multi-objective integer programming (MOIP) Problem. Our approach, which is based on the identification of objective efficiency ranges, is an improvement over classical ε-constraint method. Objective efficiency ranges are identified by solving simpler MOIP problems with fewer objectives. We first provide the classical ε-constraint method on the bi-objective integer programming problem for the sake of completeness and comment on its efficiency. Then present our method on tri-objective integer programming problem and then extend it to the general MOIP problem with k objectives. A numerical example considering tri-objective assignment problem is also provided.     

Interactive TOPSIS algorithms for solving multi-level non-linear multi-objective decision-making problems

This paper extended the concept of the technique for order preference by similarity to ideal solution (TOPSIS) to develop a methodology for solving multi-level non-linear multi-objective decision-making (MLN-MODM) problems of maximization-type. Also, two new interactive algorithms are presented for the proposed TOPSIS approach for solving these types of mathematical programming problems. The first proposed interactive TOPSIS algorithm includes the membership functions of the decision variables for each level except the lower level of the multi-level problem. These satisfactory decisions are evaluated separately by solving the corresponding single-level MODM problems. The second proposed interactive TOPSIS algorithm lexicographically solves the MODM problems of the MLN-MOLP problem by taking into consideration the decisions of the MODM problems for the upper levels. To demonstrate the proposed algorithms, a numerical example is solved and compared the solutions of proposed algorithms with the solution of the interactive algorithm of Osman et al. (2003) [4]. Also, an example of an application is presented to clarify the applicability of the proposed TOPSIS algorithms in solving real world multi-level multi-objective decision-making problems.     

Simultaneous Job Scheduling and Resource Allocation on Parallel Machines

Most deterministic production scheduling models assume that the processing time of a job on a machine is fixed externally and known in advance of scheduling. However, in most realistic situations, apart from the machines, it requires additional resources to process jobs, and the processing time of a job is determined internally by the amount of the resources allocated. In these situations, both the cost associated with the job schedule and the cost of the resources allocated should be taken into account. Therefore, job scheduling and resource allocation should be carefully coordinated and optimized jointly in order to achieve an overall cost-effective schedule. In this paper, we study a parallel-machine scheduling model involving both job processing and resource allocation. The processing time of a job is non-increasing with the cost of the allocated resources. The objective is to minimize the total cost including the cost measured by a scheduling criterion and the cost of all allocated resources. We consider two particular problems of this model, one with the scheduling criterion being the total weighted completion time, and the other with that being the weighted number of tardy jobs. We develop a column generation based branch and bound method for finding optimal solutions for these NP-hard problems. The method first formulates the problems as set partitioning type formulations, and then solves the resulting formulations exactly by branch and bound. In the branch and bound, linear relaxations of the set partitioning type formulations are decomposed into master problems and single-machine subproblems and solved by a column generation approach. The algorithms developed based on this method are capable of solving the two problems with a medium size to optimality within a reasonable computational time.     

Symmetric difference schemes of componentwise splitting and equivalent predictor-corrector scheme based on the Godunov method as applied to multidimensional gasdynamic simulation

An approach is described for improving the accuracy of numerical solutions to multidimensional gasdynamic problems produced by Godunov’s schemes. The basic idea behind the approach is to construct symmetric difference schemes based on splitting with respect to spatial variables with the subsequent transformation into equivalent predictor-corrector schemes. It is shown that the computation of “large” values by solving the one-dimensional Riemann problem at the interface of two neighboring cells leads to approximation errors in Godunov’s schemes. It is proposed to reconstruct large values so as to eliminate this source of errors. The time integration step in the modified schemes is consistent with that in the one-dimensional schemes and, on spatially uniform meshes, is 2 and 3 times larger than that in Godunov’s classical schemes for two- and three-dimensional problems, respectively. The numerical results obtained for test problems confirm the improvement of the accuracy of solutions produced by the modified schemes.     

Overlapping Schwarz waveform relaxation method for the solution of the reaction-diffusion equation

We are interested in solving time dependent problems using domain decomposition methods. In the classical approach, one discretizes first the time dimension and then one solves a sequence of steady problems by a domain decomposition method. In this article, we treat directly the time dependent problem and we study a Schwarz waveform relaxation algorithm for the convection diffusion equation. We study the convergence of the overlapping Schwarz waveform relaxation method for solving the reaction-diffusion equation over multi-overlapped subdomains. Also we will show that the method converges linearly and superlinearly over long and short time intervals, and the convergence depends on the size of overlap. Numerical results are presented from solutions of a specific model problems to demonstrate the convergence, linear and superlinear, and the role of the overlap size.     

在材料非线性问题中的摄动有限元法

摄动法是解决非线性连续介质力学问题的一种有效方法.这种方法是建立在该问题的线性解析解的基础上的,因此,若得不到一个简单的解析解,应用这种方法去解决一些复杂的非线性问题将遇到困难.有限元法对解非线性问题也是一种十分有用的工具,然而一般来说,它需要相当长的计算时间. 本文介绍摄动有限元法.这种方法吸取上述两种方法的优点,能够解决更复杂的非线性问题,而且也能大量节省计算机的计算时间. 本文讨论了比例加载下的弹塑性力学问题,并提出一个带孔拉板的数值解.     

A new Jacobi operational matrix: An application for solving fractional differential equations

In this paper, we derived the shifted Jacobi operational matrix (JOM) of fractional derivatives which is applied together with spectral tau method for numerical solution of general linear multi-term fractional differential equations (FDEs). A new approach implementing shifted Jacobi operational matrix in combination with the shifted Jacobi collocation technique is introduced for the numerical solution of nonlinear multi-term FDEs. The main characteristic behind this approach is that it reduces such problems to those of solving a system of algebraic equations which greatly simplifying the problem. The proposed methods are applied for solving linear and nonlinear multi-term FDEs subject to initial or boundary conditions, and the exact solutions are obtained for some tested problems. Special attention is given to the comparison of the numerical results obtained by the new algorithm with those found by other known methods.     

Numerical solving dynamic problems of elastoplastic deformation of solids

Numerical schemes for solving two-dimensional dynamic problems of elasticity theory based upon several local approximations for each of the required functions are discussed. The schemes contain free parameters (dissipation constants). An explicit form of artificial dissipation of the solutions allows us to control its size and to effectively construct both explicit and implicit schemes. The principle of producing such schemes is applied to a plane dynamic problem of elasticity theory as an example. We describe a class of problems for which numerical algorithms using several local approximations for each of the required functions are constructed. Examples of solving practical problems are given.     

Solving Fractional Multicriteria Optimization Problems with Sum of Squares Convex Polynomial Data

This paper focuses on the study of finding efficient solutions in fractional multicriteria optimization problems with sum of squares convex polynomial data. We first relax the fractional multicriteria optimization problems to fractional scalar ones. Then, using the parametric approach, we transform the fractional scalar problems into non-fractional problems. Consequently, we prove that, under a suitable regularity condition, the optimal solution of each non-fractional scalar problem can be found by solving its associated single semidefinite programming problem. Finally, we show that finding efficient solutions in the fractional multicriteria optimization problems is tractable by employing the epsilon constraint method. In particular, if the denominators of each component of the objective functions are same, then we observe that efficient solutions in such a problem can be effectively found by using the hybrid method. Some numerical examples are given to illustrate our results.     

An approach for solving nonlinear multi-objective separable discrete optimization problem with one constraint

We propose an exact solution approach for solving nonlinear multi-objective optimization problems with separable discrete variables and a single constraint. The approach converts the multi-objective problem into a single objective problem by using surrogate multipliers from which we find all the solutions with objective values within a given range. We call this the surrogate target problem which is solved by using an algorithm based on the modular approach. Computational experiments demonstrate the effectiveness of this approach in solving large-scale problems. A simple example is presented to illustrate an interactive decision making process.     

Numerical solution of the Burgers’ equation by automatic differentiation

We compute the solution of the one-dimensional Burgers’ equation by marching the solution in time using a Taylor series expansion. Our approach does not require symbolic manipulation and does not involve the solution of a system of linear or non-linear algebraic equations. Instead, we use recursive formulas obtained from the differential equation to calculate exact values of the derivatives needed in the Taylor series. We illustrate the effectiveness of our method by solving four test problems with known exact solutions. The numerical solutions we obtain are in excellent agreement with the exact solutions, while being superior to other previously reported numerical solutions.     

A new approach based on the surrogating method in the project time compression problems

This paper develops a mathematical model for project time compression problems in CPM/PERT type networks. It is noted this formulation of the problem will be an adequate approximation for solving the time compression problem with any continuous and non-increasing time-cost curve. The kind of this model is Mixed Integer Linear Program (MILP) with zero-one variables, and the Benders' decomposition procedure for analyzing this model has been developed. Then this paper proposes a new approach based on the surrogating method for solving these problems. In addition, the required computer programs have been prepared by the author to execute the algorithm. An illustrative example solved by the new algorithm, and two methods are compared by several numerical examples. Computational experience with these data shows the superiority of the new approach.     

An iterative approach to solve multiobjective linear fractional programming problems

This paper suggests an iterative parametric approach for solving multiobjective linear fractional programming (MOLFP) problems which only uses linear programming to obtain efficient solutions and always converges to an efficient solution. A numerical example shows that this approach performs better than some existing algorithms. Randomly generated MOLFP problems are also solved to demonstrate the performance of new introduced algorithm.