Title :
Efficiency improvement in explicit enumeration for integer programming problems
Author_Institution :
Dept. of Ind. Manage., Tungnan Univ., Taipei, Taiwan
Abstract :
An integer programming problem is a mathematical optimization or feasibility program in which some or all of the variables are restricted to be integers. In many cases, the problems can be divided into integer linear programming (ILP) problems and integer non-linear programming (INLP) problems. A more complex problems are mixed integer programming (MIP) problems. There are many algorithms to well solve ILP problems. However, there are relatively fewer algorithms to solve INLP problems. In most situations, the explicit enumeration method (EEM) can be used to solve both kinds of problems. EEM is very simple to implement but with the price of low efficiency. This paper proposes an efficient approach namely Chen´s rearrangement to improve the efficiency in explicit enumeration for integer programming problems. Part of them can also be applied to MIP problems. An interesting example is explored to explain the proposed approach.
Keywords :
integer programming; mathematical analysis; nonlinear programming; Chen rearrangement; EEM; INLP problems; MIP problems; explicit enumeration method; integer nonlinear programming; integer programming problems; mathematical optimization; mixed integer programming; Heuristic algorithms; Linear programming; Operations research; Optimization; Programming; Search problems; Traveling salesman problems; Integer programming problem; brute-force search; exhausted search; explicit enumeration;
Conference_Titel :
Industrial Engineering and Engineering Management (IEEM), 2013 IEEE International Conference on
Conference_Location :
Bangkok
DOI :
10.1109/IEEM.2013.6962382