On the use of Kronecker's algorithm in the generalized rational interpolation problem

Kronecker's algorithm can be used to solve the generalized rational interpolation problem. In order to present the algorithm, rational forms are used here instead of too restrictive rational fractions. The proposed algorithm is reliable as soon as the functionals that characterize the problem satisfy two precise conditions. These conditions are fulfilled in the modified Hermite rational interpolation problem and, as a consequence, in the special case of the Cauchy problem and of the Padé approximation problem. This reliability covers two properties: on one hand, every rational form resulting from the algorithm is a solution of the problem whereas, on the other hand, every solution of the problem is found by the algorithm (with the exception of a possible reduction of the rational form). However, if the algorithm yields a non-reduced rational form, then the corresponding rational fraction is not a solution of the problem.     

A branch-and-bound algorithm for the mini-max spanning forest problem

The mini-max spanning forest problem requires to find a spanning forest of an undirected graph that minimizes the maximum of the costs of constituent trees. In a previous work we proved this problem NP-hard. In the current paper we present three lower bounds for this problem and develop a branch-and-bound algorithm to solve the problem exactly. The algorithm is implemented and numerical experiments are conducted on a series of test problems. The experiments compare the performances of the proposed bounds and search strategies in the algorithm as well as investigate the effects of instance characteristics on the behavior of the algorithm. Also, extension of the problem to the case of more than two root vertices as well as to the problem of determining the root locations are discussed.     

Global optimization for the generalized polynomial sum of ratios problem

In this paper, a new deterministic global optimization algorithm is proposed for solving a fractional programming problem whose objective and constraint functions are all defined as the sum of generalized polynomial ratios, which arises in various practical problems. Due to its intrinsic difficulty, less work has been devoted to globally solving this problem. The proposed algorithm is based on reformulating the problem as a monotonic optimization problem, and it turns out that the optimal solution which is provided by the algorithm is adequately guaranteed to be feasible and to be close to the actual optimal solution. Convergence of the algorithm is shown and numerical examples are given to illustrate the feasibility and efficiency of the present algorithm.     

A heuristic algorithm for a production planning problem in an assembly system

This paper focuses on a production planning problem in an assembly system operating on a make-to-order basis. Due dates are considered as constraints in the problem, that is, tardiness is not allowed. The objective of the problem is to minimise holding costs for final product inventory as well as work-in-process inventory. A non-linear mathematical model is presented and a heuristic algorithm is developed using a solution property and a network model for defining solutions of the problem. A series of computational tests were done to compare the algorithm with a commercial planning/scheduling software and backward finite-loading methods that employ various priority rules. The results showed that the suggested algorithm outperformed the others.     

Relaxed two points projection method for solving the multiple-sets split equality problem

The multiple-sets split equality problem, a generalization and extension of the split feasibility problem, has a variety of specific applications in real world, such as medical care, image reconstruction, and signal processing. It can be a model for many inverse problems where constraints are imposed on the solutions in the domains of two linear operators as well as in the operators’ ranges simultaneously. Although, for the split equality problem, there exist many algorithms, there are but few algorithms for the multiple-sets split equality problem. Hence, in this paper, we present a relaxed two points projection method to solve the problem; under some suitable conditions, we show the weak convergence and give a remark for the strong convergence method in the Hilbert space. The interest of our algorithm is that we transfer the problem to an optimization problem, then, based on the model, we present a modified gradient projection algorithm by selecting two different initial points in different sets for the problem (we call the algorithm as two points algorithm). During the process of iteration, we employ subgradient projections, not use the orthogonal projection, which makes the method implementable. Numerical experiments manifest the algorithm is efficient.     

On the algorithm of the solution of the signorini problem

An algorithm is proposed for solving the Signorini problem /1/ in the formulation of a unilateral variational problem for the boundary functional in the zone of possible contact /2/. The algorithm is based on a dual formulation of Lagrange maximin problems for whose solution a decomposition approach is used in the following sense: a Ritz process in the basis functions that satisfy the linear constraint of the problem, the differential equation in the domain, is used in solving the minimum problem (with fixed Lagrange multipliers); the maximum problem is solved by the method of descent (a generalization of the Frank-Wolf method) under convexity constraints on the Lagrange multipliers. The algorithm constructed can be conisidered as a modification of the well-known algorithm to find the Udzawa-Arrow-Hurwitz saddle points /3, 4/. The convergence of the algorithm is investigated. A numerical analysis of the algorithm is performed in the example of a classical contact problem about the insertion of a stamp in an elastic half-plane under approximation of the contact boundary by isoparametric boundary elements. The comparative efficiency of the algorithm is associated with the reduction in the dimensionality of the boundary value problem being solved and the possibility of utilizing the calculation apparatus of the method of boundary elements to realize the solution.     

