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

我们的研究项目旨在开发高效的MIP解算器技术，主要由三个子项目组成。用数学规划方法加速MIP求解器的研究作为本研究项目的第一步，我们验证了最近提出的作为MIP(混合整数规划)精确算法的IBM(整基方法)的有效性。通常，MIP解算器求解困难实例的大部分计算时间被用来证明现有可行解的最优性。IBM有可能比传统方法更快地证明最优性。在我们的项目之前，只存在IBM的一个实现。我们实现了IBM来解决QAP(二次分配问题)和一般的IP(整数规划问题)。对于QAP，我们向IBM提出了几类有效的不等式，并利用连续松弛问题方法和有效的变量选择规则提出了几种技巧。我们正在寻找将我们的建议应用于基于IBM的MIP解决方案的有效方法。采用并行处理方法加速MIP解算器的研究我们在Condor/MW系统上实现了一个计算煎饼图直径的并行算法。实现的算法与一般MIP中使用的分枝定界算法具有相同的结构。因此，用于求解煎饼图直径的技术将有助于通用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.