Improving solver performance through redundancy

详细信息    查看全文

• 作者：Eduardo Lalla-Ruiz ; Stefan Voß
• 关键词：Erraticism ; redundant constraints ; multidimensional multiple ; choice knapsack problem ; dynamic berth allocation problem
• 刊名：Journal of Systems Science and Systems Engineering
• 出版年：2016
• 出版时间：September 2016
• 年：2016
• 卷：25
• 期：3
• 页码：303-325
• 全文大小：763 KB
• 刊物类别：Engineering
• 刊物主题：Systems and Information Theory in Engineering
  Game Theory and Mathematical Methods
  Operation Research and Decision Theory
  Chinese Library of Science
  
• 出版者：Systems Engineering Society of China, co-published with Springer-Verlag GmbH
• ISSN：1861-9576
• 卷排序：25

文摘

It is well known that hierarchies of mathematical programming formulations with different numbers of variables and constraints have a considerable impact regarding the quality of solutions obtained once these formulations are fed to a commercial solver. In addition, even if dimensions are kept the same, changes in formulations may largely influence solvability and quality of results. This becomes evident especially if redundant constraints are used. We propose a related framework for information collection based on these constraints. We exemplify by means of a well-known combinatorial optimization problem from the knapsack problem family, i.e., the multidimensional multiple-choice knapsack problem (MMKP). This incorporates a relationship of the MMKP to some generalized set partitioning problems. Moreover, we investigate an application in maritime shipping and logistics by means of the dynamic berth allocation problem (DBAP), where optimal solutions are reached from the root node within the solver.