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

9973339在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.