An approach for solving a class of transportation scheduling problems

An algorithm is developed for solving a class of transportation scheduling problems. It applies for a variety of problems such as: the Combining Truck Trip problem, the Delivery problem, the School Bus problem, the Assignment of Buses to Schedules, and the Travelling Salesman problem. The objective functions of the above problems differ from each other. Yet, by using the “savings method” proposed by Clarke and Wright, and extended by Gaskell, we are able to define each one of the above problems as a series of assignment problems. The cost matrix entries of each one of the assignment problems are a function of the constraints of the particular routing or scheduling problem. The solution to the assignment problem determines an upper bound of the optimal solution to the original problem. By combining the above procedure with a Branch and Bound procedure, it is possible to obtain the optimal solution in a finite number of steps. In some cases the Branch and Bound process can be eliminated due to the nature of the problem and in those cases the algorithm is efficient.     

Mathematical programming via the least-squares method

The least-squares method is used to obtain a stable algorithm for a system of linear inequalities as well as linear and nonlinear programming. For these problems the solution with minimal norm for a system of linear inequalities is found by solving the non-negative least-squares (NNLS) problem. Approximate and exact solutions of these problems are discussed. Attention is mainly paid to finding the initial solution to an LP problem. For this purpose an NNLS problem is formulated, enabling finding the initial solution to the primal or dual problem, which may turn out to be optimal. The presented methods are primarily suitable for ill-conditioned and degenerate problems, as well as for LP problems for which the initial solution is not known. The algorithms are illustrated using some test problems.     

Pointwise Control of the Burgers Equation and Related Nash Equilibrium Problems: Computational Approach

This article is concerned with the numerical solution of multiobjective control problems associated with nonlinear partial differential equations and more precisely the Burgers equation. For this kind of problems, we look for the Nash equilibrium, which is the solution to a noncooperative game. To compute the solution of the problem, we use a combination of finite-difference methods for the time discretization, finite-element methods for the space discretization, and a quasi-Newton BFGS algorithm for the iterative solution of the discrete control problem. Finally, we apply the above methodology to the solution of several tests problems. To be able to compare our results with existing results in the literature, we discuss first a single-objective control problem, already investigated by other authors. Finally, we discuss the multiobjective case.     

The role of conditioning in mesh selection algorithms for first order systems of linear two point boundary value problems

Codes for the numerical solution of two-point boundary value problems can now handle quite general problems in a fairly routine and reliable manner. When faced with particularly challenging equations, such as singular perturbation problems, the most efficient codes use a highly non-uniform grid in order to resolve the non-smooth parts of the solution trajectory. This grid is usually constructed using either a pointwise local error estimate defined at the grid points or else by using a local residual control. Similar error estimates are used to decide whether or not to accept a solution. Such an approach is very effective in general providing that the problem to be solved is well conditioned. However, if the problem is ill conditioned then such grid refinement algorithms may be inefficient because many iterations may be required to reach a suitable mesh on which to compute the solution. Even worse, for ill conditioned problems an inaccurate solution may be accepted even though the local error estimates may be perfectly satisfactory in that they are less than a prescribed tolerance. The primary reason for this is, of course, that for ill conditioned problems a small local error at each grid point may not produce a correspondingly small global error in the solution. In view of this it could be argued that, when solving a two-point boundary value problem in cases where we have no idea of its conditioning, we should provide an estimate of the condition number of the problem as well as the numerical solution. In this paper we consider some algorithms for estimating the condition number of boundary value problems and show how this estimate can be used in the grid refinement algorithm.     

AN EFFECTIVE CONTINUOUS ALGORITHM FOR APPROXIMATE SOLUTIONS OF LARGE SCALE MAX-CUT PROBLEMS

An effective continuous algorithm is proposed to find approximate solutions of NP-hardmax-cut problems.The algorithm relaxes the max-cut problem into a continuous nonlinearprogramming problem by replacing n discrete constraints in the original problem with onesingle continuous constraint.A feasible direction method is designed to solve the resultingnonlinear programming problem.The method employs only the gradient evaluations ofthe objective function,and no any matrix calculations and no line searches are required.This greatly reduces the calculation cost of the method,and is suitable for the solutionof large size max-cut problems.The convergence properties of the proposed method toKKT points of the nonlinear programming are analyzed.If the solution obtained by theproposed method is a global solution of the nonlinear programming problem,the solutionwill provide an upper bound on the max-cut value.Then an approximate solution to themax-cut problem is generated from the solution of the nonlinear programming and providesa lower bound on the max-cut value.Numerical experiments and comparisons on somemax-cut test problems(small and large size)show that the proposed algorithm is efficientto get the exact solutions for all small test problems and well satisfied solutions for mostof the large size test problems with less calculation costs.     

