Computational Study of the Maximal Inscribing Ellipsoid Problem and Applications to Integer Programming

求n维空间中内接给定多面体的最大体积椭球问题具有重要的应用前景。 然而，缺乏实际有效的算法和软件，为这个问题，到目前为止，阻碍了它在实践中的实际应用。 拟议的项目将试图纠正这种情况。 首先，我们计划开发和实现高效，实用的算法和可移植的库软件来解决这个问题。 要研究的算法将是不可行的原始-对偶邻域点方法的变体。 其次，我们将利用所得到的软件来开发和实现整数规划的算法，这些整数规划具有在很大范围内变化的非二进制变量，并且难以用传统的分支定界技术来解决。给定平面上的多边形，可以容纳在多边形内的最大椭圆是什么？ 这个问题可以很容易地从二维空间（平面）推广到更高维的空间，导致所谓的最大体积椭球问题。 在许多情况下，解决这个问题所需的计算时间决定了我们解决应用中更复杂问题的速度，例如，制造和管理决策过程中的问题。 在这个项目中，我们将开发快速的方法和建立高效的计算机代码来解决最大体积椭球问题，然后将代码应用于解决应用问题。

9973339The problem of finding the maximum-volume ellipsoid inscribing a given polytope in n-dimensional space has many important application potentials. However, the lack of practically efficient algorithms and software for this problem has so far hampered its actual applications in practice. The proposed project will attempt to rectify this situation. Firstly, we plan to develop and implement efficient, practical algorithms and portable library software for solving the problem. The algorithms to be studied will be variants of infeasible primal-dual interior-point methods. Secondly, we will utilize the resulting software to develop and implement algorithms for integer programs that have non-binary variables varying in wide ranges and are difficult to solve for conventional branch-and-bound techniques.Given a polygon on the plane, what is the largest ellipse that can fit inside the polygon? This question can be easily generalized from the two-dimensional space (the plane) to higher-dimensional spaces, resulting in the so-called maximum-volume ellipsoid problem. In many cases, the amount of computing time required for solving this problem determines how fast we can solve more complicated problems in applications, for example, problems in manufacturing and managerial decision-making processes. In this project, we will develop fast methods and build efficient computer code for solving the maximum-volume ellipsoid problem, and then apply the code to solving application problems.