Cooperative Strategies for Solving the Bicriteria Sparse Multiple Knapsack Problem

For hard optimization problems, it is difficult to design heuristic algorithms which exhibit uniformly superior performance for all problem instances. As a result it becomes necessary to tailor the algorithms based on the problem instance. In this paper, we introduce the use of a cooperative problem solving team of heuristics that evolves algorithms for a given problem instance. The efficacy of this method is examined by solving six difficult instances of a bicriteria sparse multiple knapsack problem. Results indicate that such tailored algorithms uniformly improve solutions as compared to using predesigned heuristic algorithms.     

人力资源多维分配问题的混合算法

针对已有多维分配问题求解算法复杂、耗时长及精度低等问题,本文将二部图中寻求最优匹配的方法进行推广,运用试分配、饱和路调整和增广路调整对多维分配问题的最优解进行搜索,提出了求解人力资源多维分配问题的最小零面优先分配混合算法和随机试分配混合算法,对算法的有效性进行了理论证明,并分析了算法的时间和空间复杂度;同时通过这两种混合算法对初始零元素数不同的代价矩阵求解时间的计算,以及与Lagrangian松弛算法和剪枝法的耗时、精度的对比,分别得到了两种混合算法的适用性和高效性,最后通过算例验证了算法的有效性。     

Analysis of Decomposition Algorithms with Benders Cuts for p-Median Problem

In this paper the algorithms for solving the p-median problem based on the Benders decomposition are investigated. A family of problems hard for solving with such algorithms is constructed and then generalized to a special NP-hard case of the p-median problem. It is shown that the effectiveness of the considered algorithms depends on the choice of the optimal values of the dual variables used in Benders cuts. In particular, the depth of the cuts can be equal to one.     

Using concave envelopes to globally solve the nonlinear sum of ratios problem

This article presents a branch and bound algorithm for globally solving the nonlinear sum of ratios problem (P). The algorithm works by globally solving a sum of ratios problem that is equivalent to problem (P). In the algorithm, upper bounds are computed by maximizing concave envelopes of a sum of ratios function over intersections of the feasible region of the equivalent problem with rectangular sets. The rectangular sets are systematically subdivided as the branch and bound search proceeds. Two versions of the algorithm, with convergence results, are presented. Computational advantages of these algorithms are indicated, and some computational results are given that were obtained by globally solving some sample problems with one of these algorithms.     

An implementable proximal point algorithmic framework for nuclear norm minimization

The nuclear norm minimization problem is to find a matrix with the minimum nuclear norm subject to linear and second order cone constraints. Such a problem often arises from the convex relaxation of a rank minimization problem with noisy data, and arises in many fields of engineering and science. In this paper, we study inexact proximal point algorithms in the primal, dual and primal-dual forms for solving the nuclear norm minimization with linear equality and second order cone constraints. We design efficient implementations of these algorithms and present comprehensive convergence results. In particular, we investigate the performance of our proposed algorithms in which the inner sub-problems are approximately solved by the gradient projection method or the accelerated proximal gradient method. Our numerical results for solving randomly generated matrix completion problems and real matrix completion problems show that our algorithms perform favorably in comparison to several recently proposed state-of-the-art algorithms. Interestingly, our proposed algorithms are connected with other algorithms that have been studied in the literature.     

Wiener-hopf equations and variational inequalities

In this paper, we show that the general variational inequality problem is equivalent to solving the Wiener-Hopf equations. We use this equivalence to suggest and analyze a number of iterative algorithms for solving general variational inequalities. We also discuss the convergence criteria for these algorithms.     

线性方程组l_1范数问题的松弛投影算法及其应用

考虑线性方程组l_1范数问题的求解,在分别将其转化为一个分裂可行问题和凸可行问题的基础上,设计了几种松弛投影算法,然后将所设计的求解方法用于信号处理问题的求解上.     

Consistent Numerical Schemes for Solving Nonlinear Inverse Source Problems with Gradient-Type Algorithms and Newton–Kantorovich Methods

In this paper, algorithms of solving an inverse source problem for systems of production–destruction equations are considered. Numerical schemes that are consistent to satisfy Lagrange’s identity for solving direct and adjoint problems are constructed. With the help of adjoint equations, a sensitivity operator with a discrete analog is constructed. It links perturbations of the measured values with those of the sought-for model parameters. This operator transforms the inverse problem to a quasilinear system of equations and allows applying Newton–Kantorovich methods to it. A numerical comparison of gradient algorithms based on consistent and inconsistent numerical schemes and a Newton–Kantorovich algorithm applied to solving an inverse source problem for a nonlinear Lorenz model is done.     

An algorithm for solving a linear two-point boundary value problem for an integrodifferential equation

family of algorithms for solving a linear two-point boundary value problem is constructed in terms of the data of the integrodifferential equation and the boundary condition involved. The convergence conditions for the algorithms are established, and necessary and sufficient conditions for the well-posedness of the problem are found.     

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.     

Exact Algorithms for Large-Scale Unconstrained Two and Three Staged Cutting Problems

In this paper we propose two exact algorithms for solving both two-staged and three staged unconstrained (un)weighted cutting problems. The two-staged problem is solved by applying a dynamic programming procedure originally developed by Gilmore and Gomory [Gilmore and Gomory, Operations Research, vol. 13, pp. 94–119, 1965]. The three-staged problem is solved by using a top-down approach combined with a dynamic programming procedure. The performance of the exact algorithms are evaluated on some problem instances of the literature and other hard randomly-generated problem instances (a total of 53 problem instances). A parallel implementation is an important feature of the algorithm used for solving the three-staged version.     

