Genetic Algorithm for Multi-choice Integer Linear Programming Problems

Genetic algorithms (GAs) are very powerful techniques to solve difficult combinatorial optimization problems. Multi-choice programming (MCP) belongs to a class of combinatorial optimization problems where the decision maker (DM) has to choose a value from a number of alternative choices and to find a combination which optimizes an objective function subject to a given set of constraints. In many of the real-life optimization problems, the solution of some problems cannot be fractions and must be specified as integers, and solving of such types of problems is called integer programming (IP). In this paper, a genetic algorithm (GA) for nonlinear integer programming (NLIP) to solve a multi-choice integer linear programming (MCILP) problem is proposed. Here, we consider an MCILP problem where some or all right-hand side parameters of the constraints may have multiple choices. The multi-choice parameters in the problem are handled using the interpolating polynomials. After constituting interpolating polynomials corresponding to all multi-choice parameters, an NLIP model is formulated. Using our proposed GA, optimal integer solution of the NLIP model is obtained. Lastly, some illustrative examples are presented to support the solution procedure.