可在www.sciencedirect.com在线获取理论计算机科学电子笔记346（2019）613-624www.elsevier.com/locate/entcs列表着色问题Mauro Lucci1，2 Graciela Nasini1，3 Daniel Sever 'ın1，4迪普托deMatem'atica，FCEIA，UniversidadNacionaldeRosario，ArgentinaCONICET，Argentina摘要图中的着色问题已经被广泛地用于模拟实际应用。特别是，列表着色问题推广了著名的图着色问题，许多精确的算法已经开发出来在这项工作中，我们提出了一个分支和价格算法的加权版本的列表着色问题的基础上，由Mehrotra和技巧（1996年）开发的图着色问题。该版本考虑与每个颜色相关联的非负权重，并且需要从预定列表中为每个顶点分配颜色，以使所分配颜色的权重之和最小。计算实验表明，我们的方法的良好性能，能够舒适地解决其图形有多达70个顶点的实例这些经验还表明，列表着色问题的实例的难度似乎不仅取决于定量参数，如图的大小，其密度和颜色列表的大小，而且还取决于列表中颜色的分布关键词：列表着色，分支和价格，加权问题。1介绍图着色问题（GCP）模拟了广泛的规划问题，如布线，调度，电子带宽分配和排序。一些应用对GCP施加了额外的约束，产生了已知的变体，例如公平着色，预着色扩展，（γ，μ）着色和列表着色，参见例如[1，2]。实际上，列表着色推广了GCP，预着色扩展和（γ，μ）着色，并有几个特定的应用，如无线网络中的信道分配[3]。在许多实际情况下，颜色具有不同的权重（或成本），并且需要找到最小权重的着色而不是最小基数。特别是在[4]中，1这项工作得到了资助ANPCyT PICT-2016-0410和PID-UNR ING 538的支持。2电子邮件地址：mlucci@fceia.unr.edu.ar3电子邮件地址：nasini@fceia.unr.edu.ar4电子邮件地址：daniel@fceia.unr.edu.arhttps://doi.org/10.1016/j.entcs.2019.08.0541571-0661/© 2019作者。出版社：Elsevier B.V.这是CC BY许可下的开放获取文章（http://creativecommons.org/licenses/by/4.0/）。614M. Lucci et al. /Electronic Notes in Theoretical Computer Science 346（2019）613=Σ+在公共交通公司被建模为一个最小加权列表着色问题（MWLCP）。设G=（V，E）是一个无向简单图，C是一个色集. 图G一个染色是函数f：V→C使得对G的每条边（u，v）f（u）/=f（v）.给定G的一个着色f，j∈C的类色，记为f−1（j），是由j着色的顶点v的集合，即使得f（v）=j。显然，每个类的颜色都是一个G的稳定集，因此，任何着色都可以被认为是顶点到稳定集的划分。着色f的活动色，用A表示，是那些分配给某个顶点，即A。 {j∈C：f−1（j）/=}。 GCP包括求G的最小基数为A的染色。这个最小值被称为图G的色数，记为χ（G），已知对一般图求这个色数是NP-困难的尽管它的难度，需要获得具体的解决方案，以众多的应用程序的动机发展的几个精确算法的GCP：组合分支和边界，如DSATUR5，6]，分支和切割BC-COL[7]和分支和价格LPCOLOR[8，9，10]。在BC-COL的情况下，使用基于经典顶点颜色分配变量的非线性规划（ILP）紧凑公式（从现在开始为GCP-CF）。相反，LPCOLOR是基于集合覆盖ILP公式（GCP-SC从现在开始），其中每个变量代表一个稳定的G。由于变量的数量通常是指数的大小G，GCP-SC的线性松弛的解决方案是由列生成程序。在列表着色中，每个顶点v∈V都有一个预先分配的列表L（v）<$C，定义了可以分配给v的颜色。形式上，G的列表染色是G的染色f，其附加条件是f（v）∈L（v），对所有v∈V。注意，经典图G的列表染色使得对任意v∈V，L（v）=C.给定一个向量w∈ZC，MWLCP包括找到G的一个列表着色，使得活动颜色的权重的总和，即，j∈Awj，是最小值。AS着色可以被认为是列表着色的特殊情况，MWLCP可以被看作是GCP的加权版本的推广然而，这个加权版本可以平凡地简化为GCP，因为人们可以从C中挑选最便宜的χ（G）颜色以获得最小权重的着色显然，MWLCP是一般图的NP-困难的，因为它推广了GCP。怎么--已有的一些结果表明，MWLCP确实比GCP更难。首先，与GCP不同，GCP在任何时候都是可行的，|C| ≥χ（G），MWLCP可能是不可行的，即使|L（v）|对于所有v ≥χ（G）。给出了一个著名的例子在图1中，每个顶点的可用颜色都包含在大括号中。实际上，即使仅限于列表的大小至多为3且G是上图或上图的情况，询问G是否具有列表着色也是NP-完全的。完全二分的[11]。相比之下，GCP可以在线性时间内在上图和二部图上求解。另一个例子，这些问题在困难中是不同的，当图是M. Lucci et al. /Electronic Notes in Theoretical Computer Science 346（2019）613615我们可以假设G是连通的，并且C=v∈VL（v）。.{1，2}{1，3个字符}{2，3}{1，2}{1，3个字符}{2，3}Fig. 1. 不可行的例子由树宽参数化。对于给定的树宽t固定的图G，有一个动态规划算法可以在多项式时间内找到χ（G），而询问G是否有列表着色是W[1]-Hard[12]。制剂GCP-CP（分别GCP-SC）可以扩展到MWLCP，使得它们在应用于GCP实例时一致。在这项工作中，我们提出了这些扩展的ILP公式，分别称为MWLCP-CP和MWLCP-SC，我们开发了一个分支和价格算法来解决MWLCP通过MWLCP-SC，通过[8]提供的一些想法。然而，我们必须考虑GCP和MWLCP之间的差异所产生的一些其他问题在GCP中，每个顶点都可以用C中的任何元素着色，并且所有颜色都具有相同的权重，从而使颜色彼此无法区分。显然，这个属性是不满足MWLCP迫使我们考虑一个变量为每个稳定集和每个颜色在MWLCP-SC。尽管如此，我们设计了一个机制，以利用这些情况下，颜色之间的不可分割性是部分满足。如前所述，可行性是另一个在第2节中，我们正式介绍了ILP公式MWLCP-CP和MWLCP-SC。在第3节和第4节中，我们解释了定义我们的分支和价格算法的主要组成部分：LP松弛的求解方式，如何生成列以及如何执行节点分支。在第5节中，计算实验进行评估我们的算法的性能在不同大小和类型的随机实例最后，在第六节中，我们得出了一些2用于MWLCP的ILP制剂考虑MWLCP的一个实例，由图G=（V，E）给出，一组颜色C其中weig htswj∈Z+，对于ea chj∈C，并列出L（v）<$C，对于ea chvertexv。W.l.o.gF或eachcolorj，letVj={v∈V：j∈L（v）}，Gj是G的导出子图yVj，Ij是Gj中的孤立点集，S（Gj）是Gj中的极大稳定集Gj。第一个配方基于GCP-CF [7]。我们有一个二进制变量xvj，对于每个v∈V和j∈L（v），使得它的值为1当且仅当f（v）= j，并且二进制变量yj满足yj=1ifj是f中的活动颜色。然后，MWLCP616M. Lucci et al. /Electronic Notes in Theoretical Computer Science 346（2019）613ΣSJX∈v SJSJJJ可以用公式表示如下：（MWLCP-CF）minwjyjj∈CS.T.j∈L（v）xvj= 1<$v∈V（1）xuj+xvj≤yj<$j∈C，（u，v）∈E（Gj）（2）xvj≤yj<$j∈C，v∈Ij（3）xvj∈{0，1}<$v∈V，j∈L（v）yj∈{0，1}<$j∈C约束（1）确保每个顶点都被指定一种颜色，（2）强制不一对相邻顶点接收相同的颜色（当使用该颜色时），以及（3）当v是G j中 的孤立顶点时 ， 控 制 y j 的 激活。第二个ILP模型对应于着色的公式，作为基于GCP-SC的稳定集的顶点。这里，我们有一个二进制变量xj为每个j ∈ C和每个稳定集S ∈ S（G j）. 注意，对于任何颜色j，其颜色类是来自G的稳定集，与GCP不同，不超过一个极大稳定集可以使用覆盖。以下ILP模型自然产生我的朋友j∈CS∈S（Gj）S.T.j∈L（v）SS（Gj）∈S≥1<$v∈V（4）S∈S（Gj）S≤1<$j∈C（5）S∈{0，1}<$j∈C，S∈S（G）约束条件（4）是说，对于每个顶点v，至少选择一个包含v的稳定集，而（5）允许为每个颜色最多选择一个稳定集然而，该公式没有正确地推广GCP-SC，因为GCP的实例产生了比GCP-SC具有更多变量的模型。颜色之间的不相容性。为了克服这一缺点，我们称两个颜色j，k∈C是不可区分的，XXXM. Lucci et al. /Electronic Notes in Theoretical Computer Science 346（2019）613617如果wj=wk和Gj=Gk.L∈Ck={j∈C：j，k是不可区分的}且{Ck：k∈K}是C的一个划分，其中K<$C.换句话说，每个k∈K都是一种颜色，代表来自C的那些颜色。现在，我们可以利用这些颜色之间的对称性，|C k|稳定集G k而不是一个单一的。此外，委员会认为，618M. Lucci et al. /Electronic Notes in Theoretical Computer Science 346（2019）613XS∈v SSSSSKSS.0S\∩S.如果|G K| ≤ |Ck|由于存在验证该条件的最优解，因此可以去除这种约束。现在，MWLCP可以重新制定：（MWLCP-SC）最小工作量kk∈KS∈S（Gk）S.T.k∈KSS（Gk）∈xk≥1<$v∈V（6）S∈S（Gk）x k≤ |C k|k∈K：|G K| ≥ |C k|+1（7）xk∈{0，1}<$k∈K，S∈S（Gk）因此，对于对应于GCP的实例，我们有K={1}和C1=C。此外，如果，|C |≥ |V（G）|，约束（7）不再需要，并且我们的最后一个约束（7）不再需 要 。处方与GCP-SC相同3求解MWLCP-SC给定一个实例（G，C.，w，L），令X={（S，k）：S ∈ S（Gk），k ∈ K}.MWLCP-SC的线性松弛的变量是xk，对于（S，k）∈X，它的约束可以写成Ax≥1，Bx≥ −b和x≥0，其中，对于每个变量x，A中对应的列是S的特征向量，B中的列在对应于k∈K的行中有一个非零项−1。此外，对于每个k ∈ K，b k= |C k|. 注意，形式为xk≤1的约束是不必要的（非负权重确保至少有一个最优解验证这些条件）。对于yX∈X，l∈x（X∈）是限制于（S，k）∈X∈的变量xk的向量LP（X_∞）是MWLCP-SC在x（X_∞）上的线性松弛。我们先来给出了LP松弛问题解的完整性的一些结果，这些结果将在第四节中使用。引理3.1Letx∈e是LP（X）的最优解，且令X∈={（S，k）∈X：|≥ 2 }。|≥2}. 如果x∈ N（X∈ N）是整数，则LP（X）有一个最优整数解.是的。考虑X的分区X+=XX0。 显然，x∈（X+）是LP（X+）的最优解。由于x<$（X<$）如果是整数，则X<$X+的变量被设置为1。然后，通过在LP（X+）中用1代替这些变量的共现，我们得到了一个关于变量的线性规划LP_JX+\X<$，使得x<$（X+\X<$）是LPj的最优解. 观察到X+\X_n中变量所表示的稳定集是单态的.M. Lucci et al. /Electronic Notes in Theoretical Computer Science 346（2019）613619设AJ和BJ分别是LPJ中对应于约束（6）和（7）的A和B由于AJ的列是单点稳定集的特征向量，它们有一个正项等于1。 类似地，BJ的列最多有一个等于-1的负项，因此意味着矩阵620M. Lucci et al. /Electronic Notes in Theoretical Computer Science 346（2019）613LPJ的系数是全幺模的。因此，存在LPJ和LP（X）的整数Q注意，当每个Gj都是完备的时，s表集合了一个re单例，而X是前一个引理的陈述然后，我们得到：=0.0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000推论3.2若对任意的j∈C，Gj是完全图，则LP（X）有整数最优解.实际上，推论3.2也可以从MWLCP的简化推导出，二分图上的最小加权完美匹配问题，如下所述。M. Lucci et al. /Electronic Notes in Theoretical Computer Science 346（2019）613621˜⊂Σ∗∗SΣ考虑MWLCP的一个实例（G，C，w，L），使得Gj是一个完全图，对所有j∈C.注意，每种颜色最多只能指定给一个顶点。那么，我们可以假设，|V（G）|≤C（否则，MWLCP将不可行）。 设Z是一组虚拟元素，使得|Z|为|C |− |V（G）|.其次，考虑由V（G）∈ Z和C定义的具有顶点划分的二部图G_n，证明了对任意v∈V（G）和dj∈C，（v，j）是G_n的一个无边图，若j∈L（v），则（v，j）是G_n的无边图. （v，j）的weig ht是wj。 我们还考虑边（z，j），其中z∈Z，j∈C的权为零.显然，如果f是G的列表染色，则存在G的包含边（v，f（v））的完美匹配，对于所有v∈V（G），并且对于所有z ∈ Z和某些j（z）取自f中的非活动色，存在dedges（z，j（z））。这个的重量完美匹配与列表着色的权重一致反之，对G的任意完备集M，edges（v，j）∈M，对任意v∈V（G），定义了G的一个与M具有相同权的列表染色.此外，G有完美匹配当且仅当如果MWLCP可行。在实践中，这个问题可以解决更快地通过匈牙利算法比通过解决LP松弛。3.1列生成设X为X，x∈（X∈ ）是LP（X∈）的最优解，（π∈，γ∈）是LP（X∈）的最优对偶解，其中π和γ是对应于约束（6）和（7）分别（对于那些k ∈ K，使得|G K|≤ |C k|，我们假设γ= 0）。 注意，对于任何（S，k）∈kk。Kv∈Sπv−（wk+γk）。X，x S的降低成本 cS=我们还记得，通过添加零，从x（X）yp获得的x，即。x（X\X）=0，对于LP（X）是可行的，但不一定是最优的。为了了解这一点，我们有判断是否存在（S，k）∈X使得ck>0，或者等价地，求解以下辅助问题：（Aux）<$（S，k）∈X使得v∈Sπv<$>wk+γk<$？显然，（Aux）等价于对每个k ∈ K，求解Gk上的最大加权稳定集问题（MWSSP），其中weig htπv∈V（Gk）。尽管MWSSP是NP难的，但[9]中给出的枚举例程表明，当它被分支和价格算法调用时，它是相当快的。 此外-622M. Lucci et al. /Electronic Notes in Theoretical Computer Science 346（2019）613K/∈NPJ∈因此，并不总是需要将MWSSP求解为最优。人能阻止当集合S∈S（Gk）的权值大于阈值时，该算法可以得到最优解.不=wk+γk_（？）此外，如果我们有Gk=Gl和Tk>Tl，对于某个k =1K，则不需要为Gl运行枚举例程，因为为Gk找到的稳定集可以为Gl重用。虽然对于列生成过程来说找到一个列就足够了，但初步实验表明，同时合并许多列会减少过程的迭代次数，从而减少总时间。在我们的实现中，我们搜索（如果存在）每个k∈K的一个进入变量。观察到列生成过程需要从一个集合X开始对于这类情形，LP（X）是可行的。我们回想一下，不像GCP，如果f的n个实例MWLCP是可行的，- 完整的问题和最好的算法，发现一个列表着色，只要它存在，是O（2n）nO（1）[13]。在下面的部分中，我们提出了一个初始化过程。3.2初始化线性弛豫我们的方法包括在扩展的解决方案空间，通过创建一个虚拟的颜色每个顶点。给定MWLCP的实例（G，C，w，L），我们生成一个扩展的对于（G，CJ，wJ，LJ），其中CJ=C<${dv：v∈V（G）}，对所有的j∈C，w j j = wj ， 对 所有的 v∈V（ G）， w d v = M ， 其中M是 一个大的 数（例如，男=1+jCwj）。另外，对任意v ∈ V（G），LJ（v）=L（v）<${dv}.现在，从实例（G，CJ，wJ，LJ）获得的线性松弛是平凡的。由于xdv{v} 对于所有v∈V（G）= 1是一个可行解，它允许我们开始我们的列生成过程。 也就是说，X∈ ={（{v}，dv）：v∈V（G）}。随着优化的进行，预计将不再使用虚拟颜色。事实上，如果在与扩展实例（G，CJ，wJ，LJ）相关联的松弛的最优解中某些虚拟颜色仍然是活动的，则（G，C，w，L）是不可行的。初步实验表明，从虚拟颜色开始比可行的初始着色更好，当后者可以生成时（有一些算法可以提供列表着色，例如k-Greedy-List[14]）。我们推测，这可能是因为这种着色产生的初始列质量很差，从而使LP求解器执行更多的迭代。由于我们的列生成过程嵌入在分支和价格框架中，我们必须为B B树的每个节点解决的子问题应该对应于MWLCP的新实例。为了达到这个目的，我们需要设计一个健壮的分支规则。在下一节中，我们将提出这样一个规则，适应[15]中首次提出并在[8]中用于GCP的规则M. Lucci et al. /Electronic Notes in Theoretical Computer Science 346（2019）61362314一个健壮的分支规则[8]中给出的规则背后的思想是选择两个不相邻的顶点u和v并将解空间划分为满足f（u）=f（v）的解空间（两者共享相同的颜色）和满足f（u）f（v）的那些其他的寻找最优在后一种情况下，着色等价于在通过将边（u，v）添加到G而获得的图上求解GCP。在前一种情况下，我们必须通过将顶点u和v折叠成单个顶点（即，将u连接到每个从NG（u）中取一个顶点<$NG（v），去掉v，其中NG（x）是开邻域x在G中）。我们遵循相同的策略，但附加条件是顶点u和v必须满足L（u）<$L（v）<$。 事实上，找到最佳列表着色f的（G，C，w，L）与f（u）/=f（v）等价于求解MWLCP的实例（G1，C，w，L），其中G1=（V（G），E（G）<${u，v}），而寻找最优f其中f（u）=f（v）等价于求解（G2，C，w，L2）的MWLCP，其中G2=Gv，u连接到NG（v）的每个顶点，L2（z）=L（z），对所有z∈V（G2）u，L2（u）=L（u）<$L（v）.请注意，在前面规则的有限次应用中，我们得到所有图Gk都是完全的例子此时，根据推论3.2，它们的LP松弛的最优解是整数。此外，由于求L2（u）需要求交集，因此很可能会得到一个顶点为单例列表的子问题。由于这样的顶点被强制使用唯一可用的颜色来着色，因此可以根据以下结果对实例进行预处理引理4.1设（G，C，w，L）是MWLCP的一个实例，使得对于某个u ∈ V（G）和j∈ C，L（u）={j}. 求解（G，C，w，L）等价于求解实例（GJ，C，w，LJ）的MWLCP，其中GJ= G\{u}，LJ（z）= L（z）\{j}，对于所有z∈ N（u），并且LJ（z）=L（z），对于所有z∈V（GJ）\N（u）。证据若FJ是（GJ，C，w，LJ）的最优列表染色，则f（u）=j，f（z）=FJ（z）对任意z∈V（GJ）是（G，C，w，L）的最优列表染色相反，如果（GJ，C，w，LJ）是不可行的，则（G，C，w，L）也是不可行的。Q只需要指定一个选择顶点u和v的标准，我们将在下面讨论。4.1分支变量选择策略文[8]提出了一个简单而有效的规则。我们用我们的公式对K={1}的情形作了简单的解释（上标省略）。 假设x是LP松弛的非整数最优解作者首先搜索最大自由变量，即 一个nxS1最小化|xS1−2|，且pi cku∈S1.由于x<$S1∈/{0，1}和（6）对u成立，存在另一个S2suc h使得x<$S2>0和u∈S2. 然后，他们搜索第一个顶点v，使得v∈S1ΔS2，由于由于稳定集是互不相同的，所以存在这样的v，它不与u相邻。624M. Lucci et al. /Electronic Notes in Theoretical Computer Science 346（2019）613S1S2在我们的例子中，我们搜索最分数的 xk，满足|S1|≥ 2，我们取u∈S1。引理3.1保证了这种稳定集的存在（否则，解决方案将是一体的）。现在我们需要一对（S2，l）使得S1S2，u ∈ S2，且x ∈ l> 0. 如果这样的（S2，l）存在，我们选取v∈S2\S1. 否则，我们选择v∈ S1\{u}. 通过这种方式，我们可以断言u和v不相邻，并且满足前提条件L（u）=L（v）/=L，因为它们的列表中必须有颜色k或l5计算结果这一节专门分析所提出的分支和价格算法在随机生成的实例上的性能，其中顶点数n∈{50，60，70}和边缘概率yp∈{0. 25，0。50，0。75}。C的基数和列表中颜色的分布由两个参数c∈{0. 五，一。0，1。5}且q∈{0。25，0。50，0。75}。 前者用于设置C={1， . ，[cn]. 后者，我们称之为列表匹配概率，是对于每个v，颜色j∈C属于L（v）的概率。权重设定为1、所有颜色 随机数由均匀分布产生。实验比较了CPLEX-CF和BP-SC两种方法，前者使用CPLEX的ILP求解器（带默认参数）求解MWLCP-CF公式。后者是我们的Branch-and-Price算法，它是用C++手动实现的，仅使用CPLEX来解决LP松弛问题。为了加快子问题的生成，我们复制并对实例所在的数据结构执行最小的更改。这节省了时间，因为不需要从头开始重新计算颜色集合的分区，也不需要重新计算它们之间的子图Gk。引理4.1适用于此阶段。然后，子问题以深度优先搜索的方式解决。关于定价程序，我们遍历图Gk根据值Tk降序，以避免解决MWSSP在同一个图不止一次。 对另一方面，我们当前的实现不使用匈牙利算法用于与推论3.2相关的松弛。这一功能将在未来的版本中加入。实验通过配备有AMD Phenom II X4 3.4GHz（使用单线程）、3.6GB内存、Ubuntu 16.04操作系统、GCC 5.4.0和IBM Phenom G CPLEX 12.7作为整数和线性规划求解器的台式计算机进行。解决每个实例的时间限制为1小时结果总结见表1。在每一行中，报告了使用相同的值（n、p、c、q）组合生成的5个实例的平均值：突出显示最佳时间的CPLEX-CF和BP-SC的CPU时间（以秒为单位）的平均值，以及BP-SC探索的节点数的在平均值中仅考虑在时限内解决到最优性的实例对于5个实例中至少有一个未解决的情况，已解决的实例数在括号中报告如果没有解决任何问题，则显示符号从表中可以看出，BP-SC实现了卓越的性能，能够解决98%的最优实例（405个实例中的特别是所有M. Lucci et al. /Electronic Notes in Theoretical Computer Science 346（2019）61362588.7894.082.3632.6（4）1703.64.330.794.568.5281.7（3）14.759.326.11.21.72.64.619.132.643.034.150.471.35.08.311.8npCq= 0.25q= 0.50q= 0.75SC节点SC时间CF时间SC节点SC时间CF时间SC节点SC时间CF时间0.5470.30.32338.522.0552.91235.90.251.04755.41.279233.6660.3534.2–1.5881.34.2873.3454.8565.2–0.5460.40.61594.2400.9502.1–500.501.01.5572110.73.62.56.2238638.12.5507.8623.445372.93.5––0.5390.30.5260.527.0160.6–0.751.0220.20.4230.653.1130.8–1.5300.40.8190.764.1151.3–0.51071.40.82308.6106.0895143.7–0.251.062714.18.0957.1789.918428.6–1.52618.730.1631102.3-726177.6–0.5430.71.61324.9596.5（2）48749.2–600.501.01.52491135.53.425.934.3711214.110.9--45740868.686.1––0.5510.60.9331.31686.6（3）352.3–0.751.0430.83.1341.8-403.9–1.5320.82.9452.5-334.7–0.25700.500.750.51.01.50.51.01.50.51.01.58467266948145231506661596477223.638831671853233320015066840521154.8（3）-–––––––七十一九十五101166一百五十三1614545四十六表1随机图上的结果（每行平均5个实例50和60个顶点的实例可以在几分钟内解决。当将顶点数增加到70并考虑边概率为0.5或0.75（中到高密度）时，观察到相同的行为。相比之下，边缘概率为0.25（低密度）的实例偶尔更难解决，除非成员列表概率很高。请注意，探索的节点数量很低，指出线性松弛提供了严格的边界，节点选择策略足够好，但每个松弛的解决方案非常耗时。关于CPLEX-CF，我们注意到它在时间限制内解决了一半的实例（405个中的202个）。该公式的缺点之一是由LP松弛的值提供的弱下限。事实上，BP-SC的LP弛豫比CPLEX-CF的LP弛豫大174%（平均），并且随着实例大小在任何参数（n，p，c或q）中的增长，这种差距会加剧。在n = 70，p = 0的情况下达到峰值。75，c= 1。5，q = 0。75，其中BP-SC的LP松弛大604%。虽然CPLEX-CF在5%的情况下优于BP-SC，但这些情况通常具有低密度的图形和具有少量颜色的列表，使得MWLCP-CF在变量和约束的数量上更小。在BP-SC的情况下，图的密度越低，MWSSP在图Gk（其倾向于稀疏）上的分辨率越难。最后但并非最不重要的是，这两种方法不仅在改变顶点数量和密度时，而且在改变55.8590.0（2）230.5（3）188.514.911.03.23.34.9626M. Lucci et al. /Electronic Notes in Theoretical Computer Science 346（2019）613颜色列表的结构。在BP-SC的情况下，这种行为似乎是不可预测的。即使我们固定了顶点数、边概率和列表成员概率，性能也并不总是随着颜色数的增加而变差。6结论在这项工作中，我们提出了一个分支和价格算法来解决加权版本的列表着色问题，它有许多应用，并推广了其他几个着色问题。为了实现这一点，我们提出了一个列生成过程和一个鲁棒的分支方案，基于[8]中给出的GCP。特别是，当限制来自GCP的实例时，我们的方法就像LPCOLOR一样。但是，其他方面应该已经考虑到，如可行性和颜色之间缺乏不可分割性。就我们而言，这是第一个基于ILP的精确算法。实验结果表明，该算法具有很好的性能，能够在1小时内最优地求解70个顶点的随机生成实例。我们的结果还表明，实例的硬度似乎不仅取决于生成参数（n，p，c和q），而且还取决于列表中存在的颜色的分布。在这方面，我们认为仍需进行进一步的研究。特别地，应该研究图Gk的结构，即图的大小、密度和重叠度（它们共享的顶点数）对Branch-and-Price算法性能的影响。更好地了解棘手的问题有助于发现和改进-在我们的算法中寻找机会。在未来的工作中，我们计划评估我们的算法在其他类型的实例的性能例如，通过向颜色添加不同的权重，改变无法区分的颜色的数量，使用来自应用程序的实例（请参见例如[4]）和其他着色问题（例如，预着色扩展，（γ，μ）-着色）或通过从基准图创建实例，例如来自COLORLIB（DIMACS）的实例。引用[1] Kubale，M.，Graph Colorings，American Mathematical Society（2004）.[2] Bonomo，F.，G. Dur'an，J. 马仁科，探索复杂性bouncebetwen着色和列表着色，安。Res.169（2009），3[3] 王伟，和X. Liu，基于列表着色的开放频谱无线网络的信道分配，IEEE第62届车辆技术会议，达拉斯，德克萨斯州，美国（2005），690[4] Lucci，M.，G. Nasini和D. Sever'ın，通过Graph列表着色模型规划公交车司机的工作日，电子期刊SADIO17（2018），77[5] B r'elaz，D.， 新的方法来着色的一个G raph，COM mun。 ACM22（1979），251-256.[6] 圣塞贡多山口提出了一种新的基于DSATUR-based的顶点精确着色算法Comp.操作员Res. 39（2012），1724M. Lucci et al. /Electronic Notes in Theoretical Computer Science 346（2019）613627[7] 梅恩德斯-迪亚斯岛， 和P. Zabala，一种基于割平面的图形着色算法，Discr. Appl. Math. 156（2008），159[8] Mehrotra，A.，和M. Trick，A Column Generation Approach for Graph Coloring，INFORMS J.Comput. 8（1996），331[9] 赫尔德，S.，E. Sewell和W.图着色的安全下限。注释计算SC.6655（2011），261-273。[10] Malaguti，E.，M. Monaci和P. Toth，顶点着色问题的精确方法，Discr。Optim。8（2011），174[11] Golovach，P.，M.约翰逊，D。Paulusma和J. Song，A Survey on the Computational Complexity ofColoring Graphs with Forbidden Subgraphs，J. Graph Theory84（2017），331[12] Cygan，M.，F. 福明湖Kowalik，D.Lokshtanov，D.马克思，M。Pilipczuk，M.Pilipczuk和S.索拉布参数化算法，Springer International Publishing（2015）。[13] Bjorklund，A.，T. Husfeldt和Mikko Koivisto，Set partitioning via inclusion-exclusion，SIAM JournalComput. 39（2009），546[14] Achlioptas，D.，和M. Molloy，随机图上列表着色算法的分析，第38届计算机科学基础年会，迈阿密，佛罗里达州，美国（1997），204[15] Zykov，A.一、On some properties of linear complex，Matematicheskij Sbornik24（1949），163
我的内容管理
展开
