Efficiency improvement in explicit enumeration for integer programming problems

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.