考虑后悔规避与匹配意愿的直觉模糊双边匹配方法

针对直觉模糊偏好信息的双边匹配问题,提出一种考虑匹配主体后悔规避心理行为和匹配意愿的双边匹配方法。首先,将双边主体的直觉模糊偏好信息转化为效用值;然后,依据后悔理论的思想,通过一方主体将另一方主体进行两两比较计算每个主体的后悔值和欣喜值,进而计算每个主体的总体后悔欣喜值,构建匹配满意度计算规则,建立双边匹配多目标优化模型,通过分析现有匹配意愿系数确定方法的不足,给出一种新的匹配意愿系数确定方法,在此基础上,考虑双边主体的匹配意愿,采用线性加权法将多目标优化模型转化为单目标规划模型进行求解,获得双边匹配结果;最后,通过一个算例验证了提出方法的可行性和有效性。     

Efficient Algorithms for Variants of Weighted Matching and Assignment Problems

Obtaining a matching in a graph satisfying a certain objective is an important class of graph problems. Matching algorithms have received attention for several decades. However, while there are efficient algorithms to obtain a maximum weight matching, not much is known about the maximum weight maximum cardinality, and maximum cardinality maximum weight matching problems for general graphs. Our contribution in this work is to show that for bounded weight input graphs one can obtain an algorithm for both maximum weight maximum cardinality (for real weights), and maximum cardinality maximum weight matching (for integer weights) by modifying the input and running the existing maximum weight matching algorithm. Also, given the current state of the art in maximum weight matching algorithms, we show that, for bounded weight input graphs, both maximum weight maximum cardinality, and maximum cardinality maximum weight matching have algorithms of similar complexities to that of maximum weight matching. Subsequently, we also obtain approximation algorithms for maximum weight maximum cardinality, and maximum cardinality maximum weight matching.      

同城货运众包平台的车货匹配模式对比研究

针对目前同城货运车货匹配平台采用抢单模式造成客户等待时间较长、客户满意度不高的问题,提出将派单模式应用于同城货运车货匹配过程,构建以客户平均等待时长最短为目标的动态车货匹配模型。根据抢单模式实际情况设计了就近随机配对算法,针对派单模式设计了滚动时域完美匹配算法,运用模拟仿真研究方法,对比研究了两种算法的有效性和适用性,发现订单饱和度大时宜采用派单模式,且滚动时域越短客户平均等待时长越短。研究结果可为同城货运车货匹配平台的订单分配提供决策支持,提高客户满意度。     

Routing models and solution procedures for regional less-than-truckload operations

Less-Than-Truckload (LTL) carriers are required on a daily basis to solve Intra-Group Line-Haul (IGLH) problems. IGLH problems require the determination of routes to service required pickups and deliveries (i.e., 28-foot trailers) at End-Of-Line (EOL) terminals. The objective is to minimize total costs, given that tractors are able to simultaneously transport two trailers and that all pickups and deliveries must be accomplished. In this paper, an approximate IGLH solution approach is presented. Given pickup and delivery requirements together with relevant distance data, a matching network is constructed in which nodes correspond to sets of pickups and deliveries and links to routes. A minimum weight non-bipartite matching algorithm is solved over this network and the result is an IGLH solution. This solution is improved by again applying a minimum weight matching algorithm, this time to a matching network in which nodes correspond to routes and links to improved routes. Finally, the routes are sequenced so as to achieve balance at each EOL terminal (i.e., empty trailers must be delivered or picked up as necessary to ensure that each EOL terminal has the same number of pickups and deliveries) and to minimize the inventory of empty trailers. The new IGLH solution procedure is tested on randomly generated data and on data provided by a large LTL carrier. Computational tests show that near-optimal solutions are generated rapidly.     

Max-min matching problems with multiple assignments

In job assignment and matching problems, we may sometimes need to assign several jobs to one processor or several processors to one job with some limit on the number of permissible assignments. Some examples include the assignment of courses to faculty, consultants to projects, etc. In terms of objectives, we may wish to maximize profits or minimize costs, or maximize the minimal value (max-min criterion) of an attribute such as the performance rating of a processor in the matching, or combine the two goals into one composite objective function entailing time-cost tradeoffs. The regular bipartite matching algorithms cannot solve the matching problem, when upper and lower bounds are imposed on the number of assignments. In this paper, we present a method, referred to as the node-splitting method, that transforms the given problem into an assignment problem solvable by the Hungarian method.     

The computational complexity of bilevel assignment problems

