多指标动态规划的人机交互式满意权衡法

1984年,Nakayama和Sawaragi提出了一种求解静态多目标决策问题的人机交互式满 意权衡方法.本文结合动态规划的结构特点,进一步发展了Nakayama方法的基本思想,表明 该方法可以推广到用来求解多指标动态规划问题,而且通过对原方法的改进,消除了其存在的 一些不足之处.本文所提方法,在较弱的限制条件下,针对一类普遍使用的多指标动态规划模 型,可以获得决策者充分满意的解.     

Multiobjective combinatorial optimization problems with a cost and several bottleneck objective functions: An algorithm with reoptimization

This paper addresses multicriteria combinatorial optimization problems involving one cost and several bottleneck objective functions. An algorithm is developed which generates the minimal complete set of Pareto-optimal solutions. This algorithm runs in polynomial time as long as the single objective problem considering only the cost function can be solved polynomially. A reoptimization procedure is used to accelerate the convergence of the algorithm. Applications are given. Computational results on randomly generated instances and planar grid graphs concerning the minimum cost spanning tree and the shortest path problem are presented.     

Neural network approach for multicriteria solid transportation problem

In this paper, we propose neural network approach for multicriteria solid transportation problems(STP). First we suggest a neural network architecture to solve single-objective STP according to augmented Lagrange multiplier method. Due to the massive computing unit-neurons and parallel mechanism of neural network approach can solve the large scale problem efficiently and optimal solution can be got. Then we transform the original multicriteria problem into a single objective problem by global criteria method and adopt the neural network approach to solve it. By this way we can get the satisfactory solution of the original problem. The procedure and efficiency of this approach are shown with numerical simulations.     

动态网络中多规则的最短路径查询算法

最佳排序路径查询,是智能交通中的热点问题.在实际的应用中,由于最佳排序路径查询有许多限制条件,现有的算法不能有效地解决动态网络中受限制的路径查询问题.为了解决动态网络中最佳排序路径查询问题,用规则表示每个限制条件,提出了一种新的最佳排序路径查询形式,即多规则的最短路径查询.提供了统一的框架,该框架包含了路径集合查询和最短路径查询.在路径集合查询部分,为了高效地查询出满足多规则的路径集合,在广义规则树的基础上,提出一种新的树的遍历方式,即树的继承全遍历;并基于树的继承全遍历思想,提出一种剪枝技术,对路径集合进行删减,最后求得候选路径集合.在最短路径查询部分,提出一种基于动态阈值的最短路径搜索方法.通过两个真实的动态道路网络的实验验证,所提出的算法能够高效地解决多规则的最短路径查询问题.     

On the computational complexity of combinatorial flexibility problems

The concept of flexibility – originated in the context of heat exchanger networks design – is associated with a substructure which allows the same optimal value on the substructure (for example an optimal flow) as in the whole structure, for all the costs in a given range of costs. In this work, we extend the concept of flexibility to general combinatorial optimization problems, and prove several computational complexity results in this new framework. Under some monotonicity conditions, we prove that a combinatorial optimization problem can be polynomially reduced to its associated flexibility problem. However, the minimum cut, maximum weighted matching and shortest path problems have NP-complete associated flexibility problems. In order to obtain polynomial flexibility problems, we have to restrict ourselves to combinatorial optimization problems on matroids.     

A credit ranking model for a parafinancial company based on the ELECTRE-III method and a multiobjective evolutionary algorithm

Credit rating is an assessment performed by lenders or financial institutions to determine a person’s creditworthiness based on the proposed terms of the loan. Frequently, these institutions use rating models to obtain estimates for the probabilities of default for their clients (companies, organizations, government, and individuals) and to assess the risk of credit portfolios. Numerous statistical and data mining methods are used to develop such models. In this paper, the potential of a multicriteria decision-aiding approach is studied. As a first step, the proposed methodology models the problem as a multicriteria evaluation process with multiple and in some cases, conflicting dimensions, which are integrated to derive sound recommendation for DMs. The second step of the methodology involves building a multicriteria outranking model based on ELECTRE III method. An evolutionary algorithm is used to exploit the outranking model. The methodology is applied to a small-scale financial institution operating in the agricultural sector. We compare loan applications based on their attributes and the credit profile of the customer or credit applicant. Our methodology offers the flexibility of combining heterogeneous information together with the preferences of decision makers (DMs), generating both relative and fixed rules for selecting the best loan applications among new and existing customers, which is an improvement over traditional methods The results reveal that outranking models are well suited to credit rating, providing good ranking results and suitable understanding on the relative importance of the evaluation criteria.     

Automated Generation of Search Tree Algorithms for Hard Graph Modification Problems

