Contributions to the quadratic assignment problem

Tree search procedures for solving the Koopmans Beckmann quadratic assignment problem (QAP) are unable to solve any reasonable size QAP's mainly because good quality lower bounds for this problem cannot be computed.The purpose of this paper is to propose a bounding technique based on the extraction from the QAP formulation, of a large linear assignment problem (which can then be solved optimally), leaving as a residual problem as ‘small’ a QAP as possible. The solution of this residual QAP can then be bounded by a separate procedure. This 2-step method produces improved bounds as compared with those produced by the direct application of the bounding algorithms to the original QAP. In addition, a procedure is described for the a priori fixing of variables in the QAP formulation, thus reducing the number of variables in the problem.     

Numerical solution of the Gel'fand-Levitan equation

The inverse Sturm-Liouville problem is solved by using the Gel'fand-Levitan equation. The equation is discretized by the trapezoidal rule and the problem reduced to solving a sequence of systems of linear equations. The convergence of the method is established. It is shown that the problem can be arbitrarily ill conditioned. Finally, the accuracy of the method is illustrated by two numerical examples.     

Lower bounds for nonlinear assignment problems using many body interactions

This paper concerns lower bounding techniques for the general α-adic assignment problem. The nonlinear objective function is linearized by the introduction of additional variables and constraints, thus yielding a mixed integer linear programming formulation of the problem. The concept of many body interactions is introduced to strengthen this formulation and incorporated in a modified formulation obtained by lifting the original representation to a higher dimensional space. This process involves two steps — (i) addition of new variables and constraints and (ii) incorporation of the new variables in the objective function. If this lifting process is repeated β times on an α-adic assignment problem along with the incorporation of higher order interactions, it results in the mixed-integer formulation of an equivalent (α + β)-adic assignment problem. The incorporation of many body interactions in the higher dimensional formulation improves its degeneracy properties and is also critical to the derivation of decomposition methods for the solution of these large scale mathematical programs in the higher dimensional space. It is shown that a lower bound to the optimal solution of the corresponding linear programming relaxation can be obtained by dualizing a subset of constraints in this formulation and solving O(N^2(α+β−1)) linear assignment problems, whose coefficients depend on the dual values. Moreover, it is proved that the optimal solution to the LP relaxation is obtained if we use the optimal duals for the solution of the linear assignment problems. This concept of many body interactions could be applied in designing algorithms for the solution of formulations obtained by lifting general MILP's. We illustrate all these concepts on the quadratic assignment problems With these decomposition bounds, we have found the provably optimal solutions of two unsolved QAP's of size 32 and have also improved upon existing lower bounds for other QAP's.     

Comments on practical implementation of Gomory's fractional algorithm

Gomory's fractional algorithm is widely used for solving integer linear programming problems. It is strongly influenced by round off errors and consequently has the disadvantage that in many cases the optimal solution is not reached. The present note describes a simple modification of this algorithm. The essential feature of this modification consists in conserving the integral structure of the problem. Thus the influence of round off errors is avoided. The power of our method is illustrated by a numerical example.     

A simultaneous projections method for linear inequalities

An iterative method for solving general systems of linear inequalities is considered. The method, a relaxed generalization of Cimmino's scheme for solving linear systems, was first suggested by Censor and Elfving. Each iterate is obtained as a convex combination of the orthogonal projections of the previous iterate on the half spaces defined by the linear inequalities. The algorithm is particularly suitable for implementation on computers with parallel processors. We prove convergence from any starting point for both consistent and nonconsistent systems (to a feasible point in the first case, and to a weighted least squares type solutions in the second).     

A strongly polynomial simplex method for the linear fractional assignment problem

In this paper we show that the complexity of the simplex method for the linear fractional assignment problem (LFAP) is strongly polynomial. Although LFAP can be solved in polynomial time using various algorithms such as Newton’s method or binary search, no polynomial time bound for the simplex method for LFAP is known.     

The extended linear assignment method for multiple criteria decision analysis based on interval-valued intuitionistic fuzzy sets