In bilevel optimization problems there are two decision makers, the leader and the follower, who act in a hierarchy. Each decision maker has his own objective function, but there are common constraints. This paper deals with bilevel assignment problems where each decision maker controls a subset of edges and each edge has a leader’s and a follower’s weight. The edges selected by the leader and by the follower need to form a perfect matching. The task is to determine which edges the leader should choose such that his objective value which depends on the follower’s optimal reaction is maximized. We consider sum- and bottleneck objective functions for the leader and follower. Moreover, if not all optimal reactions of the follower lead to the same leader’s objective value, then the follower either chooses an optimal reaction which is best (optimistic rule) or worst (pessimistic rule) for the leader. We show that all the variants arising if the leader’s and follower’s objective functions are sum or bottleneck functions are NP-hard if the pessimistic rule is applied. In case of the optimistic rule the problem is shown to be NP-hard if at least one of the decision makers has a sum objective function.     

Competitive equilibrium and singleton cores in generalized matching problems

We study competitive equilibria in generalized matching problems. We show that, if there is a competitive matching, then it is unique and the core is a singleton consisting of the competitive matching. That is, a singleton core is necessary for the existence of competitive equilibria. We also show that a competitive matching exists if and only if the matching produced by the top trading cycles algorithm is feasible, in which case it is the unique competitive matching. Hence, we can use the top trading cycles algorithm to test whether a competitive equilibrium exists and to construct a competitive equilibrium if one exists. Lastly, in the context of bilateral matching problems, we compare the condition for the existence of competitive matchings with existing sufficient conditions for the existence or uniqueness of stable matchings and show that it is weaker than most existing conditions for uniqueness.     

Optimal asset allocation for a general portfolio of life insurance policies

Asset liability matching remains an important topic in life insurance research. The objective of this paper is to find an optimal asset allocation for a general portfolio of life insurance policies. Using a multi-asset model to investigate the optimal asset allocation of life insurance reserves, this study obtains formulae for the first two moments of the accumulated asset value. These formulae enable the analysis of portfolio problems and a first approximation of optimal investment strategies. This research provides a new perspective for solving both single-period and multiperiod asset allocation problems in application to life insurance policies. The authors obtain an efficient frontier in the case of single-period method; for the multiperiod method, the optimal asset allocation strategies can differ considerably for different portfolio structures.     

基于语言偏好信息的稳定双边匹配决策方法

针对语言偏好信息下的双边匹配问题,提出一种双边匹配决策方法。首先,将双边主体给出的语言偏好信息转化为三角模糊数;然后,基于去模糊化处理方法将三角模糊数转化为匹配满意度,在此基础上,考虑稳定匹配约束条件,以最大化每方主体的匹配满意度为目标,建立双边匹配多目标优化模型,求解模型,获得双边匹配结果;最后,通过一个算例验证了提出方法的可行性和有效性。     

Random paths to pairwise stability in many-to-many matching problems: a study on market equilibration

This paper considers a decentralized process in many-to-many matching problems. We show that if agents on one side of the market have substitutable preferences and those on the other side have responsive preferences, then, from an arbitrary matching, there exists a finite path of matchings such that each matching on the path is formed by satisfying a blocking individual or a blocking pair for the previous matching, and the final matching is pairwise-stable. This implies that an associated stochastic process converges to a pairwise-stable matching in finite time with probability one, if each blocking individual or pair is satisfied with a positive probability at each period along the process.     

基于优势的双边匹配决策方法

传统的双边匹配方法根据主体双方给出的偏好序信息排序, 忽略匹配双方个体间存在的差异, 匹配结果不能很好的满足主体需求, 稳定性较差, 造成资源的错配甚至浪费。本文以人为出发点, 基于对匹配主体特征属性的优势结构识别, 提出新的序值依据, 将定性的不确定匹配标准依重视程度量化, 从而实现对人的多维度测量, 最大化个体差异, 以实现“按需匹配”的高稳定性、高满意度匹配结果。构建基于主体客观评价的优势属性量表; 引入个体综合情况的计算公式; 依托隶属度加权法把多目标优化转变成单目标优化; 运用Hungarain方法获得满意度最高且稳定匹配的指派方案; 最后通过算例证明本方法的科学性和可行性。     

Speeding up IP-based algorithms for constrained quadratic 0–1 optimization

In many practical applications, the task is to optimize a non-linear objective function over the vertices of a well-studied polytope as, e.g., the matching polytope or the travelling salesman polytope (TSP). Prominent examples are the quadratic assignment problem and the quadratic knapsack problem; further applications occur in various areas such as production planning or automatic graph drawing. In order to apply branch-and-cut methods for the exact solution of such problems, the objective function has to be linearized. However, the standard linearization usually leads to very weak relaxations. On the other hand, problem-specific polyhedral studies are often time-consuming. Our goal is the design of general separation routines that can replace detailed polyhedral studies of the resulting polytope and that can be used as a black box. As unconstrained binary quadratic optimization is equivalent to the maximum-cut problem, knowledge about cut polytopes can be used in our setting. Other separation routines are inspired by the local cuts that have been developed by Applegate, Bixby, Chvátal and Cook for faster solution of large-scale traveling salesman instances. Finally, we apply quadratic reformulations of the linear constraints as proposed by Helmberg, Rendl and Weismantel for the quadratic knapsack problem. By extensive experiments, we show that a suitable combination of these methods leads to a drastic speedup in the solution of constrained quadratic 0–1 problems. We also discuss possible generalizations of these methods to arbitrary non-linear objective functions.     

