文摘
线性规划是一种重要的方法,用于表示类的组合优化问题。单纯形算法的指数时间算法求解线性规划问题的复杂性。幸运的是,该算法解决现实问题的多项式时间复杂度。特别是,一个新的整数线性规划模型(ILPM)提出了半序集。罗伯特:帝尔沃斯历史学的分解定理是由ILPM制定并证明其正确性使用强劲对偶线性规划的典范。最后,运行在ILPM 15基准半序集寻找他们的宽度。计算实验表明该模型的有效性。
1。介绍
线性规划是一个非常丰富的解决问题的模型用于表示类的优化问题。优化问题被定义为问题的解决方案表示最大的值(如最大利润)或最小值(如最低成本)。有各种类型的优化问题,如约束优化问题和无拘无束的优化问题。另一方面,有许多类型根据变量的优化问题的性质,如线性规划、整数线性规划和非线性规划。有各种各样的算法来解决线性规划问题,最著名的单纯形算法和内点算法。单纯形算法是最好的十个数学算法的二十世纪1]。常见的数值例子,克利和薄荷味2]证明了单纯形算法并不是一个多项式时间算法。幸运的是,该算法解决现实问题的多项式时间复杂性。
铸件优化问题转化为一个线性程序版本是一门艺术。这种艺术的工具完成知识的表示问题表示为一个线性规划的优化。第二个工具是完整的知识一般形式的线性规划(目标function-constraints-the右边的约束(常量)-non-negative-etc)。第三这些工具的实践制定一套优化问题转化为一个线性程序版本。对于图标签问题,巴德尔et al。3- - - - - -5]介绍了新的整数线性规划模型(ILPMs)找到收音机数的上界,电台平均数和广播均方数量对于一个给定的图,分别。拟议中的ILPMs表现优于其他算法根据运行时间。对于给定图的度量维度,沙特朗等(6)制定的优化问题,确定给定的指标维度图(G)。旅行商问题,有不同的数学模型(7- - - - - -9旅行推销员问题)。
高效的任务调度问题是在计算机科学和工程的许多领域无处不在。我们常常收集的任务来完成,有些工作可以并行完成,和其他必须做在一个预定义的序列。一般来说,我们可以制定这些问题通过构造一个偏序集的对象(代表任务)一些元素是“可比性”(必须完成的工作在预定义的序列),而其他人则是“无与伦比”(可以并行完成的工作)。如果我们的目标是设计一个高效的任务调度算法,我们可能会发现最大的子集感兴趣的任务可以并行完成(最大反链的问题)。或者我们可能感兴趣的相关问题之间的分配的所有任务最少数量的子组(例如,并行处理),这样所有工作小组必须完成在一个预定义的序列(最低链覆盖问题)。
更多细节的历史分解半序集的偏序集,读者可以参考(10- - - - - -16]。另一方面,关于如何制定的更多细节问题数学模型,读者被称为(17- - - - - -19]。最后,对于更多细节都知道最优PMU放置读者被称为(20.- - - - - -22]。
在本文中,一个新的整数线性规划模型(ILPM)提出了偏序集。罗伯特:帝尔沃斯历史学的分解定理是由ILPM制定并证明其正确性使用强劲对偶线性规划的典范。最后,运行在ILPM 15基准半序集寻找他们的宽度。计算实验表明该模型的有效性。
其余本文的组织结构如下:基本定义和符号介绍部分2。节3提出了:帝尔沃斯历史学定理和数学公式。节4,实验结果的分析提出了ILPM十五基准提供了偏序集。节5,结论。
2。预赛
呈现:帝尔沃斯历史学定理之前,我们需要有一个在集合中元素之间的相似性的概念。这个概念形式化,二元关系我们定义一些属性来表示一个部分有序的集合(偏序集)。然后我们说明在一个偏序集的元素子集可以有链或反链的属性。
2.1。二元关系
一组元素可以有关系传递性或反对称性等属性。
定义1。一个二元关系, ,在一组是传递当且仅当(一个b和bc)意味着c为所有a, b, cϵ
定义2。一个二元关系
在一组是反对称当且仅当(一个≠b和一个
b)意味着b一个对所有a、bϵ
。
我们使用二进制与这些特定属性来表示一个偏序关系的元素,一些对元素是可比的
在上下文的任务调度问题,这意味着工作。之前必须完成。
定义3。一个半序集,或偏序集,是一组元素
,二元关系
,拥有的财产传递和反对称所有元素在吗。
注意,两个元素和也可以无与伦比的,也就是说,当我们有
和
。在这种情况下,任务和可能是并行完成。
我们也在偏序集最大和最小元素定义:
一个元素一个子集最大
如果不小于,其他元素年代,即
对所有
。同样,一个元素是最小的年代如果不是即大于任何其他元素。
对所有
。
定义4。元素的一个子集 形成了一个反链当且仅当 对所有我≠j。这是所有元素是成对无可比拟的。
定义5。元素的一个子集
Ƥ形成一个链当且仅当他们满足
一些元素的顺序C。这是所有元素C两两比较。
例如,在一个任务调度问题,如果工作形成一个反链的一个子集。然后,所有这些工作可以并行完成。如果工作形成一个链的一个子集,那么这些工作必须完成的序列所决定
。此外,它是有用的描述一个偏序集的覆盖通过链链的集合
这样Ƥ的每一个元素都包含在这些链的结合,也就是说,
。这是所有任务分配相关的并行处理器
所以,工作分配给任何处理器在一个预定义的序列完成。
3所示。:帝尔沃斯历史学定理
手里拿着这些定义,我们现在可以制定:帝尔沃斯历史学的定理10)最大反链和最小的尺寸链覆盖物在一个偏序集。
定理1。(:帝尔沃斯历史学定理)。最大的大小反链在任何一个偏序集的大小等于最低的报道通过链。
我们可以构建一个证明:帝尔沃斯历史学定理使用鸽子洞原理和线性规划的对偶性。如果我们让:
一个= max {
:
反链的Ƥ}(规模最大的反链
),和B=敏
(最小数量的链需要掩护
),然后一个方法来证明:帝尔沃斯历史学定理是指
和
。
为了证明
,我们使用鸽子洞原理。
引理1。任何在偏序集的大小最多等于所需要的最小数量的链盖吗 ,即。 。
证明。如上述,让B最小数量的链 需要覆盖 。为了矛盾,假设一个反链 在Ƥ大小n>B。由鸽子洞原理,至少有两个不同的元素 , 必须是相同的链的成员,这样,通过定义5,我们有或 。然而,通过定义4,这意味着和不是在同一个链,一个矛盾。因此,没有反链可以有大小大于B,它遵循反链的最大大小也没有更大的B。
3.1。铸造作为线性规划
为了证明 一个更为困难。我们可以开始试图把找到的最大大小的客观反链作为线性规划的一个偏序集。
3.1.1。原始的形式
非负权重分配 分别为每个元素 ϵP。每一个链 将有一个关联的约束不等式的元素 组成。考虑下面的规范形式的线性规划:
3.1.2。对偶形式
此外,我们可以转换(1)的对偶形式,变量代表链 ,和每个元素 都有一个关联的约束不等式在包含它的链集合(注意对称)。分配非负权重。
我们首先显示,如果原始的(1)和(2)整数解,那么客观z在(1)最大反链的大小 ,和我们的目标在(2)给的最小覆盖的大小由链。
命题1。如果所有重量 ,然后解决原始的(1)给出了最大反链 。
证明。在所有的情况下非负整数,我们希望显示的目的(1),
,等于
,在哪里是最大的反链吗
。
观察到约束(1),对于所有连锁店
把下面的要求强加给变量如果我们假设他们都非负整数:
权利要求1。对于所有连锁店 ,最多与元素相关联的权重之一= 1。所有其他的重量必须是0。
权利要求1的证明。为了矛盾,假设不止一个元素C链有一个积极的重量。我们将会有因为所有的非负整数,从而违反约束的线性规划。
由此可见,
对所有我。现在考虑每作为一个指示器变量是否元素出现在一个反链
,即让
如果和
否则。
由于最多一个指示符变量在任何链是正的,解决方案(1)满足要求,没有两个元素选择的最大反链来自同一链。
此外,根据指示符变量解释,最大化的目的
选择对应的最大数量的元素包含的反链
,所以我们有
,根据需要。这证明了命题1一个整数解(1)最大反链的大小
。
现在,我们证明了类似的对偶形式的命题。
命题2。如果所有重量然后解决双(2)提供的最小覆盖的大小P由链。
证明。命题的推理是类似于1。
限制,(2),对所有元素
,以下要求强加给变量如果我们假设他们都非负整数:
要求2。对所有 ,至少一个权重与链包含的集合是正的。
索赔证据2。它紧跟着的约束。如果对某些元素
,所有的重量与链包含有关是积极的,那么
,从而违反约束的线性规划。
此外,由于线性规划试图最小化与所有为整数,我们必须有
每当选择积极的。因此,有对所有j再次,我们可以考虑作为一个指标变量是否链在一个最小覆盖
。
请再次注意,为每一个元素
,至少有一个指示符变量与一个链包含相关联= 1,所以解决方案(2)满足要求所有元素出现在最低链覆盖。
此外,根据指示符变量解释,最小化的目标
对应于选择最小数量的链包括覆盖的
,所以我们有
,根据需要。这证明了命题2一个整数解(2)给出的最小覆盖由链。
现在,我们需要证明原始和双线性程序确实有整数解。
引理2。对于任何分布链的一个偏序集,(1)有一个最优解,所有变量取整数值。
证明。证明良序原则和矛盾的一个最佳的解决方案(1)数量最少的noninteger变量(重量)。让N元素的集合对应于这些noninteger权重。其中一些元素将在N,最大和其他人将最小(召回定义部分2)。我们首先需要确认。
要求3。没有元素N最小和最大。
索赔证据3。为了矛盾,假设一个元素最小和最大。然后,无与伦比的所有其他元素在吗N(取消定义部分2)。它遵循相关联的重量只有一个主题限制吗
在(1),即将指定值最大化目标。这与假设不是一个整数,从而证明这种说法。
因为没有元素N都是最小和最大,因此,每个链
正好有一个最大的元素,不同的最小元素。
假设我们添加一个小的价值
每个最大元素N,减去e从每一个最小的N。因为所有元素N我们确保nonintegers结果赋值的变量选择是可行的
足够小,这样
还满意吗
根据约束(1)。
如果我们一直重复这个过程,那么至少有一个变量对应于最大/最小的元素N将达到一个边界值0或1。这与假设Nnoninteger最少的变量在一个可行的解决方案。因此,所有变量分配在一个最佳的解决方案(1)必须是整数,所以引理2适用于原始的(1)。接下来,我们需要显示双(2)也有整数解。
引理3。对于任何分布链的一个偏序集,(2)有一个最优解,所有变量取整数值。
证明。首先,我们运用强劲对偶线性规划的结果(见[19]详情)。说,原始的和线性规划的对偶形式有相同的最优值。我们使用感应,如果证明kϵ
的最优值是在偏序集LP2
,然后一个覆盖了k链,所有的变量在(2)整数值。
归纳假设:任何偏序集有一个整数最优(2)k的客观价值,最优解的有限合伙人与严格的子集都是整数。
基本情况。考虑一个帖子在所有元素形成一个最优的客观价值
。的约束(2),该最优解单变量(对应链包含所有元素
)的值为1,另一个y值0。由此可见,每个LP与子集相关联的最优解也将整数权重。因此,归纳假设适用于
。
现在,假设一个最佳的解决方案(2在偏序集有一个变量赋值
这不是一个整数(注意,这个LP的最优值必须是一个整数
)。我们可以删除链中的所有元素相关的变量获得一个新的偏序集
。
让的目标函数值对于这个新的偏序集
。我们观察到最多是因为所有元素组成的链的重量
被移除,这样
。自
是一个严格的子集
,
由归纳假设是一个整数,所以呢
。此外,归纳假说告诉我们一个覆盖了链,所有权重分配链是整数。接下去我们的盖
通过k链如果我们只是分配重量
来
,实现预期的目标所需的值
。这就完成了归纳论点和引理的证明3。
在引理2和3结合命题1和2提供所需的结果,半序集
:解决(1)给出了规模最大的反链解决(2)给出的最小覆盖的大小通过链再次,运用强大的二元性的结果19在线性规划,我们得出这样的结论:原始的(1)和双(2)有相同的最优值。因此,(1)解决方案的规模最大的反链一个偏序集,(2)解决方案覆盖一个偏序集的最小的尺寸链是相等的,证明定理1(:帝尔沃斯历史学定理)。
3.2。一个Polynomial-Size线性规划
在本节中,我们引入了命题3基于提出的整数线性规划模型。
命题3。一个转让指标{0,1}的值 产生一个反链当且仅当 为所有的边缘 。
证明。首先,我们表明,任何反链满足约束条件。一个反链不能包含任何可比性的两个元素(定义4)。注意,任何两个类似的元素连接的边缘G。因此,我们最多可以选择从每条边一个顶点
,也就是说,最多的一个
,= 1,它遵循
为所有的边缘
。
相反,我们表明,任何转让指标变量满足约束产生一个有效的反链。
如果
为所有的边缘
,然后一个指示符变量
,是积极的,因为
。因此,最多一个顶点(元素
)选择在每边的反链。因为所有成对类似的元素在我们的建设由边缘相连吗E(G),因此,没有两个元素选择的反链将可比,令人满意的定义4。这证明了命题3.6。
3.2.1之上。制定问题的数学模型
对于任何一个偏序集与元素集 ,我们可以构建一个 类似的关联矩阵一个,在入口 如果元素 具有可比性, 否则。现在,与每个元素相关联 一个指标变量 对应于使用或不使用该元素的反链 。
现在,我们可以制定分解偏序集的问题如下: 在哪里 是 生成矩阵的矩阵一个(基于命题3),这样米的矩阵的数量吗一个, 和 (所有元素向量b等于1)。
例1。我们展示如何制定分解问题的部分有序的集合(如图1)作为一个整数线性规划模型。
的
类似的关联矩阵一个相应的P。
的
矩阵
从生成矩阵一个:
矩阵中的每一行
基于命题3.7代表了一种不平等。
最后,完整的整数线性规划模型如下:
我们可以使用一个可用的软件包(MATLAB、Python和行话)等为解决上述数学模型返回等于3的解决方案。
4所示。计算实验
在本节中,我们评估了ILPM十五基准偏序集。这些偏序集的特点是(各种宽度等一些特点 ,各种尺寸(n),不同的高度h(P)图2包含15基准偏序集的宽度和跳数。
使用环境是一个64位的Windows 8.1操作系统与核心(TM) i5 460 @2.53 GHz CPU米,4.00 GB的内存,MATLAB v7.01软件包。
从表1和图3,很明显,结果所提出的数学模型(ILPM)配合的标准结果所有15基准偏序集。
从表也明显1和图4的执行时间ILPM随着偏序集的宽度增加而增加。也就是说,ILPM的运行时间成正比的宽度。幸运的是,单纯形算法用于解决ILPM的行为是一个多项式时间解决实际应用中,无论是指数时间证明(2]。出于这个原因,我们已经尽力创建一个偏序集的形式提供的例子克利和明蒂在1972年,他们证明了单纯形算法指数时间,但我们没有做。
因为克利所呈现的例子,有薄荷味的依赖(右边常数,约束矩阵的系数和目标函数的系数),很少做这些问题作为现实问题的存在。我们从这得出了模型将在多项式时间内执行。众所周知,单纯形算法的复杂性O(n2)实际应用程序的平均情况n是一个偏序集的元素的个数。
5。结论
一个新的整数线性规划模型(ILPM)已经提出了偏序集。罗伯特:帝尔沃斯历史学的分解定理是由ILPM制定和证明其正确性使用强劲对偶线性规划的典范。最后,运行在ILPM 15基准半序集寻找他们的宽度。计算实验表明该模型的有效性。另一方面,CPU时间已经计算了十五基准半序集。从计算实验,得出的结论是,随着宽度的增加CPU时间增加。在未来的工作中,将评估拟议中的ILPM使用特殊的偏序集等间隔偏序集,晶格,皇冠偏序集,k塔偏序集。ILPM将应用于jump-critical命令集(23]。
数据可用性
使用的数据来支持本研究的发现可以从相应的作者。
的利益冲突
作者宣称没有利益冲突。
确认
作者感谢Runpeng刘,他建议让这个手稿更好。