带0-1和线性约束的特殊三次规划问题的全局最优性条件

研究了一类带有不等式约束和0-1约束的特殊三次规划问题的全局最优性条件,给出了此问题的一个全局最优性充分必要条件.同时通过数值例子来说明给出的全局最优性充分必要条件是很容易验证的.

求解多约束0-1背包问题的遗传算法的改进

提出对基本遗传算法(Genetic Algorithm,GA)的改进策略,并将其应用于多约束0-1背包问题(Multi-constrained 0-1Knapsack Problems,MKP)的求解。改进策略主要有:将线性规划松弛法求得的MKP的解作为初始解,另外为了避免种群多样化的丧失,将复杂的修复操作和局部优化操作应用于每一个最近产生的解。最后,对大规模测试数据的标准集进行实验,并将该算法与先前的方法进行比较,结果表明新的遗传算法在大多数时间能够更快速地收敛到较优解。

0-1多项式规划问题的SDP松弛方法(英文)

本文提出了一类新的构造0-1多项式规划的半定规划(SDP)松弛方法.我们首先利用矩阵分解和分片线性逼近给出一种新的SDP松弛,该松弛产生的界比标准线性松弛产生的界更紧.我们还利用拉格朗日松弛和平方和(SOS)松弛方法给出了一种构造Lasserre的SDP松弛的新方法.

0—1规划的一维搜索

本文给出了一种分离线性0—1约束的可行域和非可行域的搜索方法。用该法求解变量系数均非负的0—1规划,其收敛速度不低于一般的稳枚举法。文末给出了一个具体算例,共做16次搜索,而Balas算法则需进行37次搜索。