On a free interface problem for linear ordinary differential equations and the one-phase Stefan problem

A numerical method for the solution of the one-phase Stefan problem is discussed. By discretizing the time variable the Stefan problem is reduced to a sequence of free boundary value problems for ordinary differential equations which are solved by conversion to initial value problems. The numerical solution is shown to converge to the solution of the Stefan problem with decreasing time increments. Sample calculations indicate that the method is stable provided the proper algorithm is chosen for integrating the initial value problems.     

Degeneration and regularization of the operator in the Cauchy problem for the Schrödinger equation

The Cauchy problem for the Schrödinger equation whose operator degenerates on a half-line is studied. In order to approximate a solution to the problem with degeneracy by solutions to well-posed problems, the notion of regularization for an operator with degeneracy is introduced; an approximative solution to a problem with degeneracy is defined as the limit of a sequence of regularized problems. The dependence of the approximative solution on the choice of the class of admissible regularizations is studied. The weak compactness of sequences of states determined by sequences of solutions to regularized problems in the topologies determined by the space of all bounded linear operators and by subspaces of mutually commuting bounded linear operators is investigated.     

Numerical solution by the quasi-reversibility method of unstable problems for the first-order evolution equation

Prior bounds are derived on the solution of the perturbed problem in different versions of the quasi-reversibility method used for approximate solution of unstable problems for first-order evolution equations. An example of such a problem is provided by the problem backward in time for the equation of heat conduction. Approximate solution of perturbed problems by difference methods is considered. The investigation of the difference schemes of the quasi-reversibility method relies on the general theory of p-stability of difference schemes. Specific features of solution of problems with non-self-adjoint operators are considered. Efficient difference schemes are constructed for multidimensional problems.Translated from Matematicheskoe Modelirovanie i Reshenie Obratnykh Zadach. Matematicheskoi Fiziki, pp. 93–124, 1993.     

Exact penalty property for a class of inequality-constrained minimization problems

We use the penalty approach in order to study constrained minimization problems. A penalty function is said to have the exact penalty property if there is a penalty coefficient for which a solution of an unconstrained penalized problem is a solution of the corresponding constrained problem. In this paper we establish the exact penalty property for a large class of inequality-constrained minimization problems.     

A Solution Concept for Fuzzy Multiobjective Programming Problems Based on Convex Cones

A solution concept for fuzzy multiobjective programming problems based on ordering cones (convex cones) is proposed in this paper. The notions of ordering cones and partial orderings on a vector space are essentially equivalent. Therefore, the optimality notions in a real vector space can be elicited naturally by invoking a concept similar to that of the Pareto-optimal solution in vector optimization problems. We introduce a corresponding multiobjective programming problem and a weighting problem of the original fuzzy multiobjective programming problem using linear functionals so that the optimal solution of its corresponding weighting problem is also the Pareto-optimal solution of the original fuzzy multiobjective programming problem.     

特征值反问题的迭代解法

§1.引言 近年来,由于许多应用科学,如地球物理、海洋、地质、声学、光学、量子力学和识别等问题的需要,提出了特征值反问题和广义特征值反问题.这些问题形成一类区别于经典代数特征值问题的复杂非线性问题.这类问题中只有少量在理论上、数值上有一些求解的方法,前人的工作主要集中于sturm-Liouville反问题,见[1,2,3,4].本文讨论下列各种特征值反问题:     

An optimal asymptotic-numerical method for convection dominated systems having exponential boundary layers

The convection dominated diffusion problems are studied. Higher order accurate numerical methods are presented for problems in one and two dimensions. The underlying technique utilizes a superposition of given problem into two independent problems. The first one is the reduced problem that refers to the outer or smooth solution. Stretching transformation is used to obtain the second problem for inner layer solution. The method considered for outer or degenerate problems are based on higher order Runge–Kutta methods and upwind finite differences. However, inner problem is solved analytically or asymptotically. The schemes presented are proved to be consistent and stable. Possible extensions to delay differential equations and to nonlinear problems are outlined. Numerical results for several test examples are illustrated and a comparative analysis is presented. It is observed that the method presented is highly accurate and easy to implement. Moreover, the numerical results obtained are not only comparable with the exact solution but also in agreement with the theoretical estimates.     

One nonlocal problem of determination of the temperature and density of heat sources

We consider one family of problems simulating the determination of the temperature and density of heat sources from given values of the initial and final temperature. The mathematical statement of these problems leads to the inverse problem for the heat equation, where it is required to find not only a solution of the problem, but also its right-hand side that depends only on a spatial variable. A specific feature of the considered problems is that the system of eigenfunctions of the multiple differentiation operator subject to boundary conditions of the initial problem does not have the basis property.We prove the unique existence of a generalized solution to thementioned problem.     