We present a framework for an automated generation of exact search tree algorithms for NP-hard problems. The purpose of our approach is twofold—rapid development and improved upper bounds. Many search tree algorithms for various problems in the literature are based on complicated case distinctions. Our approach may lead to a much simpler process of developing and analyzing these algorithms. Moreover, using the sheer computing power of machines it may also lead to improved upper bounds on search tree sizes (i.e., faster exact solving algorithms) in comparison with previously developed hand-made search trees. Among others, such an example is given with the NP-complete Cluster Editing problem (also known as Correlation Clustering on complete unweighted graphs), which asks for the minimum number of edge additions and deletions to create a graph which is a disjoint union of cliques. The hand-made search tree for Cluster Editing had worst-case size O(2.27^k), which now is improved to O(1.92^k) due to our new method. (Herein, k denotes the number of edge modifications allowed.)     

Vertex covering by paths on trees with its applications in machine translation

Given a tree and a set of paths in the tree, the problem of finding a minimum number of paths from the given path set to cover all the vertices in the tree is investigated in the paper. To distinguish from the classical path cover problem, such an optimization problem is referred to as vertex covering by paths. The problem and its edge variant, edge covering by paths, find applications in machine translation. Complexity and algorithmic results are presented for the problem and its edge variant.     

A stabilized branch-and-price-and-cut algorithm for the multiple length cutting stock problem

Many heuristic approaches have been proposed in the literature for the multiple length cutting stock problem, while only few results have been reported for exact solution algorithms. In this paper, we present a new branch-and-price-and-cut algorithm which outperforms other exact approaches proposed so far. Our conclusions are supported on many computational experiments conducted on instances from the literature. In the second part of the paper, we investigate the use of valid dual inequalities within the previous algorithm. We show how column generation can be accelerated in all the nodes of our branching tree using such inequalities. Until now, dual inequalities have been applied only for original linear programming relaxations. Their validity within a branch-and-bound procedure has never been investigated. Our computational experiments show that extending these inequalities to the whole branch-and-bound tree can significantly improve the convergence of our branch-and-price-and-cut algorithm.     

Carousel greedy: A generalized greedy algorithm with applications in optimization

In this paper, we introduce carousel greedy, an enhanced greedy algorithm which seeks to overcome the traditional weaknesses of greedy approaches. We have applied carousel greedy to a variety of well-known problems in combinatorial optimization such as the minimum label spanning tree problem, the minimum vertex cover problem, the maximum independent set problem, and the minimum weight vertex cover problem. In all cases, the results are very promising. Since carousel greedy is very fast, it can be used to solve very large problems. In addition, it can be combined with other approaches to create a powerful, new metaheuristic. Our goal in this paper is to motivate and explain the new approach and present extensive computational results.     

Decomposition methods in multiobjective discrete-time dynamic problems

Decomposition methods for multicriteria dynamic (discrete-time) problems are derived. In these methods, the original problem is reduced to a series of multicriteria subproblems related to individual stages. Hence, the dimensionality of decision variables in each subproblem is smaller than in the original problem. The following decomposition procedures for such problems are developed: (1) a dynamic programming method, (2) a two-point boundary value problem method, (3) multilevel methods, and (4) the formulation of a temporal hierarchy. For completeness, methods for multicriteria dynamic problems are reviewed that, at the outset, transform a problem into a series of single-objective problems. Formulation of the multiobjective problem in the context of a multilayer temporal hierarchy is also presented. The temporal structure motivates problem simplification by decomposing the overall decision-making problem according to relative time scales.     

A Polynomial Time Approximation Scheme for Minimum Cost Delay-Constrained Multicast Tree under a Steiner Topology

This paper is concerned with a restricted version of minimum cost delay-constrained multicast in a network where each link has a delay and a cost. Given a source vertex $s$ and $p$ destination vertices $t_1, t_2, \ldots, t_p$ together with $p$ corresponding nonnegative delay constraints $d_1, d_2, \ldots, d_p$, many QoS multicast problems seek a minimum cost multicast tree in which the delay along the unique $s$--$t_i$ path is no more than $d_i$ for $1 \le i \le p$. This problem is NP-hard even when the topology of the multicast tree is fixed. In this paper we show that every multicast tree has an underlying Steiner topology and that every minimum cost delay-constrained multicast tree corresponds to a minimum cost delay-constrained realization of a corresponding Steiner topology. We present a fully polynomial time approximation scheme for computing a minimum cost delay-constrained multicast tree under a Steiner topology. We also present computational results of a preliminary implementation to illustrate the effectiveness of our algorithm and discuss its applications.     

A Polynomial Time Approximation Scheme for Minimum Cost Delay-Constrained Multicast Tree under a Steiner Topology

This paper is concerned with a restricted version of minimum cost delay-constrained multicast in a network where each link has a delay and a cost. Given a source vertex $s$ and $p$ destination vertices $t_1, t_2, \ldots, t_p$ together with $p$ corresponding nonnegative delay constraints $d_1, d_2, \ldots, d_p$, many QoS multicast problems seek a minimum cost multicast tree in which the delay along the unique $s$--$t_i$ path is no more than $d_i$ for $1 \le i \le p$. This problem is NP-hard even when the topology of the multicast tree is fixed. In this paper we show that every multicast tree has an underlying Steiner topology and that every minimum cost delay-constrained multicast tree corresponds to a minimum cost delay-constrained realization of a corresponding Steiner topology. We present a fully polynomial time approximation scheme for computing a minimum cost delay-constrained multicast tree under a Steiner topology. We also present computational results of a preliminary implementation to illustrate the effectiveness of our algorithm and discuss its applications.     

