• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文学位 >On selecting disjunctions for solving mixed integer programming problems.
【24h】

On selecting disjunctions for solving mixed integer programming problems.

机译：关于选择析取项来解决混合整数规划问题。

获取原文
获取原文并翻译 | 示例
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

Mixed integer linear programs (MIPs) offer a flexible way to model a variety of real-world problems. In this thesis, we undertake a comprehensive study of "general disjunctions" that are a fundamental concept underlying most solution techniques for MIPs, with the aim of extending the current understanding of the theory of these disjunctions and also of developing novel ways of using them so as to enhance the performance of current state of the art MIP solvers.;Solving MIPs is difficult both theoretically (it lies in the class of so called NP -hard problems) and in practice as well. Two algorithms that have been most successful in solving MIPs are the "branch-and-bound" and the "cutting-plane" algorithm. The concept of valid disjunctions , which are logical conditions that will be satisfied by any feasible solution is fundamental to both these algorithms. In branch-and-bound, one recursively imposes valid disjunctions on the problem to create smaller "subproblems" and solves the LP relaxations of these subproblems until a solution is found or the problem can be shown infeasible. The cutting-plane algorithm works on the principle that any inequality valid for each subproblem resulting from the imposition of a given disjunction is also valid for the original MIP. Such valid inequalities are iteratively added until an optimal solution is exposed or the feasible region can be shown to be empty. The performance of both algorithms thus greatly depends on which valid disjunctions are selected and imposed at each step.;In this thesis, we consider the problem of selecting disjunctions from a rich class that we call "general disjunctions". Our work is divided into two parts: theory and computation. In the first part, we analyze the computational complexity of finding the "optimal" disjunction based on specific criteria. We show that the problem is in general NP -hard, i.e., this problem is theoretically as difficult as solving the original MIP. We also show that the problem of selecting a general disjunction remains NP -hard when several natural restrictions are imposed. These results lead to analogous results for the branch-and-bound and the cutting-plane algorithm: the problem of selecting a general disjunction that maximally improves the bound when used to branch and the problem of finding an "elementary split inequality" that maximally improves the bound are both NP -hard. We also develop a polynomial-time algorithm that solves the separation problem for the elementary split closure when the point to be separated lies on an edge (i.e., a one dimensional face) of the feasible region of the LP relaxation.;In the second part, we perform several computational experiments to study the effect of employing methods for finding an "optimal" general disjunction on the performance of the branch-and-cut algorithm. We start by formulating the problem of finding an "optimal" general disjunction as a MIP. In a branch-and-bound setting, the solutions obtained from exact solution of these problems lead to significant reduction in the number of steps in the recursive procedure. When the set of allowed disjunctions is further restricted, one can use explicit enumeration techniques to select the optimal disjunction. We develop a procedure that eliminates poor choices of disjunctions in such a procedure by analyzing the solutions obtained from other disjunctions. We observe in our experiments that the use of this procedure reduces significantly the number of disjunctions that are evaluated for two particular types of general disjunctions.;We also use the disjunctions obtained from the techniques described above to generate valid inequalities. We observe that the number of inequalities needed to improve the bound is significantly fewer than that required by the existing techniques that generate the "most-violated" inequalities. In all our experiments, the time required to select the disjunctions by attempting to solve the above-mentioned formulation using an exact method was prohibitive. This underscores the importance of developing fast computational methods for solving these problems. To motivate future work, we describe some open problems related to our work.
机译：混合整数线性程序（MIP）提供了一种对各种实际问题建模的灵活方法。在本文中，我们对“一般析取”进行了全面的研究，这是大多数MIP解决方案技术所依据的基本概念，目的是扩展对这些析取理论的当前理解，并开发出新颖的用法。在理论上（在所谓的NP硬问题类别中）和在实践中都很难解决MIP。解决MIP方面最成功的两种算法是“分支约束”和“切割平面”算法。有效分离的概念是任何可行解决方案都可以满足的逻辑条件，这对于这两种算法都是至关重要的。在分支定界中，对问题递归地施加有效的析取关系以创建较小的“子问题”，并解决这些子问题的LP松弛问题，直到找到解决方案或该问题无法显示为止。切平面算法的工作原理是，由于强加给定的析取力而对每个子问题有效的任何不等式对于原始MIP也是有效的。反复添加此类有效不等式，直到暴露出最佳解或可以证明可行区域为空为止。因此，这两种算法的性能在很大程度上取决于在每个步骤中选择并施加了哪些有效的析取关系。在本文中，我们考虑了从称为“一般析取关系”的丰富类中选择析取关系的问题。我们的工作分为两个部分：理论和计算。在第一部分中，我们分析了基于特定标准找到“最优”分离的计算复杂性。我们证明该问题通常是NP困难的，即从理论上讲该问题与解决原始MIP一样困难。我们还表明，当强加几个自然限制时，选择一般析取的问题仍然是NP-hard。这些结果导致了分支定界算法和切割平面算法的相似结果：选择一般分支以最大程度地改善分支时的界线问题，以及找到最大程度改善“基本分裂不等式”的问题边界都是NP难的。我们还开发了多项式时间算法，当要分离的点位于LP弛豫的可行区域的边缘（即一维面）上时，解决了基本拆分闭合的分离问题。 ，我们进行了一些计算实验，以研究采用各种方法找到“最优”一般析取函数对分支剪切算法性能的影响。我们首先提出寻找“最佳”一般分离作为MIP的问题。在分支定界设置中，从这些问题的精确解决方案中获得的解决方案导致递归过程中步骤数的显着减少。当允许的析取集进一步受到限制时，可以使用显式枚举技术来选择最佳析取。通过分析从其他析取物中获得的解，我们开发了一种消除析取中选择不当的过程。我们在实验中观察到，使用此过程可以显着减少针对两种特定类型的一般析取进行评估的析取数量;我们还使用从上述技术获得的析取来生成有效不等式。我们观察到，改善边界所需的不平等数量明显少于产生“违反程度最大”的不平等的现有技术所需要的数量。在我们所有的实验中，通过尝试使用精确方法求解上述配方来选择析取词所需要的时间是令人望而却步的。这强调了开发快速计算方法来解决这些问题的重要性。为了激励未来的工作，我们描述了一些与我们的工作有关的未解决的问题。

著录项

  • 作者

    Mahajan, Ashutosh.;

  • 作者单位

    Lehigh University.;

  • 授予单位 Lehigh University.;
  • 学科 Engineering Industrial.
  • 学位 Ph.D.
  • 年度 2009
  • 页码 151 p.
  • 总页数 151
  • 原文格式 PDF
  • 正文语种 eng
  • 中图分类 一般工业技术;
  • 关键词

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号