The theory of interval-valued intuitionistic fuzzy sets is useful and beneficial for handling uncertainty and imprecision in multiple criteria decision analysis. In addition, the theory allows for convenient quantification of the equivocal nature of human subjective assessments. In this paper, by extending the traditional linear assignment method, we propose a useful method for solving multiple criteria evaluation problems in the interval-valued intuitionistic fuzzy context. A ranking procedure consisting of score functions, accuracy functions, membership uncertainty indices, and hesitation uncertainty indices is presented to determine a criterion-wise preference of the alternatives. An extended linear assignment model is then constructed using a modified weighted-rank frequency matrix to determine the priority order of various alternatives. The feasibility and applicability of the proposed method are illustrated with a multiple criteria decision-making problem involving the selection of a bridge construction method. Additionally, a comparative analysis with other methods, including the approach with weighted aggregation operators, the closeness coefficient-based method, and the auxiliary nonlinear programming models, has been conducted for solving the investment company selection problem to validate the effectiveness of the extended linear assignment method.     

A Heuristic Approach to Quadratic Assignment Problem

A new algorithm for solving quadratic assignment problems is presented. The algorithm, which employs a sequential search technique, constructs a matrix of lower bounds on the costs of locating facilities at different sites. It then improves the elements of this matrix, one by one, by solving a succession of linear assignment problems. After all the elements of the matrix are improved, a feasible assignment is obtained, which results in an improved value for the objective function of the quadratic assignment problem. The procedure is repeated until the desired accuracy in the objective function value is obtained.     

An efficient parallel processing optimal control scheme for a class of nonlinear composite systems

This article presents an efficient parallel processing approach for solving the optimal control problem of nonlinear composite systems. In this approach, the original high-order coupled nonlinear two-point boundary value problem (TPBVP) derived from the Pontryagin's maximum principle is first transformed into a sequence of lower-order decoupled linear time-invariant TPBVPs. Then, an optimal control law which consists of both feedback and forward terms is achieved by using the modal series method for the derived sequence. The feedback term specified by local states of each subsystem is determined by solving a matrix Riccati differential equation. The forward term for each subsystem derived from its local information is an infinite sum of adjoint vectors. The convergence analysis and parallel processing capability of the proposed approach are also provided. To achieve an accurate feedforward-feedback suboptimal control, we apply a fast iterative algorithm with low computational effort. Finally, some comparative results are included to illustrate the effectiveness of the proposed approach.     

Benders's method revisited

The master problem in Benders's partitioning method is an integer program with a very large number of constraints, each of which is usually generated by solving the integer program with the constraints generated earlier. Computational experience shows that the subset B of those constraints of the master problem that are satisfied with equality at the linear programming optimum often play a crucial role in determining the integer optimum, in the sense that only a few of the remaining inequalities are needed. We characterize this subset B of inequalities. If an optimal basic solution to the linear program is nondegenerate in the continuous variables and has p integer-constrained basic variables, then the corresponding set B contains at most 2^p inequalities, none of which is implied by the others. We give an efficient procedure for generating an appropriate subset of the inequalities in B, which leads to a considerably improved version of Benders's method.     

一种基于匈牙利算法的二次分配问题求解方法

二次分配问题(Quadratic assignment problem,QAP)属于NP-hard组合优化难题.二次分配问题的线性化及下界计算方法,是求解二次分配问题的重要途径.以Frieze-Yadegar线性化模型和Gilmore-Lawler下界为基础,详细论述了二次分配问题线性化模型的结构特征,并分析了Gilmore-Lawler下界值往往远离目标函数最优值的原因.在此基础上,提出一种基于匈牙利算法的二次分配问题对偶上升下界求解法.通过求解QAPLIB中的部分实例,说明了方法的有效和可行性.     

A space-truss model for plain-weave coated fabrics

A coated fabric element is modelled by a stable geometrically nonlinear space truss and the problem formulated using matrix structural analysis. The solution is determined by solving the system's equations using the secant method. Results for a range of fabric properties and boundary loadings are presented. Experimental results are presented to demonstrate the predictive capability of the model.     

An algorithm for solving linearly constrained minimax problems

