多目标混合整数线性优化的Web应用程序

软件X 19（2022）101109原始软件出版物IDOL：一个混合整数线性多目标优化的Web应用程序Kaliszewskia，b，Olga Karelkinaa，ba波兰科学院系统研究所，ul。Newelska 6，01-447华沙，波兰b华沙信息技术学院，ul。Newelska 6，01-447华沙，波兰ar t i cl e i nf o文章历史记录：2021年12月15日收到收到修订版，2022年5月11日接受，2022年保留字：多目标优化混合整数线性优化Chebyshev标量化Web应用程序a b st ra ct实际的决策往往会导致复杂的多目标优化问题，只能通过高级软件来解决。目前，该方法只适用于单目标优化问题，而对多目标优化问题的研究较少.因此，多目标优化最常用的方法是简化（标量化）到其单目标优化等价物。为此，将目标聚合为目标的加权（参数化）总和。然而，这种形式的标量化并不能保证每个帕累托最优解都能得到。我们提出了一个免费的基于Web的应用程序来自动标量化多目标混合整数优化问题的特定形式的标量化，这一过程可能是繁琐的大规模的实例。这种形式标量化的方法保证了每一个Pareto最优解都是可导出的。©2022作者（S）。由爱思唯尔公司出版这是CC BY-NC-ND下的开放获取文章许可证（http://creativecommons.org/licenses/by-nc-nd/4.0/）。代码元数据当前代码版本V1.1用于此代码版本的代码/存储库的永久链接https://github.com/ElsevierSoftwareX/SOFTX-D-21-00242Code Ocean compute capsule法律代码许可证MIT许可证使用git的代码版本控制系统使用的软件代码语言、工具和服务Python 3.8.10、Django 3.1、Django Channels 3.0、PostgreSQL 12、Redis 3.5、Celery 5.1、Python-MIP、Cbc solver、HTML、JavaScript编译要求，操作环境依赖Ubuntu 20.04 LTS或Windows 10，Python 3.8如果可用，链接到开发人员文档/手册https://github.com/rhombicosi/IDOL/blob/master/README.md支持电子邮件问题olga. ibspan.waw.pl软件元数据当前软件版本V1.1此版本可执行文件的永久链接https://github.com/rhombicosi/IDOL/releases/tag/V1.1法律软件许可证MIT许可证计算平台/操作系统Ubuntu 20.04 LTS，Windows 10安装要求依赖Python 3.8，Django 3.1，Django Channels 3.0，PostgreSQL 12，Redis 3.5，芹菜5.1如果可用，请链接到用户手册-如果正式出版，请在参考列表中引用该出版物https://github.com/rhombicosi/IDOL/blob/master/docs/IDOL%20V1.0%20User%20Guide.pdf支持电子邮件问题olga. ibspan.waw.pl*通讯作者。电子邮件地址：olga. ibspan.waw.pl（Olga Karelkina）.https://doi.org/10.1016/j.softx.2022.1011091. 动机和意义1.1. 背景优化，即在一个域上找到（目标）函数的极值（最大或最小），是直观的。一些--至少对新手来说，不那么直观的是多目标的2352-7110/©2022作者。由爱思唯尔公司出版。这是一篇开放获取的文章，使用CC BY-NC-ND许可证（http://creativecommons.org/licenses/by-nc-nd/4.0/）。可在ScienceDirect上获得目录列表SoftwareX期刊主页：www.elsevier.com/locate/softxKaliszewski和Olga Karelkina软件X 19（2022）1011092--=<$≥< $==+=∈=-x∈ X0l优化，即同时找到几个函数的极值。除平凡情况外，当所有函数在同一元素处达到极值时，使各个函数的值极值化的元素是不同的。这就产生了域的一组元素，其中没有函数可以在不恶化至少一个其他函数的值的情况下获得更好的值。在这个意义上，在这些元件处的函数值相对于所考虑的所有函数是最佳的;据说这些价值构成了帕累托意义上的均衡。这个集合，推广了最优化问题的解的概念，被称为有效集合，它的元素被称为帕累托最优解。当一个多目标优化问题模拟一个技术、经济或社会决策困境时，最终的决策自然是在帕累托最优解中寻找的。实际的决策往往导致复杂的多目标优化问题，只能通过先进的软件来解决。目前，先进的软件多用于单目标优化，多目标优化的软件较少因此，多目标优化最常用的方法是通过目标函数集合的形式将多目标优化问题简化（标化）为单目标优化问题，并应用相应的软件。每个帕累托最优解都可以被导出（参见第三节的例子）。对于通过切比雪夫函数聚合目标函数的（加权）切比雪夫标量化存在这样的保证（参见下面的公式（2））。切比雪夫标量化的一般性是有代价的，即为了得到它，与加权和标量化相比，需要一些额外的计算工作。也就是说，必须通过在可行集上分别优化每个目标函数来计算特定的参考元素。此外，为了通过MIP求解器来处理切比雪夫标量化，必须将其线性化，代价是引入一个额外的变量，k个附加约束，其中k是目标函数的数量。网络应用程序IDOL（交互式演示多目标优化pLatform）提供了这项任务的帮助。它的第一个安装是由系统研究所（华沙，波兰），并可在：http://213.135.34.49/。1.2. 多目标优化问题多目标优化问题的一般公式如下：max f1（x）···一些领先的优化软件接受多个目标和标度各自的问题。作为一项规则，要将问题标量化，将目标聚合为加权max fk（x）S.T.x∈X0，（一个）(i.e.参数化的）目标的总和。由此产生的标量化问题可以像任何其他优化问题一样解决然而，一般来说，这种形式的标量化并不能保证每个帕累托最优解都能得到。这可能会导致忽略建模问题的一些有价值和重要的选项。受多目标优化作为支持决策工具在广泛的技术，经济和社会风险的高潜力的激励，我们提出了一个免费的基于Web的应用程序，通过特定形式的标量化（切比雪夫标量化）自动标量化多目标混合整数优化问题，该过程对于大规模实例可能是繁琐的。这种形式的标量化保证了每个帕累托最优解都是可导出的。本质上，该应用程序采用多目标混合整数问题的数 据 文 件 ， 根 据 加 权 和 标 量 化 的 要 求 进 行 准 备 ， 并 使 用Chebyshev标量化生成文件切比雪夫标量化的概念是围绕一个特定的参考元素构建的为了得到这样的单元，必须预先解决此过程由应用程序在内部执行此Web应用程序的主要动机是优化软件提供商当前的趋势，即在免费许可的基础上向学术界提供他们的产品（通常称为求解器这个机会为研究人员创造了巨大的潜力，可以解决越来越复杂的问题，或者通过解决以前超出计算处理能力的问题来深化业务分析例如，NEOS服务器[1]是一个免费的基于互联网的服务，用于解决优化问题。它提供了访问60多个国家的最先进的求解器在十几个优化categories。用于混合整数（MIP）二次和线性问题的Guidelines求解器[2]，声称是同类中最快的求解器，在学术许可下免费提供本地安装。与单目标优化相比，专业求解器的列表很长，多目标优化的报价是有限的。一些混合整数规划求解器接受多个目标，这些目标被混合成目标的加权和（加权和标量化），然后像任何其他优化问题一样解决所得到的标量化问题然而，一般来说，这种形式的标量化并不能保证其中X0是（可行）解的集合。为了表示的一致性，假设所有目标函数都是最大化的（这可以通过将要最小化的函数乘以1来实现）。所寻求的对象是帕累托最优解。解x是帕累托最优的（或：有效的），如果对任何解x，fl（x）fl（x），l1，. . . ，k，蕴含f（x）f（x）。这是一个很好的结果（cf。[3例如，在一个实施例中，[3]，p.103，[4]，pp. 50-59，pp. 36minmax[λl （ y<$l−fl （ x ） ） +ρek （ y<$−f （ x ） ） ] ，（ 2）其中（一组权重）λl>0，l1，. . .，k，ek（1，1，. . .，1），y∈lmax xX0fl（x）ε，ε>0，l1，. . . ，k，ρ是一个“足够小”的正数。这里的目标函数是聚集的-由切比雪夫函数“最大化l个分量”门控元素y必须被计算或提供（在某些问题中，它可以很容易地推断出来），IDOL提供了两种选择。通过如上所述，加权和标量化一般不具有这种性质（特别是在离散变量问题的情况下）（参见，例如，在一个实施例中，[3]，p.[4]，p. 73，[5]，pp.3754-56）。对于切比雪夫标量化，导出每个帕累托最优解的能力取决于是否存在能够解决问题（2）的求解器。当前版本的IDOL旨在处理多目标MIP线性问题（即，所有函数都是线性的，变量可以是连续的或整数的问题为了解决这个问题，有必要在（2）中去掉（非线性）最大值函数。（2）的以下等效公式：最小sx∈ X0S.T.（三）s≥λl（y<$l−fl（x））+ρek（y <$−f（x）），l=1，. . . ，k.Kaliszewski和Olga Karelkina软件X 19（2022）1011093=−f（x）llFig. 1. IDOL前端图。是线性的，只要函数f l（x），l1，. . . ，k，以及定义X 0的约束都是线性的。切比雪夫标量化的一个独特之处在于，它提供了一种简单易行的方法来操作帕累托最优性（或效率）测试。也就是说，x<$∈X0是帕累托最优的，当且仅当它解（2），其中λ<$l=y<$1其中，l=1，. . . ，k，[6].1.3. 潜在贡献IDOL背后的想法是简化从线性加权标量化到切比雪夫标量化的迁移。IDOL产生切比雪夫标量化文件，但不提供问题解决。由于生成的文件是通用的LP（线性规划）格式，因此可以使用任何MIP求解器来解决底层问题。据我们所知，没有MIP求解器或独立应用程序提供这样的功能。IDOL提供的功能，必须实现每次一个是解决多目标优化问题的Chebyshev标量化。在解决此类问题的大规模实例时，手头有这样一个支持性应用程序可以节省大量的时间和精力。在[7，8]中报道的实验可以作为例子。优化，特别是多目标优化，是一个通用的建模框架，适用于人类活动的任何领域。从采用该框架的最新说明性研究论文中，可以列举出，例如，[9IDOL有潜力帮助任何多目标优化建模企业在任何这样的领域与最全面的方法。1.4. 其它相关工作文献中报告了两个类似的学术倡议。其中之一是NIMBUS，这是一种用于连续优化问题的通用非线性专业求解器，可通过Web服务访问[12]。第二个是onlinemoco.web[13]，混合整数优化问题。该服务旨在导出所有帕累托最优解（对于纯整数优化问题）或一组具有代表性的帕累托最优解，一种想要的品质。这个想法是好的，只要一个停留在中等规模的问题的范围内。然而，当一个人诉诸解决大规模的问题，这种方法的复杂性变得令人望而却步。1.5. 输入数据格式IDOL处理LP格式的输入数据，Guideline流派。LP格式是优化问题的输入数据格式之一LP格式的Guideline类型要求变量的系数与变量名之间用空白字符分隔开。此外，假定在输入数据文件中呈现多个对象的Guidelines标准（参见[2]，cf.也是第3节中的例子）。2. 软件描述2.1. 软件功能IDOL的主要功能是从问题文件中生成包含切比雪夫标量化问题数据的文件。制作的文件可以下载。问题文件可以用用户指定的方法上传（公式（1）中所需的元素）和/或权重集合如果没有，指定，IDOL使用自由Cbc MIP求解器计算一个，参见。第2.1节.从问题文件生成的切比雪夫标量化文件可以通过改变y_s、改变权重集或两者来修改。细节IDOL由客户端和服务器端组成。客户端在IDOL的主页上，用户可以注册，登录，注销，并转到她/他的个人我的问题页面。或者，她/他可以在没有注册的情况下进入所有未注册用户共享的问题页面。这两种类型的页面都列出了上传的问题文件。这两个页面的功能是类似的。在这里，用户可以上传一个新的问题文件，提交上传的问题文件，以产生切比雪夫标量化文件，更新权值集或y∈（s），下载Chebyshev标量化文件，或删除问题文件（见图① 的人。Kaliszewski和Olga Karelkina软件X 19（2022）1011094图二. 切比雪夫标量化工作流程。每个IDOL页面都包含用于注册、登录和注销的导航栏。为了上传问题文件（UPLOAD按钮），用户被引导到上传表单以选择问题文件，并且可选地，包含权重集的文本文件和包含以下内容的文本文件y（s）。如果未指定y_n，IDOL将计算y_n。如果没有一组权重则所有权重都设置为1。上传文件后，用户将被重定向回“问题”（我的问题）页面，该页面现在列出了上传的问题文件。此外，在数据库中，将创建新的问题文件实例，并将关联的文件保存在云上。用户可以添加或修改权重集和/或通过UPDATE表单输入（更新按钮）。在MAKE Chebyshev按钮上单击IDOL开始生成Chebyshev标量化文件。页面上的状态框更改为服务器端在服务器端生成切比雪夫标量化文件。切比雪夫标量化工作流程如图所示。 二、IDOL利用Python-MIP包和开源的Cbc MIP求解器作为建模和优化工具来生成Chebyshev标量化文件。2.2. 软件构架IDOL是用Python编写的，基于Django Web框架。IDOL遵循Django MVT（模型-视图-模板组件）设计模式。模型组件由包含用户文件、标量化参数和结果的数据库组成。所有文件都存储在Amazon S3云上。视图组件负责应用程序背后的整个逻辑它包含用于输入文件处理、参考点y值计算、和切比雪夫标量化。模型和视图构成了应用程序的服务器端。客户端在模板中表示。它包含用户可见的HTML页面和JavaScript动态更新的内容计算y，这意味着解决多个线性优化-问题，是一项长期的任务。为了避免阻塞客户端的进程，这些任务由Celery后台工作者和Redis消息代理管理。Scalarization 任 务 的 状 态 由 Celery beat 轮 询 ， 并 通 过WebSockets和Django Channels在客户端每秒更新一次。IDOL架构如图所示。3.第三章。3. 说明性示例在当前版本中，IDOL处理输入LP文件，其中包含多个约束多目标背包问题的数据。这类问题具有非负系数、二元变量和下面的玩具例子的项目组合选择问题制定为一个单约束双准则背包问题。问题文件，LP格式，Guesthouse流派，有两个目标，如下所示：最大化多目标表1：优先级=1权重=1 AbsTol=0 RelTol=09 x1 +7 x2 + 8 x3 + 8 x4 + 6 x5 + 9 x6 + 1 x7表2：优先级=1权重=1 AbsTol=0 RelTol=0 x1 + 4x2 + 2 x3 + 3 x4 + 3 x5 + 2 x6 + 8 x7受约束1：70 x1 + 12 x2 + 33 x3 + 40 x4 + 65 x5 + 75 x6 + 45 x7 =155二进制x1 x2 x3 x4 x5 x6 x7结束图三. IDOL Web服务体系结构。Kaliszewski和Olga Karelkina软件X 19（2022）1011095=≥≥====-∗∗--包含λ1的切比雪夫标量化问题的文件λ21 、目标函数容差0，ρ0的情况。001,ε0的情况。1在下面介绍。为了构建这个文件，IDOL解决了两个优化问题分别最大化每个目标函数。 原始 问题文件 中的参数 Priority 、Weight 、AbsTol 和RelTol将被忽略。最小化OBJROW：s受约束1：70 x1 + 12 x2 + 33 x3 + 40 x4 + 65 x5 + 75 x6 + 45 x7 =155s1：s + 1.001 f1 + 0.001 f2 32.1492s2：s + 0.001000 f1 + 1.01000 f2 17.1492f1：9 x1+7 x2+8 x3+8 x4+6 x5+9 x6+1 x7-f1=0f2：x1+4x2+2 x3+3 x4+3 x5+2 x6+8 x7-f2=0界限0 = x1 = 10 = x2 = 10 = x3 = 10 = x4 = 10 = x5 = 10 = x6 = 10 = x7 = 1整数电话：+86-10 - 8888888传真：+86-10 - 88888888端变量s是切比雪夫标量化所必需的附加变量。两个（在一般情况下为k）附加约束s1和s2有助于该线性化。两个（在一般情况下为k）附加约束f1和f2定义变量f1和f2，变量f1和f2携带目标函数的值引入变量f1和f2（一般情况下为k个变量），得到约束s1和s2（一般情况下为k个 改变λ仅改变f i的系数，其中i 1，. . .，k.变量的指定与输入文件中的变量指定不同，但它们是等效的。它是CBC求解器采用的标准。这个切比雪夫标量化问题的例子，如果提交给MIP求解器，会产生一个帕累托最优解，f1（x）=29，f2（x）12个（与（y1）maxx∈X0f1（x）32岁，（2岁）maxx∈X0f2（x）17）.可以证明不存在权重这个问题的加权标量化产生了这个解。在https：//github中可以找到许多大规模切比雪夫标量化问题。com/rombicosi/IDOL/tree/master/examples。4. 影响多目标优化是一种通用的工具，可以应用于人类活动的任何领域然而，其目前的使用没有充分利用现有方法的潜力。这样做的后果是，一些偏好的帕累托最优解可能会被忽略。IDOL试图填补这一空白。该应用程序为用户提供了信心，即可以全面分析正在考虑的问题，这意味着：没有解决方案是先验排除在考虑之外的。5. 结论IDOL为用户提供了获得每个帕累托最优解的完整方法，没有任何例外。任何熟练的程序员都可以在一个专业的应用程序中复制它的功能，而不需要付出很大的努力。IDOL的价值在于推广这种方法并简化应用它的工作。因此，它的潜在受益者是科学、教育和商业应用。竞合利益作者声明，他们没有已知的竞争性财务利益或个人关系，可能会影响本文报告的工作附录A. 补充数据与本文相关的补充材料可以在https://doi.org/10.1016/j.softx.2022.101109上找到。补充材料包含IDOL客户端功能的所有网页的屏幕截图。引用[1] 近地天体。2022年，https://neos-server.org/neos/。最后访问时间：2022年4月20日。[2]GuidanceOptimizerReferenceManual，ver.9.5.2021年，https://www.gurobi。com/documentation/9.5/refman/index.html。[3]Miettinen KM.非线性多目标优化Kluwer AcademicPublishers;1999.[4]埃格特湾 多目标优化。 Springer;2005.[5]卡利谢夫斯基岛复杂多准则决策的软计算。New York：Springer;2006.[6]Kaliszewski I，Mirofortagh J，Podkopaev D.多目标优化的多准则决策-工具箱。Springer; 2016.[7]Kaliszewski I ， Mirofortenj. 关 于 Pareto 前 沿 的 上 近 似 。 JGlobalOptim2018;72：475-90.[8]Kaliszewski I，Mirofordinger J.合作多目标优化与目标函数的界限。J GlobalOptim2021;79：369-85.[9]杨文伟，王晓，王晓伟，王晓伟.选择最适宜能源作物的多标准分析IntJSustain Energy 2016;35（1）：47-58. http://dx.doi.org/10.1080/14786451的网站。2014.898640。[10]范海佛伦R，海门BJM，Breedveld S. 应用于口咽癌的全自动多目标治疗计划的参考点方法的 自 动 配 置 。医学物理2020;47（4）：1499[11][10]张文辉，张文辉，张文辉.利用智能空间信息的大型航空公司航线网络多目标优化。Int J Interact Multimedia Artif Intell2020;6（1）：123-31.[12]雨云。2022年，https://wwwnimbus.it.jyu.fi。最后访问时间：2022年2月[13]在线互联网2022年，http://www.onlinemoco.com/MOIP/。最后访问时间：2022年2月10日[14]COIN-OR 分 支 和 切 割 求 解 器 -CBC ， 版 本 2.10.8.2022 ，http://dx.doi.org/10.5281/zenodo.6522795。