2016/02/25 by Joey Huchette, Huchette, Joey, Santanu S. Dey +3
Computer Science · Engineering · Mathematics · #Advanced Optimization Algorithms Research #FOS: Mathematics #Formal Methods in Verification #Optimization and Control (math.OC) #VLSI and FPGA Design Techniques
paper · pdf · doi:10.48550/arxiv.1602.07802
openalex publication_date 2016/02/25 · openalex created_date 2022/10/03 · openalex updated_date 2026/07/28
For many mixed-integer programming (MIP) problems, high-quality dual bounds\ncan be obtained either through advanced formulation techniques coupled with a\nstate-of-the-art MIP solver, or through semidefinite programming (SDP)\nrelaxation hierarchies. In this paper, we introduce an alternative bounding\napproach that exploits the "combinatorial implosion" effect by solving portions\nof the original problem and aggregating this information to obtain a global\ndual bound. We apply this technique to the one-dimensional and two-dimensional\nfloor layout problems and compare it with the bounds generated by both\nstate-of-the-art MIP solvers and by SDP relaxations. Specifically, we prove\nthat the bounds obtained through the proposed technique are at least as good as\nthose obtained through SDP relaxations, and present computational results that\nthese bounds can be significantly stronger and easier to compute than these\nalternative strategies, particularly for very difficult problem instances.\n