Solving (large scale) matching problems combinatorially

In this paper we describe computational results for a modification of the shortest augmenting path approach for solving large scale matching problems. Using a new assignment start procedure and the two-phase strategy, where first the problem is solved on a sparse subgraph and then reoptimization is used, matching problems on complete graphs with 1000 nodes are solved in about 10–15 seconds on an IBM 4361.This work was partially supported by Sonderforschungsbereich 303, University of Bonn, and a special grant from the Deutsche Forschungsgemeinschaft.     

一类四阶非线性奇摄动方程的边值问题

利用匹配渐近展开法,讨论了一类四阶非线性方程的具有两个边界层的奇摄动边值问题．引进伸长变量,根据边界条件与匹配原则,在一定的可解性条件下,给出了外部解和左右边界层附近的内层解,得到了该问题的二阶渐近解,并举例说明了这类非线性问题渐近解的存在性．     

Improved processor bounds for combinatorial problems in RNC

Our main result improves the known processor bound by a factor ofn ⁴ (maintaining the expected parallel running time,O(log³ n)) for the following important problem:find a perfect matching in a general or in a bipartite graph with n vertices. A solution to that problem is used in parallel algorithms for several combinatorial problems, in particular for the problems of finding i) a (perfect) matching of maximum weight, ii) a maximum cardinality matching, iii) a matching of maximum vertex weight, iv) a maximums-t flow in a digraph with unit edge capacities. Consequently the known algorithms for those problems are substantially improved.The results of this paper have been presented at the 26-th Annual IEEE Symp. FOCS, Portland, Oregon (October 1985).Partially supported by NSF Grants MCS 8303139 and DCR 8511713.Supporeted by NSF Grants MCS 8203232 and DCR 8507573.     

Combinatorial algorithms for matchings,even factors and square-free 2-factors

Even factors and square-free 2-factors are restricted matching problems for which it seems to be difficult to generalize Edmonds’ matching algorithm directly. Here, we present a slight modification of Edmonds’ algorithm, which adapts to these restricted matching problems. Thus, we construct algorithms for these problems which do not use alternating forests. The author is a member of the Egerváry Research Group (EGRES). Research is supported by OTKA grants T 037547 and TS 049788, by European MCRTN Adonet, Contract Grant No. 504438 and by the Egerváry Research Group of the Hungarian Academy of Sciences.     

Test driving three 1995 genetic algorithms: New test functions and geometric matching

Genetic algorithms have attracted a good deal of interest in the heuristic search community. Yet there are several different types of genetic algorithms with varying performance and search characteristics. In this article we look at three genetic algorithms: an elitist simple genetic algorithm, the CHC algorithm and Genitor. One problem in comparing algorithms is that most test problems in the genetic algorithm literature can be solved using simple local search methods. In this article, the three algorithms are compared using new test problems that are not readily solved using simple local search methods. We then compare a local search method to genetic algorithms for geometric matching and examine a hybrid algorithm that combines local and genetic search. The geometric matching problem matches a model (e.g., a line drawing) to a subset of lines contained in a field of line fragments. Local search is currently the best known method for solving general geometric matching problems.     

偶匹配可扩性的极图问题(英文)

设G是含有完美匹配的简单图.称图G是偶匹配可扩的(BM-可扩的),如果G的每一个导出子图是偶图的匹配M都可以扩充为一个完美匹配.极图问题是图论的核心问题之一.本文将刻画极大偶匹配不可扩图,偶图图类和完全多部图图类中的极大偶匹配可扩图.     

基于三角直觉模糊数信息的双边匹配决策

本文研究了基于三角直觉模糊数信息的双边匹配问题。给出了三角直觉模糊数和双边匹配的相关理论;以实现每个主体三角直觉模糊满意度最高为目标,考虑到一对一双边匹配约束,构建了多目标双边匹配模型;运用线性加权法和三角模糊数重心法,将多目标双边匹配模型转化为单目标双边匹配模型;进而通过求解该模型获得“最佳”双边匹配方案。风险投资者和风险投资企业的匹配算例证明了所提双边匹配决策的可行性和实用性。     

On the Hamming distance in combinatorial optimization problems on hypergraph matchings

In this note we consider the properties of the Hamming distance in combinatorial optimization problems on hypergraph matchings, also known as multidimensional assignment problems. It is shown that the Hamming distance between feasible solutions of hypergraph matching problems can be computed as an optimal value of linear assignment problem. For random hypergraph matching problems, an upper bound on the expected Hamming distance to the optimal solution is derived, and an exact expression is obtained in the special case of multidimensional assignment problems with 2 elements in each dimension.