A Novel and Effective Integer Optimization Approach for the NSF Panel Assignment Problem: A Multi-Resource and Preference ¿Constrained Assignment Problem

Web Published:
11/30/2011
Description:

Princeton University Invention # 06-2223-1

           

In this work, an enhanced version of the generalized assignment problem (GAP), called the NSF panel assignment problem, is posed.  The GAP has been the subject of considerable research over the last two decades and has many real life applications including job scheduling, production planning, modeling of computer and communication networks, storage space allocation, vehicle routing and facility location problems.  The GAP seeks to determine the minimum cost assignment of n jobs to m agents so that each job is assigned to exactly one agent subject to resource restrictions on the agents.  The GAP can be formulated as an integer programming problem where binary assignment variables are used to indicate if an agent is to perform a job.  Because the GAP is an NP-hard problem, heuristic solutions are often necessary to solve large-scale instances. 

 

Researchers at Princeton University have developed a new mathematical formulation to solve a modified version of the generalized assignment problem (GAP), called the panel assignment problem. The mathematical formulation and associated solution process have been thoroughly tested and implemented in a publicly available on-line solver.

 

The NSF panel assignment is an enhanced version of the multi-resource GAP.  Each job has a specific number of agents assigned to it and each agent has a lower and upper bound on the number of jobs that can be assigned to it.  In addition, preference criteria are incorporated to assign each agent to a specific position for a job, introducing preference-based constraints.  The panel assignment problem seeks to find an assignment of reviewers to proposals on a panel so as to optimize the sum of the preference criteria for each reviewer on each proposal while ensuring that each reviewer is assigned to approximately the same number of proposals.  This multi-resource and preference-constrained generalized assignment problem can be formulated as an integer linear programming problem and can be solved to optimality. 

 

In this work, a mathematical model has been developed to address the NSF panel assignment problem and some representative example problems are solved to demonstrate the effectiveness of the proposed approach.  In addition, a web-based interface has been created to allow users to solve different instances of the NSF panel assignment problem.

 

  

Princeton is currently seeking industrial collaborators to commercialize this technology. Patent protection is pending.

 

 

For more information on Princeton University Invention # 06-2223-1, please contact:

               

 

                                Laurie Tzodikov

                                Office of Technology Licensing and Intellectual Property

                                Princeton University

                                4 New South Building

                                Princeton, NJ 08544-0036

                                (609) 258-7256

                                (609) 258-1159 fax

                                tzodikov@princeton.edu

Patent Information:
For Information, Contact:
Laurie Tzodikov
Licensing Associates
Princeton University
tzodikov@Princeton.EDU
Inventors:
Christodoulos Floudas (DECEASED) See Fotini P. Baba
Stacy Janak
Martin Taylor
Maria Burka
T J Matziaris
Keywords: