Portal de Periódicos da CAPES

A heuristic for multiple choice programming

1985; Elsevier BV; Volume: 12; Issue: 1 Linguagem: Inglês

10.1016/0305-0548(85)90004-8

1873-765X

Suk‐Gwon Chang, Dong‐wan Tcha,

Smart Parking Systems Research

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 Balas and Martin for pure 0–1 programming, are incorporated into the procedure along with the additional features of cut generation, variable fixing and exchage 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.