最大影响着色问题的整数规划方法

我→I∈可在www.sciencedirect.com在线获取理论计算机科学电子笔记346（2019）199-208www.elsevier.com/locate/entcs最大影响着色多面体的面生成方法莫妮卡·布拉加a，1 Javier Marencoa，2a科学研究所国立萨米恩托将军大学阿根廷布宜诺斯艾利斯摘要给定同一顶点集上的两个图G=（V，EG）和H=（V，EH），并给定一组颜色C，G的C，表示为 （c），是边的个数ij使得c（i）= c（j）。在这种情况下，最大影响着色问题要求G的适当着色c使影响最大化（c）H.在分配教室的背景下，课程，在那里它是可取的-但不是强制性的-从同一门课程的讲座分配到同一个教室。我们感兴趣的是整数规划的方法来解决这个问题。在这项工作中，我们提出了两个程序，从现有的不平等，基于扩展单个颜色的颜色集和扩展G的边缘集团，分别构造有效的不等式。如果原始不等式定义了一个方面，并且满足了附加的技术假设，那么得到的不等式也定义了一个方面。我们提出了一个通用的分离算法的基础上，这些程序，并报告计算实验表明，这种方法是有效的。保留字：着色，整数规划，刻面生成程序。1介绍在课程安排中经常出现的问题是确定哪些教室被分配给每门课程的每个讲座，以这种方式，重叠的讲座接收不同的教室[4]，其中每个讲座的开始和结束时间这种情况通常由一个不规则图G=（V，EG）和一个教室集合C来建模，不规则图G的顶点表示讲座，其边连接不能接收同一教室的讲座对，因为相应的图G通常被称为与讲座相关的冲突图这个问题对应于经典的图的顶点着色问题，因为任何C-着色1电子邮件：mbraga@campus.ungs.edu.ar2电子邮件：jmarenco@campus.ungs.edu.arhttps://doi.org/10.1016/j.entcs.2019.08.0181571-0661/© 2019作者。出版社：Elsevier B.V.这是CC BY许可下的开放获取文章（http://creativecommons.org/licenses/by/4.0/）。200M. Braga，J.Marenco/理论计算机科学电子笔记346（2019）199c（即， 一个赋值c：V→C使得c（i）c（j）当ij∈EG）对应时，要求将教室分配给讲座。注意，这个问题是可行的，当且仅当|C| ≥χ（G），其中色数χ（G）表示G的任意可行染色的最小颜色数.在实际环境中，一个通常的要求是将同一门课程的所有讲座分配到同一个教室。然而，这一要求并不严格，如果没有足够的教室，就可能违反这一要求。 为了考虑这一要求，在[1]中提出了以下组合优化问题。除了G之外，我们还有第二个图H =（V，E H）定义在相同的顶点集上，使得ij∈E H当且仅当i和j是同一门课程的讲义。 我们假设EGEH=。 如果c是G的一个着色，我们定 义 c对H的影响为eI（c）=|{ij∈EH：c（i）=c（j）}|，也就是，从H开始，端点接收相同颜色的边的数量。 给定两个图G =（V，E G）和H =（V，E H），其中E G∈ E H= λ和一个颜色集C，最大影响着色问题（MICP）在于找到G的一个C-着色，使H的影响最大化。 MICP是NP难的[5]，即使限制G是一个区间图，H是不相交的团的并[1]。在课程编排的背景下，许多现实生活中的要求和规则出现，并施加特定的约束，以获得实际的解决方案。经典顶点着色问题的几种公式和技术应用于广泛的出版物中（参见，例如，[2、3、6、12]）。此外，这些应用中的一些已经让位于调度软件，如[7，8]中所示。在[9，10]中，开发了一种基于约束分支的方法，其目的是减少问题的大小，同时试图保留最佳解，并将其应用于实际情况。在[11]中，SAT求解器的性能与标准的整数规划技术进行了比较。由于整数规划技术对于经典的顶点着色问题以及类似的调度和排产问题已经证明是相当成功的，在[1]中，我们提出用这种技术来解决MICP问题我们提出了一个自然的整数规划公式的MICP和识别几个家庭的小平面诱导的不平等，原来是成功地提高per-perception的分支和切割过程。许多这些家庭的有效不等式是基于类似的想法，因此，相应的证明facetness诉诸类似的论点。此外，在与每个家庭有关这些观察结果表明，存在一般性的结果来解释所识别的不等式的facetness属性，并为它们设计一个统一的分离框架在这项工作中，我们探讨这些问题，提出了两个有效性和facetness保存程序，从现有的不平等，构建有效的不平等，扩大他们的支持过程中。我们还介绍了一个通用的分离算法，这些程序的基础上，从一组小的支持不等式，并寻求应用这些程序，以获得尽可能大的支持削减。我们目前的计算实验表明，这种方法可能是有竞争力的应用程序的个人M. Braga，J.Marenco/理论计算机科学电子笔记346（2019）199201ΣΣ每个有效不等式族的分离算法。本文的组织结构如下。第2节介绍了整数规划公式的MICP。第三节给出了构造有效不等式的两个步骤。最后，第4节报告了我们的计算实验，第5节包括结论和对未来工作的想法2整数规划公式[1]中介绍的MICP的以下整数规划公式是基于顶点着色的标准模型对于i∈V和c∈C，如果顶点i被赋予颜色c，则我们定义二元赋值变量xic为xic= 1，否则xic=0。对于每个ij∈EH，如果顶点i和j被赋予不同的颜色，则我们定义二元影响变量yij为yij=<对于ij∈EH，ij，我们定义yji=yij作为符号上的方便。在这种情况下，MICP可表述如下。Maxij∈EH，ij伊日（一）（二）（三）（四）（五）（六）S.T.xic=1<$i∈Vc∈Cxic+xjc≤1<$ij∈EG，<$c∈Cyij≤1 +xic−xjc<$ij∈EH ， i χ（G）+1。为此，我们首先应用过程2以便用团K替换边jk，从而得到(11)xic+ y它≤1+xtc。t∈Kt∈K接下来，我们将过程1应用于（11），以便用集合D替换颜色c颜色。 将所得不等式与模型约束（1）相结合，我们得到了C分块不等式（9），它对P（G [i，p]，H（i，p），C <$D）是有效的，且是分面诱导的，如果|C|+的|D|> χ（G）+p +1。4计算实验过程1和过程2提供了从具有小支持的不等式开始构造具有潜在大支持的有效不等式的工具，并且在满足正确假设时也保持了面性。这提出了一个简单的启发式方法，用于尝试在切割平面环境中找到违反的有效不等式：从违反或“几乎违反”的小不等式开始，然后从违反或“几乎违反”的小不等式开始，然后从违反或“几乎违反”的小不等式开始。t∈V\Kd∈Cuv∈EH\{il，jl}206M. Braga，J.Marenco/理论计算机科学电子笔记346（2019）199尝试使用上一节中介绍的方法来扩大不等式的支持范围。 如果结果不等式被违反，那么它可以被添加为切割。在本节中，我们将探讨基于这些思想的切割生成计算过程的设计。分离过程中有一个池的通用有效的不等式P（G，H，C），我们建议调用模板。在这种情况下，模板是具有小支撑的非常简单的不等式，用作搜索切割的起点。在我们的实现中，我们采用以下模板池(i) 模型约束yij≤1+xic−xjc，对于ij∈EH和c∈C，(ii) 边不等式xic+xjc≤1，对ij∈EG和c∈C，(iii) 证明了点团不等式yij+yik≤1，其中i，j，k∈V，使得jk∈EG，ij，ik∈EH，(iv) 半三角不等式yij≤2+（xjc−xic）+（xid−xjd）−（xkc−xkd），i，j，k∈V使得ik，jk∈EG且ij∈EH，且对于c，d∈C，c d，(v) 半菱形不等式yij+2yik≤ 3+（xkc+xjc−xic）+（xid−xkd）+（xke−xie）−（xld+xle）对于i，j，k，l∈V使得jk，jl，kl∈EG且ij，ik∈EH，对c，d，e∈D，c/=d，c e，d/=e.给定一个分数解（x，y）∈P（G，H，C），分离过程首先采用回溯算法，以检测这些模板的违规和为此，将模板定义中存在的顶点和颜色与满足模板假设的所有可能的顶点和颜色进行匹配，并且识别所有违反和“几乎违反”的不等式。由于模板涉及小的支持，这样的bracktracking程序是不是计算昂贵。一个不等式πx+μy≤π0几乎被（x<$，y<$）违背，如果π0−ε≤πx<$+μy<$≤π0，对于某个小ε。 我们已经使用ε= 0。25在我们的实验中然后，对由此发现的每个有效不等式进行过程1和过程2。为了扩大所得到的不等式的支持范围，我们将这些方法应用到广义上。这两个过程的理论公式为问题的修改实例生成有效不等式，即过程1中具有颜色集（C\{c}）D的实例和过程2中的实例（G[i，p]，H（i，p），CD）。然而，在我们的实现中，我们保持实例固定，并使用原始实例的正确构造的子实例执行过程，如下所示。当应用这两个过程时，我们将C作为不等式支持中的颜色集合，并将D作为剩余的颜色集合。此外，当应用程序2时，我们将由不等式的支持引起的G的子图作为输入图，并且不是将边扩大为团，而是搜索包括现有边的团（在整个图中）。这允许快速实现，而不需要修改图形和变量集。由此产生的过程可能会产生来自[1]中提出的有效不等式族的削减（尽管不能保证削减来自[1]中提出的有效不等式族）。M. Braga，J.Marenco/理论计算机科学电子笔记346（2019）199207Cplex 12.5Cplex + cuts[1]这项工作例如|V||EG||EH||C|时间（秒）节点时间（秒）节点时间（秒）节点2010.01.I2351894124211.4011.4511.4712010.01.II26725932992216.214212.06111.4312010.02.I2561884118184.151161.9611.8512010.02.II2792914164262.6392.0912.1212011.01.I26520921371633.822282.5912.1912011.01.II2552295218202.3632.1212.1112012.01.I1821381113187.45512.1111.9012012.01.II2352220189233.7882.7512.5512012.02.I2531974162204.58282.3112.2312012.02.II2542368186221.5211.6111.5412014.02.I172120126620* 0.06%156244.0213.2312014.02.II238229449820** 0.36%210392.6816199.5993表1Cplex作为黑盒求解程序的最优时间和枚举树中的节点（标有“Cplex 12.5”), for the branch and cut presented in 对于标有“*"的实例，Cplex达到了1GB的内存限制。标记为“**"的实例每个这样的家庭最终都会产生）。与此相反，在[1]中提出的分支和切割过程诉诸于一个定制的分离过程，为每个家庭的有效的不等式。我们在相同的实现中比较了两种方法，以评估本节中提出的单个过程的计算效率表1显示了来自真实设置的一组实例的运行时间。在Cplex 12.5环境中执行实施，并且在具有Intel Core 2 Duo CPU的计算机上执行实验，其中两个T8100核心以2GHz运行，并且具有2GB RAM存储器。 我们保持所有Cplex参数均为默认值。该表显示了当采用[1]中考虑的分离程序时所实现的改进，并且还显示了本工作中提出的单一程序的性能相对于这些结果是相当有竞争力的。由于时间限制或内存限制，[1]中采用的分支和切割过程表2比较了每种情况下产生的切口数量。有趣的是，这项工作中提出的程序发现了更少数量的切割，同时获得了类似的性能。这是由于[1]中半菱形不等式的分离过程产生了许多不等式。对该过程进行更好的调整可以生成来自该族的较少数量的切割，从而使得切割数量的差异不那么重要。然而，目前尚不清楚是否可以达到这样一个更好的调整，而不诉诸于本工作中提出的技术208M. Braga，J.Marenco/理论计算机科学电子笔记346（2019）199削减例如|V||EG||EH||C|Cplex 12.5Cplex + cuts[1]这项工作2010.01.I2351894124210002010.01.II26725932992222602072010.02.I25618841181858426492010.02.II2792914164260365252011.01.I26520921371605254172011.01.II2552295218200244042012.01.I182138111318295472162012.01.II23522201892332453172012.02.I253197416220474736122012.02.II2542368186220002014.02.I17212012662013526304552014.02.II238229449820277247029181表2通过Cplex（标记为“Cplex 12.5”的列）发现的切口数量对于每个有效不等式族（标有“Cplex + cuts [ 1 ]“的列5结论从理论的角度来看，提供一个统一的框架来解释许多族的分面诱导不等式是很有趣的。在[1]中提供的facetness证明包含了类似的想法，这些想法被重复了很多次，并且在不同的证明中几乎没有变化，因此在这项工作中提出的facet-preserving程序允许对这些结果进行更优雅的证明从实际的角度来看，我们的计算实验表明，至少对于本工作中考虑的实例，没有必要对每个有效不等式族采取特定的分离过程，并且基于本工作中提出的思想的单个切割生成过程允许获得类似的这在实现分支和切割过程时很有趣，因为只需要实现一个分离过程，并且在这样的过程中考虑的模板作为未来的工作，我们计划将此实验扩展到更多的MICP实例。在这项工作中提出的刻面生成程序和分离算法可以应用到经典的顶点着色公式的标准制定。在这种情况下，我们必须忽略程序中的y变量.探索这些思想是否可以进一步细化为经典的顶点着色问题，以获得更精确的过程和更有效的（统一的）分离启发式，这将是有趣的。这也将是有趣的，考虑类似的小面保留程序的其他问题，因为这些想法可能有助于提供更简单的解释现有的小面和更简单的实现切割平面为基础的程序。引用[1] 布拉加，M.，D.德勒多恩河Linfati和J. Marenco，最大影响着色多面体，Intl. Trans. in Op. Res. 24（2017），303 https://doi.org/10.1111/itor.12265.M. Braga，J.Marenco/理论计算机科学电子笔记346（2019）199209[2] Bur ke，E.， J. Mar ePasticek，A. Parks，和H. Rud ov'a，Abranch-and-cutprocedurefortheUdinecourseallocabling problem，Annals of Operations Research 194（2012），71-87.[3] Daskalaki，S.，T. Birbas和E. Housos，An integer programming formulation for a case study inuniversity schoolabling，European Journal of Operational Research153（2004），117[4] De Werra，D.，An introduction to discovering，European Journal of Operational Research19-2（1985），151-162.[5] Garey，M.，和D.约翰逊，W. H. 弗里曼1979年[6] La ch，G.， 和M. 卢伯克，课程设置：新的解决方案，乌迪内本enchmark实例，运筹学年鉴，卷。194，pp.255[7] 米兰达，J.，eClasSkeduler：A course scheduling system for the Executive Education Unit at theUniversidad de Chile，Interfaces40-3（2010），196[8]Mooney，E.，R. Rardin和W.Parmenter，大规模教室调度，IIEE交易28-5（1996），369[9] Phillips，A.，D. Ryan和M. Ehrgott，使用整数规划解决课堂分配问题，2013年NZSA+ORSNZ联合会议论文集，2013年。[10] Phillips，A.，H. Waterer，M. Ehrgott和D. Ryan，《大规模实际课堂作业问题的编程方法》，计算机运筹学53（2015），42[11] Wasfy，A.，和F.Aloul，使用高级ILP技术解决大学课程调度问题，第四届IEEE GCC会议论文集，2007年。[12] Waterer，H.，A zero-one integer programming model for room assignment at the University ofAuckland，Proceedings of the 1995 ORSNZ Conference，1995.