Genetic Algorithm for the Jump Number Scheduling Problem

This paper introduces genetic algorithms for the jump number scheduling problem. Given a set of tasks subject to precedence constraints, the problem is to construct a schedule to minimize the number of jumps. We show that genetic algorithms outperform the previously known Knuth and Szwarcfiter's exhaustive search algorithm when applied to some classes of orders in which no polynomial time algorithms exist in solving the jump number problem. Values for various parameters of genetic jump number algorithms are tested and results are discussed.     

Falsification of hybrid systems with symbolic reachability analysis and trajectory splicing

The falsification of a hybrid system aims at finding trajectories that violate a given safety property. This is a challenging problem, and the practical applicability of current falsification algorithms still suffers from their high time complexity. In contrast to falsification, verification algorithms aim at providing guarantees that no such trajectories exist. Recent symbolic reachability techniques are capable of efficiently computing linear constraints that enclose all trajectories of the system with reasonable precision. In this paper, we leverage the power of symbolic reachability algorithms to improve the scalability of falsification techniques. Recent approaches to falsification reduce the problem to a nonlinear optimization problem. We propose to reduce the search space of the optimization problem by adding linear state constraints obtained with a reachability algorithm. An empirical study of how varying abstractions during symbolic reachability analysis affect the performance of solving a falsification problem is presented. In addition, for solving a falsification problem, we propose an alternating minimization algorithm that solves a linear programming problem and a non-linear programming problem in alternation finitely many times. We showcase the efficacy of our algorithms on a number of standard hybrid systems benchmarks demonstrating the performance increase and number of falsifyable instances.     

求解单调变分不等式的两类迭代算法

给出了求解单调变分不等式的两类迭代算法．通过解强单调变分不等式子问题,产生两个迭代点列,都弱收敛到变分不等式的解．最后,给出了这两类新算法的收敛性分析．     

The linearization method: Principal concepts and perspective directions

The linearization method, for solving the general problem of nonlinear programming and its various modifications, is considered. On the basic ideas of the linearization method, the algorithms for solving the various problems of mathematical programming are constructed for (a) solving systems of equalities and inequalities, (b) multiobjective programming and (c) complementary problem.     

Local elimination algorithms for solving sparse discrete problems

The class of local elimination algorithms is considered that make it possible to obtain global information about solutions of a problem using local information. The general structure of local elimination algorithms is described that use neighborhoods of elements and the structural graph describing the problem structure; an elimination algorithm is also described. This class of algorithms includes local decomposition algorithms for discrete optimization problems, nonserial dynamic programming algorithms, bucket elimination algorithms, and tree decomposition algorithms. It is shown that local elimination algorithms can be used for solving optimization problems.     

Using cutting planes to solve the symmetric Travelling Salesman problem

Two algorithms using cutting planes are developed for solving the Travelling Salesman Problem. In both algorithms the problem is started with a subset of the set of constraints that define the problem (apart from integrality requirements).However, the two algorithms differ in the order in which the omitted constraints and the cutting planes that are required are generated.The computational experience obtained suggests that cutting planes can provide a competitive approach to other efficient methods of solving the problem.     

Impact of the pheromone trail on the performance of ACO algorithms for solving the <Emphasis Type="Italic">car-sequencing</Emphasis> problem

This paper compares different ant colony optimization algorithms for solving the NP-hard car-sequencing problem, which is of great practical interest. The five algorithms that are compared are the Ant System (AS), the Elitist AS, the Rank-Based AS, the Max–Min AS and the Ant Colony System. These algorithms, which are well known in the literature, differ in the way in which the pheromone trail is managed. The comparative analysis seeks to identify which algorithm best manages the learning process in solving the car-sequencing problem. Moreover, we propose a new structure for the pheromone trail specifically designed to take advantage of the type of constraints found in the car-sequencing problem. The quality of the results obtained with this new form of learning for three problem sets drawn from the literature is superior to that of the best results published and demonstrates the efficiency of this new trail structure.     

A fast ant-colony algorithm for single-machine scheduling to minimize the sum of weighted tardiness of jobs

The problem of scheduling on a single machine is considered in this paper with the objective of minimizing the sum of weighted tardiness of jobs. A new ant-colony optimization (ACO) algorithm, called fast ACO (FACO), is proposed and analysed for solving the single-machine scheduling problem. By considering the benchmark problems available in the literature for analysing the performance of algorithms for scheduling on a single machine with the consideration of weighted tardiness of jobs, we validate the appropriateness of the proposed local-search schemes and parameter settings used in the FACO. We also present a comparison of the requirements of CPU time for solving the single-machine total-weighted tardiness problem by the FACO and the existing algorithms.     

带松弛因子的Schwarz交替方法

§1.引言 Schwarz交替方法的收敛速度,依赖于子区域重迭部分的大小,重迭部分越大,收敛越快。然而重迭部分增大,必将引起计算量的增大,因此,在重迭部分不变的情况下,如何改善Schwarz交替过程的收敛速度,已成为人们感兴趣的问题。关于Schwarz算法收敛速度的讨论,许多文章都是对具体类型的微分方程展开的。