Some algebraic methods for solving multiobjective polynomial integer programs

Multiobjective discrete programming is a well-known family of optimization problems with a large spectrum of applications. The linear case has been tackled by many authors during the past few years. However, the polynomial case has not been studied in detail due to its theoretical and computational difficulties. This paper presents an algebraic approach for solving these problems. We propose a methodology based on transforming the polynomial optimization problem to the problem of solving one or more systems of polynomial equations and we use certain Gröbner bases to solve these systems. Different transformations give different methodologies that are theoretically stated and compared by some computational tests via the algorithms that they induce.     

On modified Runge-Kutta trees and methods

Modified Runge-Kutta (mRK) methods can have interesting properties as their coefficients may depend on the step length. By a simple perturbation of very few coefficients we may produce various function-fitted methods and avoid the overload of evaluating all the coefficients in every step. It is known that, for Runge-Kutta methods, each order condition corresponds to a rooted tree. When we expand this theory to the case of mRK methods, some of the rooted trees produce additional trees, called mRK rooted trees, and so additional conditions of order. In this work we present the relative theory including a theorem for the generating function of these additional mRK trees and explain the procedure to determine the extra algebraic equations of condition generated for a major subcategory of these methods. Moreover, efficient symbolic codes are provided for the enumeration of the trees and the generation of the additional order conditions. Finally, phase-lag and phase-fitted properties are analyzed for this case and specific phase-fitted pairs of orders 8(6) and 6(5) are presented and tested.     

QoS multicast routing using a quantum-behaved particle swarm optimization algorithm

QoS multicast routing in networks is a very important research issue in networks and distributed systems. It is also a challenging and hard problem for high-performance networks of the next generation. Due to its NP-completeness, many heuristic methods have been employed to solve the problem. This paper proposes the modified quantum-behaved particle swarm optimization (QPSO) method for QoS multicast routing. In the proposed method, QoS multicast routing is converted into an integer programming problem with QoS constraints and is solved by the QPSO algorithm combined with loop deletion operation. The QPSO-based routing method, along with the routing algorithms based on particle swarm optimization (PSO) and genetic algorithm (GA), is tested on randomly generated network topologies for the purpose of performance evaluation. The simulation results show the efficiency of the proposed method on QoS the routing problem and its superiority to the methods based on PSO and GA.     

Algorithms to Separate $\{0,\frac{1}{2}\}$ -Chvátal-Gomory Cuts

Chvátal-Gomory cuts are among the most well-known classes of cutting planes for general integer linear programs (ILPs). In case the constraint multipliers are either 0 or , such cuts are known as -cuts. It has been proven by Caprara and Fischetti (Math. Program. 74:221–235, 1996) that separation of -cuts is -hard. In this paper, we study ways to separate -cuts effectively in practice. We propose a range of preprocessing rules to reduce the size of the separation problem. The core of the preprocessing builds a Gaussian elimination-like procedure. To separate the most violated -cut, we formulate the (reduced) problem as integer linear program. Some simple heuristic separation routines complete the algorithmic framework. Computational experiments on benchmark instances show that the combination of preprocessing with exact and/or heuristic separation is a very vital idea to generate strong generic cutting planes for integer linear programs and to reduce the overall computation times of state-of-the-art ILP-solvers.     

The manpower allocation problem with time windows and job-teaming constraints: A branch-and-price approach

In this paper, we consider the manpower allocation problem with time windows, job-teaming constraints and a limited number of teams (m-MAPTWTC). Given a set of teams and a set of tasks, the problem is to assign to each team a sequential order of tasks to maximize the total number of assigned tasks. Both teams and tasks may be restricted by time windows outside which operation is not possible. Some tasks require cooperation between teams, and all teams cooperating must initiate execution simultaneously. We present an integer programming model for the problem, which is decomposed using Dantzig–Wolfe decomposition. The problem is solved by column generation in a branch-and-price framework. Simultaneous execution of tasks is enforced by the branching scheme. To test the efficiency of the proposed algorithm, 12 realistic test instances are introduced. The algorithm is able to find the optimal solution in 11 of the test instances. The main contribution of this article is the addition of synchronization between teams in an exact optimization context.     

基于半监督典型相关分析的多视图维数约简

为了有效地在半监督多视图情景下进行维数约简,提出了使用非负低秩图进行标签传播的半监督典型相关分析方法。非负低秩图捕获的全局线性近邻可以利用直接邻居和间接可达邻居的信息维持全局簇结构,同时,低秩的性质可以保持图的压缩表示。当无标签样本通过标签传播算法获得估计的标签信息后,在每个视图上构建软标签矩阵和概率类内散度矩阵。然后,通过最大化不同视图同类样本间相关性的同时最小化每个视图低维特征空间类内变化来提升特征鉴别能力。实验表明所提方法比已有相关方法能够取得更好的识别性能且更鲁棒。     

Development of a Cloud Trust Label: A Delphi Approach

The purpose of this research is to identify the potential information components of an online, real-time trust label, which is proposed as a communication mechanism to encourage trust in cloud service providers and cloud computing products. An online Delphi process was used with 28 cloud computing experts (including vendors, software providers, and legal and business representatives). The proposed label contains 81 information components, covering the cloud service provider (e.g. physical location, legal jurisdiction), the cloud service itself (e.g. data location, security, backup, certification), and a historical service-level summary (e.g. uptime data, support response times). The potential benefits of such a label to encourage trustworthiness perceptions and trust behaviors in the cloud computing environment are explored. Limitations of the study are highlighted, and further research studies are suggested to test the concept of the label and to refine the components of the label itself.     

产品评论中领域情感词典的构建

领域情感词典是情感分析最重要的基础。由于产品评论的数量巨大、领域众多,如何自动构建领域情感词典已经成为近年来的一个研究热点。该文提出了一个两阶段的领域情感词典构建算法。第一阶段,利用情感词间的点互信息和上下文约束,使用基于约束的标签传播算法构造基本情感词典;第二阶段,根据情感冲突的频率来识别领域相关情感词,并根据其上下文约束以及修饰的特征完善领域情感词典。实验结果表明,该方法在实际产品评论数据集上取得了较好的效果。
     

基于模块度优化的标签传播社区发现算法

标签传播算法（LPA）是一种快速高效的社区发现算法,算法无需社区数量等先验信息,但存在大量随机性,稳定性较差. 为了提高标签传播算法的稳定性,提出了一种改进的标签传播算法（LPAMP）. 该算法分为两个阶段,第一阶段以模块度贪婪为依据,进行节点粗聚类;第二阶段在粗聚类的基础上,进行节点标签传播. 实验结果表明,所提算法降低了标签传播算法的随机性,增强了稳定性,并且提高了准确率.