In this study, we propose an algorithm for solving a minimax problem over a polyhedral set defined in terms of a system of linear inequalities. At each iteration a direction is found by solving a quadratic programming problem and then a suitable step size along that direction is taken through an extension of Armijo's approximate line search technique. We show that each accumulation point is a Kuhn-Tucker solution and give a condition that guarantees convergence of the whole sequence of iterations. Through the use of an exact penalty function, the algorithm can be used for solving constrained nonlinear programming. In this case, our algorithm resembles that of Han, but differs from it both in the direction-finding and the line search steps.     

An algebraic approach to assignment problems

For assignment problems a class of objective functions is studied by algebraic methods and characterized in terms of an axiomatic system. It says essentially that the coefficients of the objective function can be chosen from a totally ordered commutative semigroup, which obeys a divisibility axiom. Special cases of the general model are the linear assignment problem, the linear bottleneck problem, lexicographic multicriteria problems,p-norm assignment problems and others. Further a polynomial bounded algorithm for solving this generalized assignment problem is stated. The algebraic approach can be extended to a broader class of combinatorial optimization problems.     

Constrained optimization along geodesics

An arc method is presented for solving the equality constrained nonlinear programming problem. The curvilinear search path used at each iteration of the algorithm is a second-order approximation to the geodesic of the constraint surface which emanates from the current feasible point and has the same initial heading as the projected negative gradient at that point. When the constraints are linear, or when the step length is sufficiently small, the algorithm reduces to Rosen's Gradient Projection Method.     

Methods for solving fuzzy assignment problems and fuzzy travelling salesman problems with different membership functions

Mukherjee and Basu proposed a new method for solving fuzzy assignment problems. In this paper, some fuzzy assignment problems and fuzzy travelling salesman problems are chosen which cannot be solved by using the fore-mentioned method. Two new methods are proposed for solving such type of fuzzy assignment problems and fuzzy travelling salesman problems. The fuzzy assignment problems and fuzzy travelling salesman problems which can be solved by using the existing method, can also be solved by using the proposed methods. But, there exist certain fuzzy assignment problems and fuzzy travelling salesman problems which can be solved only by using the proposed methods. To illustrate the proposed methods, a fuzzy assignment problem and a fuzzy travelling salesman problem is solved. The proposed methods are easy to understand and apply to find optimal solution of fuzzy assignment problems and fuzzy travelling salesman problems occurring in real life situations.     

平衡和不平衡运输问题与分配问题的通用迭代算法

将不平衡运输问题转化成网络最短路问题,利用Floyd算法规则,给出了一种既可以解平衡和不平衡运输问题,又可以解平衡和不平衡分配问题的通用迭代算法。与专门用于解运输问题的闭合回路法和专门用于解分配问题的匈牙利法相比,这种算法不但具有通用的优点,而且更便于在计算机上运行。     

Numerical solution of fuzzy differential equations under generalized differentiability

In this paper, we interpret a fuzzy differential equation by using the strongly generalized differentiability concept. Utilizing the Generalized Characterization Theorem, we investigate the problem of finding a numerical approximation of solutions. Then we show that any suitable numerical method for ODEs can be applied to solve numerically fuzzy differential equations under generalized differentiability. The generalized Euler approximation method is implemented and its error analysis, which guarantees pointwise convergence, is given. The method’s applicability is illustrated by solving a linear first-order fuzzy differential equation.     

Picard's successive approximation for non-linear two-point boundary-value problems

It is demonstrated that Picard's successive approximation provides a simple and efficient method for solving linear and non-linear two-point boundary-value problems. For problems, where intrinsic convergence is slow, the method can be readily modified to speed up convergence.     

On an optimal solution for maximizing the probability of retention in PPS sampling

A direct alternative proof of Keyfitz's optimal solution to the problem of maximizing the probability of retention in sampling on a second occasion is given, using techniques of elementary linear algebra. The proof and comments help one to better understand Keyfitz's solution, and they clearly demonstrate that the closed form solution of Keyfitz is one of a possible infinity of solutions offered by a linear programming approach. We also give one of those other solutions offered by linear programming, which is easy to obtain by hand calculations using only the operation of subtraction.