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

点击翻译按钮获取中文摘要

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.