EURO Journal on Computational Optimization 9（2021）100016艾尔莎湖兰德和她1979年对旅行推销员问题的研究：个人回忆和历史评论帕纳焦蒂斯A. 米利奥蒂斯雅典经济与商业大学ABsTRA cT这篇简短的说明提供了一些历史性的评论之际，2021年欧洲金牌授予教授艾尔莎H。土地非常个人化的介绍Ailsa Land对数学规划的贡献是公认的，并获得了2021年欧洲金牌奖，这是运筹学的最高荣誉之一。而艾尔莎带的学生，在她的指导下，在数学规划方面获得的优秀技能，也是有目共睹的。但她的学生真正欠艾尔莎的是，当他们 在她的指导下，他们完成了博士学位，成为了更好的人。艾尔莎掌握了和谐地结合似乎是矛盾的品质的艺术。• 要求很高，但同时表现出同情和理解。• 采用一种非常温和的方式来纠正即使是最基本的错误，而不会伤害学生。• 有一个非常简单的行为，结合一个非常清晰，深刻和原始的思维方式。这种非常不寻常的人类品质的组合使了不起的人。很久以前，Ailsa就已经获得了生活所建立的最高奖项：她所有的朋友，同事和学生对她的爱，尊重和钦佩，无论是她的学术成就还是她的态度生活中现在，在她去世后，我有一种强烈的感觉，艾尔莎将继续陪伴我们，在她自己独特的，在亲切友好的方式，在我们一生的旅程。早在1974年，当我完成博士研究时，Ailsa建议我准备两篇文章。由于她在研究和文章的写作方面都给予了很大的帮助，我请她与我合著她说：“不，这是你的作品，你将独自出版。你应该把它提交给数学规划。”让我用卡瓦菲的《帖莫皮莱》中的一段话来结束这一节“Honor to those who in the life they leaddefine and guard a在他们所做的但也要表现出怜悯和同情;他们富有时慷慨仍然尽可能地帮助他们;总是说实话，而不是恨那些撒谎的人。对Land 1979论文的一些评论Ailsa Land未发表的论文“100个城市旅行推销员问题的解决方案”于1979年10月完成。为什么这篇论文没有发表仍然是一个谜，因为它包括了一些重要的创新特征。首先，一个启发式算法来寻找第一个可行的解决方案，用于加速算法。第二，使用收缩（压缩）和标记城市的方法，以便有效地识别违反的subtour约束。此外，一种方法，用于检测一些违反2-匹配的约束之前诉诸Gomory削减。第三，也是最重要的，该算法使用了一种技术，通过该技术，LP变量的一个小核心是活跃的。通过扫描剩余的变量（边缘）并检测那些违反最优性条件的变量，定期更新该核心。在所有最近的研究中，这种技术的变体被采用的切割平面法的大问题。本文详细讨论，并在Applegate、Bi X by、Chvátal和Cook（Applegate等人，2006），以及其前身（Applegate et al.， 2003年）。除了这个更详细的说明，其他研究人员也已经意识到这项工作，因为有大约20个参考文献（引用它作为LSE的技术报告），大多数都很不具体;一个主题，原文DOI：10.1016/j.ejco.2021.100017https://doi.org/10.1016/j.ejco.2021.100016接收日期：2021年9月1日;接受日期：2021年10月18日2192-4406/© 2021作者。由Elsevier Ltd代表欧洲运筹学协会（EURO）出版。这是一篇基于CC BY-NC-ND许可证的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）可在ScienceDirect上获得目录列表欧洲计算优化期刊主页：www.elsevier.com/locate/ejcoP.A. Miliotis欧洲计算优化杂志9（2021）10001630年以上引文的主动选择是（Crowder和Padberg，1980，Fekete等人，2017，Fleischmann，1985，Fleischmann，1988，Khodamoradi和Krishnamurti，2016）。以下是对该文件的一些详细评论首先，对违反组合约束（2-匹配和梳状不等式）的搜索这导致了早期引入的Gomory切割，虽然采取了适当的切割选择，并通过使用已知的边界来加强切割的过程，但切割很快变得很弱，导致收敛缓慢这种情况是由行列式的大值表示的在1978年4月的一封信中，艾尔莎写道：其次，Ailsa对是否有可能在一组受限变量的基础上构造一个有效的分支定界算法在一封信的1976年1月14日，她写道：或者反过来说，当你要扩展变量集时，你必须将它们应用到树的每一个尾部。至少，这是我目前看到的方式”。这可能就是为什么虽然她已经开发了一个完整的0-1 BB代码的精确算术，她没有继续设计和测试一个集成的分支和切割系统。三是必须看到，随机性问题呈现出范围广的困难。例如，随机成本TSP问题要容易比随机的欧几里得问题更难解决。但是，即使在随机欧几里得问题的集合中，困难也有很大的不同。因此，该算法在100个城市问题上略微失败的事实并不表明它不能解决一些更大的问题。事实是 在那个时候，缺乏一个大型问题的TSP库，使得更直接地比较全自动的替代方法变得困难。引用Applegate，David L.，罗伯特·E·比克斯，Chvátal，Vašek，Cook，WilliamJ.，2003.实现了求解大型TSP问题的Dantzig-Fulkerson-Johnson算法。数学。Ser. B 97，91Applegate ， David L. ， 罗 伯 特 ·E· 比 克 斯 ， Chvátal， Vašek ， Cook ， WilliamJ. ，2006/2011. 旅行商问题：一个计算研究。 普林斯顿大学出版社，普林斯顿。克劳德，哈伦，帕德伯格，曼弗雷德W.，1980.大规模对称旅行商问题的最优解。管理。Sci. 26（5），439Fekete，Sándor P.， 哈斯，安德烈亚斯，黑默，迈克尔，霍曼，迈克尔，作者：Kostit- syna ， Irina ， Krupke ， Dominik ， Maurer ， Florian ， Mitchell ， JosephS.B. ，Schmidt，Arne，Schmidt，Christiane，Troegel，Julian，2017.最小周长的非简单多边形的计算. J. 计算几何学8（1），340Fleischmann，Bernhard，1985. 道路网上旅行商问题的一个割平面方法EUR. J. 操作员Res. 21（3），307Fleischmann，Bernhard，1988.对称旅行商问题的一类新的割平面。数学课程。40，225-246.Khodamoradi，Kamyar，Krishnamurti，Ramesh，2016.奖品收集旅行推销员问题-快速启 发 式 分 离 。 第 五 届 运 筹 学 与 企 业 系 统 国 际 会 议 论 文 集 （ ICORES 2016 ）Scitepress，Setúbal，pp. 380-3872
我的内容管理
展开