A nonlinear compromise scheme in multicriteria evaluation and optimization problems

The concept of a nonlinear compromise scheme in multicriteria problems of evaluation and optimization is presented. It is shown that the problem is to approximate correctly the utility function and construct a substantial mathematical model (scalar convolution) adequate to the given situation to solve various multicriteria problems. In analysis problems, this convolution is an objective function. Its extremization results in a compromise-optimal vector of arguments. An illustrative example is given. Translated from Kibernetika i Sistemnyi Analiz, No. 4, pp. 106–114, July–August 2009.     

TRANSMax II: Designing a flexible model for transit route optimization

Covering path problems date from the pioneering work of Current et al. (1984, 1985). Two basic forms were defined in their work: the shortest covering path problem and the maximal covering shortest path problem. These two problems differ in that one requires complete coverage by the defined path and the other involves determining path alternatives which cover as much as possible while keeping the path length as short as possible. The latter of these two problems, the maximal covering shortest path problem, embodies the two major goals in transit planning: that is, finding efficient paths which serve as many people as possible. Often transit routes are restricted to major road segments, and when that occurs, routes do not compete with one another unless they overlap along a street segment or at an intersection. In addition, coverage distances can be quite small, barely extending to other streets. Given this type of situation, Curtin and Biba (2011) developed a model called TRANSMax (Transit Route Arc-Node Service Maximization), which maximizes node and arc service, where service coverage is defined for only those street and node segments that are part of a route. They based their model on a structure first proposed by Vajda (1961) in formulating and solving the traveling salesman problem. Because of this structure, we demonstrate that it is possible that a route generated by their original TRANSMax model may not be Pareto optimal with respect to both distance and access. In this paper, we develop a flexible TRANSMax model formulation that finds Pareto Optimal solutions when the original form does not. We also present computational experience in solving this new model on the same street network of Curtin and Biba involving Richardson, Texas. This application allows us to make comparisons between this work and the original work of Curtin and Biba. Overall, we show that this new model can identify new, improved routes over the existing TRANSMax model.     

基于组合核的蛋白质交互关系抽取

蛋白质交互关系(PPI)抽取是生物医学信息抽取领域的一个重要部分,具有很高的应用价值和实际意义。该文使用一种基于SVM的组合核方法进行蛋白质关系抽取,将基于特征的平面核和基于结构的卷积树核组合。一棵完整的句法解析树中包含了较多噪声,需对其修剪以提高PPI抽取效果。首先讨论不同的树的剪裁策略对实验结果的影响,分别使用完全树、最小完全树、最小树和最短路径闭包树进行实验,最短路径闭包树效果最好;然后在最短路径闭包树的基础上提出一种动态拓展树,该树取得了明显优于其他解析树的效果。最后基于组合核在AIMED上进行10倍交叉实验,精确率、召回率和F值分别达到了82.40%、51.30%和63.23%。     

A new bidirectional heuristic for the assembly line balancing problem

Assembly line balancing problem (ALBP) is one of the well-known NP-hard layout planning problems for mass production systems. Many exact solution approaches have been developed, including 0–1 integer programming model, branch and bound algorithm, dynamic programming model, etc.; however, all optimal approaches are computationally inefficient in solving large-scale problems, which makes heuristic approaches a necessity in practice. In this paper we propose a new efficient heuristic, based on a recent bidirectional approach and the famous critical path method (CPM) widely used in project management, to resolve the issue of task assignment for ALBP. An example is given for illustration, and numerical results of sample problems selected from the literature are also given to show the effectiveness of the proposed heuristic.     

Solving the Orienteering Problem with Time Windows via the Pulse Framework

The Orienteering Problem with Time Windows (OPTW) is the problem of finding a path that maximizes the profit available at the nodes in a time-constrained network. The OPTW has multiple applications in transportation, telecommunications, and scheduling. First, we extend an exact method for shortest path problems with side constraints into a general-purpose framework for hard shortest path variants. Then, using this framework, we develop a new method for the OPTW that incorporates problem-specific knowledge. Our method outperforms the state-of-the-art algorithm on instances derived from benchmark datasets from the literature achieving speedups of up to 266 times and is able to find optimal solutions to large-scale problems with up to 562 nodes in short computational times.     

一种基于链路容量和可靠性的组播树算法

组播路由算法是要找到一棵以源节点为根,包含所有组播组成员节点的组播村。在许多多媒体应用中,需要考虑两大因素：源至目的节点间的路径容量和可靠性。路径容量是该路径上链路容量的最小值,而路径可靠性是该路径上链路可靠性的乘积。我们设计了一个算法,在保证使路径可靠性不小于某个闯值的条件下计算一棵容量最大化的组播树。最后在具体实验中实现了该算法,并阐明了随着可靠性闯值的增加,容量有随之减小的趋势。