SGER: Solution Evaluation Methods for Multi-objective Combinatorial Optimization Algorithms

Arizona State University, Scottsdale AZ

Investigators

Abstract

This Small Grant for Exploratory Research (SGER) will investigate methods for evaluating and comparing heuristically derived solutions to multi-objective combinatorial optimization problems. Almost all such problems are NP-Hard, so characterizing the Pareto-optimal efficient set is computationally intractable. The research will draw on heuristic and approximate solution methods for these models, and structure a approach to comparing them based on distance to the (possibly) unknown Pareto set. Drawing on promising preliminary results for small models, the research will seek to develop and extend the methods to higher dimension. Multi-objective optimization problems model important tradeoffs that decision makers face in many settings. For example, in strategic facilities location problems, decision makers must trade off minimizing cost and maximizing service. Most of these problems are also combinatorial, in that discrete decisions such as build or don't build require choice of one option or another without the opportunity to compromise the difference. Such models are so common in engineering practice that advances in methods for treating them have great potential significance to the broad field of operations research.