Inverse problems for a quasilinear hyperbolic equation in the case of moving observation point

We consider two inverse coefficient problems for a quasilinear hyperbolic equation, where the additional information used for finding the coefficients is the values of the solution on some curve. (This corresponds to measurements performed at a moving observation point.) The unknown coefficient depends on the space variable in the first inverse problem and on the solution of the equation in the second inverse problem. We prove theorems of uniqueness of solution to the inverse problems.     

Solution of a tropical optimization problem with linear constraints

An optimization problem is considered that is formulated in terms of tropical (idempotent) mathematics and consists in the minimization of a nonlinear function in the presence of linear constraints on the domain of admissible values. The objective function is defined on the set of vectors over an idempotent semifield by a matrix with the use of the operation of multiplicative conjugate transposition. The problem considered is a further generalization of several known problems in which the solution involves the calculation of the spectral radius of the matrix. This generalization implies the use of a more complicated objective function compared with that in the above-mentioned problems, and the imposition of additional constraints. To solve the new problem, an auxiliary variable is introduced that describes the minimum value of the objective function. Then the problem reduces to solving an inequality in which the auxiliary variable plays the role of a parameter. Necessary and sufficient conditions for the existence of solutions to the inequality are used to calculate the parameter, and then the general solution of the inequality is taken as a solution to the original optimization problem. Numerical examples of the solution of problems on the set of two-dimensional vectors are presented.     

Error bounds for finite element solutions of mildly nonlinear elliptic boundary value problems

Summary The equivalence in a Hilbert space of variational and weak formulations of linear elliptic boundary value problems is well known. This same equivalence is proved here for mildly nonlinear problems where the right hand side of the differential equation involves the solution function. A finite element approximation to the solution of the weak problem ina finite dimensional subspace of the original Hilbert space is defined. An inequality bounding the error in this approximation over all functions of the space is derived, and in particular this holds for an interpolant to the weak solution. Thus this inequality, together with previously known, interpolation error bounds, produces a bound on the finite element solution to this nonlinear problem. An example of a mildly nonlinear Poisson problem is given.     

Case-based reasoning for repetitive combinatorial optimization problems, part I: Framework

This article presents a case-based reasoning approach for the development of learning heuristics for solving repetitive operations research problems. We first define the subset of problems we will consider in this work: repetitive combinatorial optimization problems. We then present several general forms that can be used to select previously solved problems that might aid in the solution of the current problem, and several different techniques for actually using this information to derive a solution for the current problem. We describe both fixed forms and forms that have the ability to change as we solve more problems. A simple example for the 0–1 knapsack problem is presented.     

Scalarization of the fuzzy optimization problems

Scalarization of the fuzzy optimization problems using the embedding theorem and the concept of convex cone (ordering cone) is proposed in this paper. Two solution concepts are proposed by considering two convex cones. The set of all fuzzy numbers can be embedded into a normed space. This motivation naturally inspires us to invoke the scalarization techniques in vector optimization problems to solve the fuzzy optimization problems. By applying scalarization to the optimization problem with fuzzy coefficients, we obtain its corresponding scalar optimization problem. Finally, we show that the optimal solution of its corresponding scalar optimization problem is the optimal solution of the original fuzzy optimization problem.     

On the numerical treatment of nonconvex energy problems of mechanics

The present paper presents three numerical methods devised for the solution of hemivariational inequality problems. The theory of hemivariational inequalities appeared as a development of variational inequalities, namely an extension foregoing the assumption of convexity that is essentially connected to the latter. The methods that follow partly constitute extensions of methods applied for the numerical solution of variational inequalities. All three of them actually use the solution of a central convex subproblem as their kernel. The use of well established techniques for the solution of the convex subproblems makes up an effective, reliable and versatile family of numerical algorithms for large scale problems. The first one is based on the decomposition of the contigent cone of the (super)-potential of the problem into convex components. The second one uses an iterative scheme in order to approximate the hemivariational inequality problem with a sequence of variational inequality problems. The third one is based on the fact that nonconvexity in mechanics is closely related to irreversible effects that affect the Hessian matrix of the respective (super)-potential. All three methods are applied to solve the same problem and the obtained results are compared.     

Initial Solutions to Sets of Related Transportation Problems

Where sets of similar transportation problems are solved independently a great deal of information is wasted. A routine which has been used successfully is described; it is for use in conjunction with the Ford and Fulkerson method for solving the transportation problem, and utilizes the information provided by the optimum solution to one problem to give a good initial solution to the later problems.A similar routine could be easily developed for use with the Stepping Stone method.