Lower bounds and a tabu search algorithm for the minimum deficiency problem

An edge coloring of a graph G=(V,E) is a function c:E→ℕ that assigns a color c(e) to each edge e∈E such that c(e)≠c(e′) whenever e and e′ have a common endpoint. Denoting S _v (G,c) the set of colors assigned to the edges incident to a vertex v∈V, and D _v (G,c) the minimum number of integers which must be added to S _v (G,c) to form an interval, the deficiency D(G,c) of an edge coloring c is defined as the sum ∑ _v∈V D _v (G,c), and the span of c is the number of colors used in c. The problem of finding, for a given graph, an edge coloring with a minimum deficiency is NP-hard. We give new lower bounds on the minimum deficiency of an edge coloring and on the span of edge colorings with minimum deficiency. We also propose a tabu search algorithm to solve the minimum deficiency problem and report experiments on various graph instances, some of them having a known optimal deficiency.     

A successive approximation algorithm for the multiple knapsack problem

It is well-known that the multiple knapsack problem is NP-hard, and does not admit an FPTAS even for the case of two identical knapsacks. Whereas the 0-1 knapsack problem with only one knapsack has been intensively studied, and some effective exact or approximation algorithms exist. A natural approach for the multiple knapsack problem is to pack the knapsacks successively by using an effective algorithm for the 0-1 knapsack problem. This paper considers such an approximation algorithm that packs the knapsacks in the nondecreasing order of their capacities. We analyze this algorithm for 2 and 3 knapsack problems by the worst-case analysis method and give all their error bounds.     

An improved approximation algorithm for uncapacitated facility location problem with penalties

In this paper, we consider an interesting variant of the classical facility location problem called uncapacitated facility location problem with penalties (UFLWP for short) in which each client is either assigned to an opened facility or rejected by paying a penalty. The UFLWP problem has been effectively used to model the facility location problem with outliers. Three constant approximation algorithms have been obtained (Charikar et al. in Proceedings of the Symposium on Discrete Algorithms, pp. 642–651, 2001; Jain et al. in J. ACM 50(6):795–824, 2003; Xu and Xu in Inf. Process. Lett. 94(3):119–123, 2005), and the best known performance ratio is 2. The only known hardness result is a 1.463-inapproximability result inherited from the uncapacitated facility location problem (Guha and Khuller in J. Algorithms 31(1):228–248, 1999). In this paper, We present a 1.8526-approximation algorithm for the UFLWP problem. Our algorithm significantly reduces the gap between known performance ratio and the inapproximability result. Our algorithm first enhances the primal-dual method for the UFLWP problem (Charikar et al. in Proceedings of the Symposium on Discrete Algorithms, pp. 642–651, 2001) so that outliers can be recognized more efficiently, and then applies a local search heuristic (Charikar and Guha in Proceedings of the 39th IEEE Symposium on Foundations of Computer Science, pp. 378–388, 1999) to further reduce the cost for serving those non-rejected clients. Our algorithm is simple and can be easily implemented. The research of this work was supported in part by NSF through CAREER award CCF-0546509 and grant IIS-0713489. A preliminary version of this paper appeared in the Proceedings of the 11th Annual International Computing and Combinatorics Conference (COCOON’05).     

基于随机p-鲁棒优化的国家血液战略储备库选址-库存模型

以往的救灾实践对建立国家血液战略储备体系提出了迫切要求。国家血液战略储备库的建设问题亟待解决。由于血液产品特性以及应急血液保障特性的存在,使得国家血液战略储备库的选址决策具有一定的复杂性。本文将问题定位为选址-库存问题。首先,以应急条件下血液保障及时度最高为目标,构建了一个不确定环境下考虑多情景、多血型、多阶段、带提前期、有容量限制、日常随机需求、有预算约束及协同定位的国家血液战略储备库选址-库存模型。同时,为了规避应急条件下的不确定风险,进一步构建了国家血液战略储备库选址-库存问题的随机p-鲁棒优化模型。该模型为离散非线性混合整数规划模型,难以快速精确求解。故基于模型性质,设计了相应的遗传算法。最后,设计了两组算例验证模型与算法的有效性。其中,第1组算例基于我国大陆地区31个省级血液中心与省级行政区的数据,并根据不同预算值给出6个算例,得到了国家血液战略储备库的选址-库存决策方案。第2组算例为6个不同规模的模拟算例,用来测试不同规模下的算法性能。算例结果表明：遗传算法的性能更好;鲁棒解与确定性模型最优值相差不大（最大差距≤1.08%）,可降低不确定性导致的风险。实践中,可对本文所建模型稍作改进,应用于具有类似特征的易腐品（药品、粮食等）应急物资储备库选址-库存决策。     

