Research on Speeding Up Techniques for General Mixed Integer Programming Problem Solvers

我们的研究项目旨在开发高效的MIP求解技术，主要由三个子项目组成。在本课题的第一步，我们验证了IBM （Integral Basis Method）算法的有效性，该算法是最近提出的一种精确的MIP （Mixed Integer programming Problem）算法。一般来说，MIP求解器的大部分计算时间都用于求解困难实例，以证明现有可行解的最优性。IBM有可能比传统方法更快地证明最优性。在我们的项目之前，只存在IBM的一个实现。我们为QAP（二次分配问题）和通用IP（整数规划问题）实现了IBM。我们为QAP提出了一些有效不等式的类别，并提出了使用连续松弛问题方法和有效变量选择规则的几种技术。我们正在寻找将我们的建议应用于基于ibm的MIP解决方案的有效方法。利用Condor/MW系统实现了一种计算煎饼图直径的并行算法。所实现的算法与常见MIPs中使用的分支定界算法具有相同的结构。因此，用于求解煎饼图直径的技术将有助于一般MIP求解器的并行化。MIP求解器门户的设计本研究项目仍处于设计阶段。在这个项目之后，我们将继续开发MIP求解器门户。

Our research project, which aim is to develop efficient techniques for MIP solvers, is mainly composed of three parts of subprojects.1. Research on speed up MIP solvers by mathematical programming approachAs the first step of this research project, we validated the effectiveness of the IBM (Integral Basis Method) which was recently proposed as an exact algorithm of MIP (Mixed Integer programming Problem). Generally, the most of computation time of MIP solvers to solve hard instances is used to prove the optimality of incumbent feasible solutions. The IBM has a possibility to prove the optimality faster than the traditional methods. Before our project only an implementation of IBM existed. We implemented IBM for the QAP (Quadratic Assignment Problem) and the general IP (Integer programming Problem). We proposed some classes of valid inequalities to IBM for the QAP and also proposed several techniques using continuous relaxation problem methods and effective variable selection rules. We are searching for effective methods of applying our proposals to IBM-based MIP solvers.2. Research on speed up MIP solvers by parallel processing approachWe implemented a parallel algorithm to compute the diameter of pancake graphs using the Condor/MW system. The implemented algorithm has the same structure with the branch and bound algorithm used in common MIPs. Therefore, the techniques used for solving the diameter of pancake graphs would be contributed for the parallelization of general MIP solvers.3. Designing a MIP Solver PortalThis research project is still a design phrase. We will continue to develop a MIP Solver Portal after this project.