Generating Multiple Solutions for Mixed Integer Programming Problems
Generating Multiple Solutions for Mixed Integer Programming Problems
复制标题
DOI：
10.1007/978-3-540-72792-7_22
复制
发表时间：
2007-06
期刊：
影响因子：
--
通讯作者：
E. Danna;M. Fenelon;Zonghao Gu;Roland Wunderling
中科院分区：
文献类型：
--
作者：
E. Danna;M. Fenelon;Zonghao Gu;Roland Wunderling
随着混合整数规划(MIP)问题在实际中变得更容易解决，它们被用于越来越多的应用中，在这些应用中，产生唯一的最优解通常不足以回答潜在的商业问题。例如，一些优化标准或一些约束很难建模，或者需要多个解决方案以在数据更改的情况下进行快速解决方案修复。在本文中，我们讨论了如何有效地为同一模型生成多个解的问题，集中在最优解和近最优解上。我们首先对问题进行了形式化的定义，研究了问题的复杂性，并给出了三种不同的求解算法。我们介绍的主要算法是单树算法，它是对标准分支定界算法的修改。我们的第二个算法是基于MIP启发式的。第三种算法推广了以前按顺序生成解的方法。然后，我们通过大量的计算实验表明，单树算法在生成多个解的速度方面显著优于以前已知的算法，同时提供了可接受的解的多样性水平。
As mixed integer programming (MIP) problems become easier to solve in pratice, they are used in a growing number of applications where producing a unique optimal solution is often not enough to answer the underlying business problem. Examples include problems where some optimization criteria or some constraints are difficult to model, or where multiple solutions are wanted for quick solution repair in case of data changes. In this paper, we address the problem of effectively generating multiple solutions for the same model, concentrating on optimal and near-optimal solutions. We first define the problem formally, study its complexity, and present three different algorithms to solve it. The main algorithm we introduce, the one-tree algorithm, is a modification of the standard branch-and-bound algorithm. Our second algorithm is based on MIP heuristics. The third algorithm generalizes a previous approach that generates solutions sequentially. We then show with extensive computational experiments that the one-tree algorithm significantly outperforms previously known algorithms in terms of the speed to generate multiple solutions, while providing an acceptable level of diversity in the solutions produced.