A heuristic for multiple choice programming (Q1089261)

A linear programming-based heuristic procedure for solving Multiple Choice Programming (MCP) problems is presented. Two pivot schemes which may be viewed as the specialized versions of those in ''Pivot and Complement'', an efficient heuristic by \textit{E. Balas} and \textit{C. H. Martin} [Manage. Sci. 26, 86-96 (1980; Zbl 0442.90060)] for pure 0-1 programming, are incorporated into the procedure along with the additional features of cut generation, variable fixing and exchange operation. Three types of MCP problems were tested to evaluate the performance of our procedure. The computational results with seventy five test problems indicate that our heuristic is superior to the default option of APEX-III, which dictates to end the search for better solutions if one within ten per cent of optimum has been found, in both its computational efficiency and the quality of the solution obtained.