| There are a wide variety of combinatorial optimization problems in fields ranging from defense and semiconductor manufacturing to financial engineering and facility location. Many of these optimization problems are nondeterministic polynomial time (NP)-hard for a single objective, meaning that large problem instances are difficult to solve optimally in a reasonable amount of time. Also, many real-world problems involve multiple conflicting objectives. Unfortunately, many of these problems also need to be solved repeatedly and quickly, as is the case with machine scheduling problems in industry.;Rather than generating the full set of efficient solutions (which solves the problem for any trade-off among the objectives), this technique uses an interactive approach to solving multi-objective combinatorial optimization problems. The technique uses a genetic algorithm to develop solutions to the optimization problem, and employs convex preference cones generated from interactions with the decision maker in the evaluation of the solutions. These interactions serve to guide the genetic algorithm into more preferred regions of the solution space while only restricting that the preference function is a quasiconcave function of the objectives.;The interactive genetic algorithm uses a reasonable number of decision maker interactions and provides good solutions to the multi-objective knapsack, parallel machine scheduling, and facility location problems. The experiments show that the technique is promising for multi-objective combinatorial optimization problems with an unknown quasiconcave preference function that need to be solved more quickly than the set of efficient solutions can be generated. |