A proposal for a hybrid meta-strategy for combinatorial optimization problems

In this paper, we propose an algorithm named BDS (Bound-Driven Search) that combines features of exact and approximate methods. The proposed procedure may be seen as a local search algorithm that systematically explores (in a branch-and bound sense) the most promising nodes, thus preventing solutions from being reevaluated. Additionally, it can be regarded as an exact method as it may be able to guarantee that the solution found is optimal. We present the application of this new algorithm to a specific problem domain: the permutation flow shop scheduling problem with makespan objective. The subsequent computational experiments are encouraging, as the algorithm is able to yield exact or near exact solutions to most instances of the problem. Furthermore, the algorithm outperforms one of the best state-of-the-art algorithms for the problem.     

An efficient alorithm for the general multiple-choice knapsack problem (GMKP)

A common problem frequently faced by business firms and individual investors is to select a few investment opportunities from many available possibilities. This problem, in its simplest form, can be modeled as a 0–1 knapsack problem. In a more general investment scenario, however, we obtain a model which is a general knapsack problem with a multiple-choice constraint. To solve this problem, an efficient enumerative algorithm is developed. The algorithm includes an efficient procedure to solve the LP-relaxed problem, a reduction algorithm which may allow the initial fixing of some of the variables, and various other implicit enumeration criteria derived from the group problem. Extensive computational experience illustrates the efficiency of the algorithm and related results.     

An all-linear programming relaxation algorithm for optimizing over the efficient set

The problem (P) of optimizing a linear function over the efficient set of a multiple objective linear program has many important applications in multiple criteria decision making. Since the efficient set is in general a nonconvex set, problem (P) can be classified as a global optimization problem. Perhaps due to its inherent difficulty, it appears that no precisely-delineated implementable algorithm exists for solving problem (P) globally. In this paper a relaxation algorithm is presented for finding a globally optimal solution for problem (P). The algorithm finds an exact optimal solution to the problem after a finite number of iterations. A detailed discussion is included of how to implement the algorithm using only linear programming methods. Convergence of the algorithm is proven, and a sample problem is solved.Research supported by a grant from the College of Business Administration, University of Florida, Gainesville, Florida, U.S.A.     

GMG — A guaranteed global optimization algorithm: Application to remote sensing

We investigate the role of additional information in reducing the computational complexity of the global optimization problem (GOP). Following this approach, we develop GMG — an algorithm for finding the Global Minimum with a Guarantee. The new algorithm breaks up an originally continuous GOP into a discrete (grid) search problem followed by a descent problem. The discrete search identifies the basin of attraction of the global minimum after which the actual location of the minimizer is found upon applying a descent algorithm. The algorithm is first applied to the golf-course problem, which serves as a litmus test for its performance in the presence of both complete and degraded additional information. GMG is further assessed on a set of standard benchmark functions. We then illustrate the performance of the validated algorithm on a simple realization of the monocular passive ranging (MPR) problem in remote sensing, which consists of identifying the range of an airborne target (missile, plane, etc.) from its observed radiance. This inverse problem is set as a GOP whereby the difference between the observed and model predicted radiances is minimized over the possible ranges and atmospheric conditions. We solve the GOP using GMG and report on the performance of the algorithm.     

Inverse Eigenvalue Problem in Structural Dynamics Design

1 Introduction Structural dynamics design is to design a structure subject to the dynamic characteristics re- quirement, i.e., determine physical and geometrical parameters such that the structure has the given frequencies and (or) mode shapes. This problem often arises in engineering connected with vibration. Recently, Joseph [1], Li et al. [2,3] converted the structural dynamics design to the following inverse eigenvalue problem. GIEP Let x = (x1, , xm)T , and let A(x) and B(x) be real n…     

基于蝙蝠退火算法的无等待流水线调度问题研究