The web proxy location problem in general tree of rings networks

The Web proxy location problem in general networks is an NP-hard problem. In this paper, we study the problem in networks showing a general tree of rings topology. We improve the results of the tree case in literature and get an exact algorithm with time complexity O(nhk), where n is the number of nodes in the tree, h is the height of the tree (the server is in the root of the tree), and k is the number of web proxies to be placed in the net. For the case of networks with a general tree of rings topology we present an exact algorithm with O(kn ²) time complexity.This research has been supported by NSF of China (No. 10371028) and the Educational Department grant of Zhejiang Province (No. 20030622).     

An immune algorithm with stochastic aging and kullback entropy for the chromatic number problem

We present a new Immune Algorithm, IMMALG, that incorporates a Stochastic Aging operator and a simple local search procedure to improve the overall performances in tackling the chromatic number problem (CNP) instances. We characterize the algorithm and set its parameters in terms of Kullback Entropy. Experiments will show that the IA we propose is very competitive with the state-of-art evolutionary algorithms.     

考虑属性关联的两阶段获胜者确定模型

研究了多属性逆向拍卖的获胜者确定问题。考虑属性之间的两两关联,以定义在2-可加模糊测度上的Choquet积分表达拍卖人的偏好,其中模糊测度的值由拍卖人提供的偏好信息推测得出。由于一般情况下与偏好信息一致的模糊测度取值并不唯一,考虑所有一致的评分函数提出了两阶段获胜者确定方法。首先采用线性规划挑选出在任意评分函数下可能获胜的报价,再通过混合整数规划确定一个与所有一致的评分函数的评价结果最为接近的报价排序,以得分最高者为稳健获胜报价。仿真实验表明,大量的报价为不可能获胜报价,说明了在第一阶段进行筛选的必要性。与现有方法的比较表明了该方法的有效性,且在拍卖轮数较大、报价数目较多时,该方法在计算效率上更有优势。     

考虑风险规避的秘书问题求解的一个启发式方法

秘书问题是一类序贯观察与选择问题,描述了动态的信息搜索与决策过程.针对现有的以寻找满意解为目标的启发式方法存在诸多局限,提出了新的启发式方法,该方法基于当前观测中侯选项在已观察侯选项中的相对排名、待观测侯选项数量以及决策者的抱负水平,决策者可以通过设定抱负水平灵活决定该启发式方法的结果导向.推导了该启发式方法的性能指标,并通过仿真的方法与已有启发式方法的性能进行了比较.结果发现,该启发式方法在最终选择的侯选项的期望排名和稳定性,以及风险解的避免上均优于已有的启发式方法.     

Defining Problems Fast and Slow: The U‐shaped Effect of Problem Definition Time on Project Duration

This study examines how time spent in problem definition affects problem solving in projects such as Six Sigma projects. Our hypotheses are tested using data collected from 1558 Six Sigma projects in a company. The results show evidence of a U‐shaped relationship between the amount of time spent in the Define phase and project duration. This finding suggests that spending too little time on problem definition potentially causes poor problem formulation, which leads to deficient problem solving and lengthens overall project time. On the other hand, too much time spent on problem definition can lead to unneeded delays in project completion due to diminishing returns on problem definition efforts. Furthermore, the optimal balance between spending too little and too much time depends on prior project experience and project complexity. Prior project experience reduced project completion time and weakened the U‐shaped effect. Conversely, complex projects took longer and appeared to show some evidence of a stronger U‐shaped effect; this suggests balancing the time spent in the Define phase was more challenging for complex projects. Our study also underscores the importance of managing project duration, as projects that were completed faster tended to be associated with higher project savings.     

An upper bound on the minimal total cost of the transportation problem with varying demands and supplies

In general cases, to find the exact upper bound on the minimal total cost of the transportation problem with varying demands and supplies is an NP-hard problem. In literature, there are only two approaches with several shortcomings to solve the problem. In this paper, the problem is formulated as a bi-level programming model, and proven to be solvable in a polynomial time if the sum of the lower bounds for all the supplies is no less than the sum of the upper bounds for all the demands; and a heuristic algorithm named TPVDS-A based on genetic algorithm is developed as an efficient and robust solution method of the model. Computational experiments on benchmark and new randomly generated instances show that the TPVDS-A algorithm outperforms the two existing approaches.