一类半线性卷积积分微分方程的初边值问题

本文考虑具线性粘弹性杆受粘性阻尼的横振动所引出的积分微分方程的初边值问题，在某些条件下，得到了解的存在性、唯一性、稳定性和正则性的结论。     

面向知识管理的企业业务问题求解方案管理系统研究

针对企业求解业务问题时方案制定不合理的问题, 设计了面向知识服务的业务问题求解模型框架以及求解方案管理系统的体系架构, 并介绍了该系统的功能模块、关键技术和实现方法. 系统通过对企业业务问题求解方案进行多层次的建模, 规范制定了企业求解方案的建模流程, 使求解方案的制定效率更高; 同时实现了业务执行过程的知识化. 系统通过分析和抽取企业内外的信息, 实现了企业知识资源的自生长, 从而提高了求解方案制定的准确性.     

The Capacitated Team Orienteering Problem: A Bi-level Filter-and-Fan method

This paper focuses on vehicle routing problems with profits and addresses the so-called Capacitated Team Orienteering Problem. Given a set of customers with a priori known profits and demands, the objective is to find the subset of customers, for which the collected profit is maximized, and to determine the visiting sequence and assignment to vehicle routes assuming capacity and route duration restrictions. The proposed method adopts a hierarchical bi-level search framework that takes advantage of different search landscapes. At the upper level, the solution space is explored on the basis of the collected profit, using a Filter-and-Fan method and a combination of profit oriented neighborhoods, while at the lower level the routing of customers is optimized in terms of traveling distance via a Variable Neighborhood Descent method. Computational experiments on benchmark data sets illustrate the efficiency and effectiveness of the proposed approach. Compared to existing results, new upper bounds are produced with competitive computational times.     

Towards a new framework for evaluating systemic problem structuring methods

Operational researchers and social scientists often make significant claims for the value of systemic problem structuring and other participative methods. However, when they present evidence to support these claims, it is usually based on single case studies of intervention. There have been very few attempts at evaluating across methods and across interventions undertaken by different people. This is because, in any local intervention, contextual factors, the skills of the researcher and the purposes being pursued by stakeholders affect the perceived success or failure of a method. The use of standard criteria for comparing methods is therefore made problematic by the need to consider what is unique in each intervention. So, is it possible to develop a single evaluation approach that can support both locally meaningful evaluations and longer-term comparisons between methods? This paper outlines a methodological framework for the evaluation of systemic problem structuring methods that seeks to do just this.     

Deformation Techniques for Sparse Systems

We exhibit a probabilistic symbolic algorithm for solving zero-dimensional sparse systems. Our algorithm combines a symbolic homotopy procedure, based on a flat deformation of a certain morphism of affine varieties, with the polyhedral deformation of Huber and Sturmfels. The complexity of our algorithm is cubic in the size of the combinatorial structure of the input system. This size is mainly represented by the cardinality and mixed volume of Newton polytopes of the input polynomials and an arithmetic analogue of the mixed volume associated to the deformations under consideration. Research was partially supported by the following grants: UBACyT X112 (2004–2007), UBACyT X847 (2006–2009), PIP CONICET 2461, PIP CONICET 5852/05, ANPCyT PICT 2005 17-33018, UNGS 30/3005, MTM2004-01167 (2004–2007), MTM2007-62799 and CIC 2007–2008.     

Expanding Neighborhood GRASP for the Traveling Salesman Problem

In this paper, we present the application of a modified version of the well known Greedy Randomized Adaptive Search Procedure (GRASP) to the TSP. The proposed GRASP algorithm has two phases: In the first phase the algorithm finds an initial solution of the problem and in the second phase a local search procedure is utilized for the improvement of the initial solution. The local search procedure employs two different local search strategies based on 2-opt and 3-opt methods. The algorithm was tested on numerous benchmark problems from TSPLIB. The results were very satisfactory and for the majority of the instances the results were equal to the best known solution. The algorithm is also compared to the algorithms presented and tested in the DIMACS Implementation Challenge that was organized by David Johnson.     

Geometric quadrisection in linear time, with application to VLSI placement

We consider the following problem: given a set of points in the plane, each with a weight, and capacities of the four quadrants, assign each point to one of the quadrants such that the total weight of points assigned to a quadrant does not exceed its capacity, and the total distance is minimized.

This problem is most important in placement of VLSI circuits and is likely to have other applications. It is NP-hard, but the fractional relaxation always has an optimal solution which is “almost” integral. Hence for large instances, it suffices to solve the fractional relaxation. The main result of this paper is a linear-time algorithm for this relaxation. It is based on a structure theorem describing optimal solutions by so-called “American maps” and makes sophisticated use of binary search techniques and weighted median computations.

This algorithm is a main subroutine of a VLSI placement tool that is used for the design of many of the most complex chips.     

Lehmer's problem for compact Abelian groups

We formulate Lehmer's Problem concerning the Mahler measure of polynomials for general compact abelian groups, introducing a Lehmer constant for each such group. We show that all nontrivial connected compact groups have the same Lehmer constant and conjecture the value of the Lehmer constant for finite cyclic groups. We also show that if a group has infinitely many connected components, then its Lehmer constant vanishes.

     

A Variable Neighborhood Search for the Multi Depot Vehicle Routing Problem with Time Windows

The aim of this paper is to propose an algorithm based on the philosophy of the Variable Neighborhood Search (VNS) to solve Multi Depot Vehicle Routing Problems with Time Windows. The paper has two main contributions. First, from a technical point of view, it presents the first application of a VNS for this problem and several design issues of VNS algorithms are discussed. Second, from a problem oriented point of view the computational results show that the approach is competitive with an existing Tabu Search algorithm with respect to both solution quality and computation times.     

一种基于约束的指针程序路径选择方法

动态符号执行是对程序进行安全性分析的重要技术.在动态符号执行过程中,存在着符号地址,系统调用,路径选择等问题.针对符号地址导致的别名分析问题,本文提出了一种基于约束的指针分析方法,对程序进行过程内的指向分析,并对指针分析过程引入约束条件,产生可以进行路径选择的测试用例,以提高指针分析的精度.在国内首款某型号商用编译器的开发过程中实现了该方法,实验结果表明,该方法可以准确地分析C语言测试用例,缩短用例测试的时间.