无等待流水线调度问题(no-wait flow shop scheduling problem,NWFSP)是一类比较重要的复杂生产调度问题,并已经被证明是典型的NP问题.蝙蝠算法(Bat algorithm,BA)是一种较新颖的群体智能算法.本文针对蝙蝠算法在求解无等待流水线调度问题上的不足,提出一种蝙蝠退火算法,它通过采用ROV的编码方式以实现离散问题的连续编码,同时为了避免算法早熟现象引入了模拟退火算法.算法采用基于NEH的局部搜索规则,在很大程度上提高了算法的性能.利用标准Car问题和Rec问题算例进行仿真实验,结果表明了改进算法的可行性和有效性.     

Comparison of two algorithms for solving a two‐stage bilinear stochastic programming problem with quantile criterion

The paper is devoted to solving the two‐stage problem of stochastic programming with quantile criterion. It is assumed that the loss function is bilinear in random parameters and strategies, and the random vector has a normal distribution. Two algorithms are suggested to solve the problem, and they are compared. The first algorithm is based on the reduction of the original stochastic problem to a mixed integer linear programming problem. The second algorithm is based on the reduction of the problem to a sequence of convex programming problems. Performance characteristics of both the algorithms are illustrated by an example. A modification of both the algorithms is suggested to reduce the computing time. The new algorithm uses the solution obtained by the second algorithm as a starting point for the first algorithm. Copyright © 2015 John Wiley & Sons, Ltd.     

Global optimization method for maximizing the sum of difference of convex functions ratios over nonconvex region

A global optimization algorithm is presented for maximizing the sum of difference of convex functions ratios problem over nonconvex feasible region. This algorithm is based on branch and bound framework. To obtain a difference of convex programming, the considered problem is first reformulated by introducing new variables as few as possible. By using subgradient and convex envelope, the fundamental problem of estimating lower bound in the branch and bound algorithm is transformed into a relaxed linear programming problem which can be solved efficiently. Furthermore, the size of the relaxed linear programming problem does not change during the algorithm search. Lastly, the convergence of the algorithm is analyzed and the numerical results are reported.     

一类最小-最大车辆路线问题的启发式算法研究

针对个性化和多样性的需求,建立以缩短最长子线路为目标的最小-最大车辆路径问题模型, 并提出启发式算法求解。首先,采用自然数编码,使问题变得更简洁;用最佳保留选择法,以保证群体的多样性;引入爬山算法,加强局部搜索能力;其次,对遗传算法求得的精英种群再进行禁忌搜索,保证算法能够收敛到全局最优。最后,通过实例的计算,表明本算法均优于遗传算法和禁忌搜索算法,并为大规模解决实际问题提供思路。     

NONDESCENT SUBGRADIENT METHOD FOR NONSMOOTH CONSTRAINED MINIMIZATION

A kind of nondecreasing subgradient algorithm with appropriate stopping rule has been proposed for nonsmooth constrained minimization problem. The dual theory is invoked in dealing with the stopping rule and general global minimiizing algorithm is employed as a subroutine of the algorithm. The method is expected to tackle a large class of nonsmooth constrained minimization problem.     

A new nonsmooth optimization algorithm for minimum sum-of-squares clustering problems

The minimum sum-of-squares clustering problem is formulated as a problem of nonsmooth, nonconvex optimization, and an algorithm for solving the former problem based on nonsmooth optimization techniques is developed. The issue of applying this algorithm to large data sets is discussed. Results of numerical experiments have been presented which demonstrate the effectiveness of the proposed algorithm.     

Computation of the optimal tolls on the traffic network

The present paper is devoted to the computation of optimal tolls on a traffic network that is described as fuzzy bilevel optimization problem. As a fuzzy bilevel optimization problem we consider bilinear optimization problem with crisp upper level and fuzzy lower level. An effective algorithm for computation optimal tolls for the upper level decision-maker is developed under assumption that the lower level decision-maker chooses the optimal solution as well. The algorithm is based on the membership function approach. This algorithm provides us with a global optimal solution of the fuzzy bilevel optimization problem.     

求解摩擦接触问题的一个非内点光滑化算法

给出了一个求解三维弹性有摩擦接触问题的新算法,即基于NCP函数的非内点光滑化算法．首先通过参变量变分原理和参数二次规划法,将三维弹性有摩擦接触问题的分析归结为线性互补问题的求解;然后利用NCP函数,将互补问题的求解转换为非光滑方程组的求解;再用凝聚函数对其进行光滑化,最后用NEWTON法解所得到的光滑非线性方程组．方法具有易于理解及实现方便等特点．通过线性互补问题的数值算例及接触问题实例证实了该算法的可靠性与有效性．