A heuristic algorithm for mixed-integer programming problems
Generate an AI Snapshot to get a quick, structured summary of this paper.
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
The heuristic algorithm was successful in obtaining exact optimal solutions for many problems with known optimal solutions and the quality of the obtained solutions seem to be quite high.
Abstract
A heuristic algorithm for solving mixed-integer programming problems is proposed. The basic idea is to search good feasible solutions located near the LP optimal solution. It consists of four phases: Phase 0, computation of LP optimal solution; Phase 1, computation of the central trajectory T of the feasible region; Phase 2, search for (integer) feasible solutions along T; Phase 3, improvements of feasible solutions. The computational results are encouraging. For example, randomly generated problems with 50 constraints and 400 variables consumed 2∼3 minutes on a FACOM 230/60. The quality of the obtained solutions seem to be quite high. In fact, for many problems with known optimal solutions, our algorithm was successful in obtaining exact optimal solutions.