The robust knapsack problem with queries

We consider robust knapsack problems where item weights are uncertain. We are allowed to query an item to find its exact weight,where the number of such queries is bounded by a given parameter Q. After these queries are made, we need to pack the items robustly, i.e., so that the choice of items is feasible for every remaining possible scenario of item weights.The central question that we consider is: Which items should be queried in order to gain maximum profit? We introduce the notion of query competitiveness for strict robustness to evaluate the quality of an algorithm for this problem, and obtain lower and upper bounds on this competitiveness for interval-based uncertainty. Similar to the study of online algorithms, we study the competitiveness under different frameworks, namely we analyze the worst-case query competitiveness for deterministic algorithms, the expected query competitiveness for randomized algorithms and the average case competitiveness for known distributions of the uncertain input data. We derive theoretical bounds for these different frameworks and evaluate them experimentally. We also extend this approach to Γ-restricted uncertainties introduced by Bertsimas and Sim.Furthermore, we present heuristic algorithms for the problem. In computational experiments considering both the interval-based and the Γ-restricted uncertainty, we evaluate their empirical performance. While the usage of a Γ-restricted uncertainty improves the nominal performance of a solution (as expected), we find that the query competitiveness gets worse.     

A heuristic 0–1 integer programming method

Summary In this paper, we present a novel relaxation method for the integer programming problem:Ax=b,A {–1,0,+1}^m×N,x {0,1}^N, N>m. The report includes experimental results of problems with up tom=100 equations andN=400 variables.     

求解背包问题的病毒协同进化粒子群算法

为提高粒子群算法的搜索性能,提出一种基于病毒进化理论的改进离散粒子群算法:病毒协同进化粒子群算法.在粒子群中引入生物病毒机制和宿主与病毒基于感染操作的思想,病毒采用与粒子等长的编码方式,执行反向代换、结合等操作,利用病毒的水平感染和垂直传播能力较好地维持个体的多样性和对解空间的局部搜索能力.通过解决背包问题对算法进行验证,仿真表明所提算法搜索性能优于遗传算法、模拟退火及标准粒子群等其他算法.该算法能有效求解背包问题等NP难题.     

背包公钥密码体制的数学理论研究

对背包公钥密码体制的数学理论进行了研究,给出了背包单射加密函数的一个充分必要条件,以及获得单射加密函数的方法,并给出了背包公钥密码体制中的3个数学结论。     

改进的细菌觅食优化算法求解0-1背包问题

细菌觅食优化算法作为一种新兴的智能优化算法,一般用来解决连续域的问题。为了解决离散域问题,提出了一种改进的细菌觅食优化算法。采用线性递减的思想和随机的游动长度代替固定步长和随机游动方向,改进了趋向性操作方案,并将其应用于解决0-1背包问题。将改进的细菌觅食优化算法与遗传算法、离散粒子群优化算法及基本的离散化细菌觅食优化算法分别在小规模和大规模的0-1背包问题上进行了仿真比较,表明了改进的细菌觅食优化算法能取得较好的效果,寻优能力强。     

ID-based trapdoor mercurial commitment under one-way functions assumptions

The notion of identity-based trapdoor mercurial commitment incorporates the advantages of both identity-based trapdoor commitment and trapdoor mercurial commitment. So far, the existing identity-based trapdoor mercurial commitment schemes are based on the strong Diffie-Hellman assumption or computational Diffie-Hellman assumption. One-way function existence is one of the fundamental assumptions in the cryptography. In this paper, we first propose a general construction for identity-based trapdoor mercurial commitment based on the one-way function. Meanwhile, we give a concrete instantiation based on the Boneh-Boyen signature scheme.     

随机背包公钥密码的分析与改进

针对随机背包公钥密码方案,提出一种私钥恢复攻击方法.发现Wang等人所构造的随机背包公钥方案实际上是隐含使用了一个特殊的超递增背包.通过使用普通超递增背包代替该特殊超递增背包,将超递增背包隐藏在随机选择的背包中,对原方案进行了改进,提出一种新的基于中国剩余定理的背包公钥密码方案.改进后的方案消除了原方案存在的设计缺陷,能够抵抗针对原方案提出的格规约攻击、低密度攻击以及shamir攻击.     

A note on semidefinite relaxation for 0-1 quadratic knapsack problems

We investigate in this note solution properties of semidefinite programming (SDP) relaxation for 0-1 quadratic knapsack problem (QKP). In particular, we focus on the issue of uniqueness of the optimal solution to the SDP relaxation for QKP. We first give a counterexample which shows that the optimal solution to the SDP relaxation for QKP could be non-unique. This is in contrast with the case of unconstrained 0-1 quadratic problems. A necessary and sufficient condition is then derived to ensure the uniqueness of the optimal solution to the SDP relaxation for QKP.     

基于蜂群遗传算法的0-1背包问题

针对0-1背包问题,本文提出了基于蜂群遗传算法的优化求解方案。该算法包括两个种群,一个主要用于全局搜索,另一个主要用于局部搜索;每个个体采用二进制编码;采用最优个体交叉策略;对当前解的处理措施是将还未装入背包且性价比最好的物品装进背包,直至不能装为止;不符合约束条件的解采用诱变因子指导变异处理;遗传算子包括单点交叉算子、简单变异算子、主动进化算子和抑制算子。本算法充分发挥了遗传算法的群体搜索和全局收敛的特性,快速地并行搜索,有效地克服了经典遗传算法容易陷入局部最优问题。数值实验表明,该算法在求解0-1背包问题中取得了较好的效果,同样可以应用于其它的组合优化问题。