A Cardinality Induced Disaggregated Formulation of the Generalized Assignment Problem and Its Facets
Ishwar Murthy
Indian Institute of Management, Bangalore, Bannerghatta Road, Bangalore 560076, INDIA,
ishwar@iimb.ernet.in
Sam Ransbotham
Carroll School of Management, Boston College, Chestnut Hill, MA 02467, USA, sam.ransbotham@bc.edu
October 19, Friday, 13:40
Place: EA-409
We present a new disaggregated formulation of the Generalized Assignment Problem (GAP), consisting of O(mn2) variables and constraints, where m denotes the number of agents and n the number of jobs. In contrast, the traditional formulation consists of O(mn) variables and constraints. The disaggregated formulation is stronger than the traditional formulation; the linear programming relaxation of the disaggregated formulation provides tighter lower bounds. Furthermore, this new formulation provides additional opportunities for generalizations of the well-known Cover and (1, k)-Configuration inequalities that are not present in the traditional formulation. Under certain restrictive conditions, both inequalities are shown to be facets of the polytope defined by feasible solutions of GAP. We introduce two classes of inequalities involving multiple agents that are specific to this formulation. One class of inequalities is called the Bar-and-Handle (1, ) Inequality, which under certain restrictive condition is a facet of the polytope defined by feasible solutions of GAP. Finally, we introduce another important class of inequality called the 2-Agent Cardinality Matching Inequality involving exactly two agents. Given the un-capacitated version of GAP in which each agent can process all jobs, we first show this inequality to be facets of the polytope defined by the associated bipartite graph. We then show how this inequality can be easily lifted to become a facet of the polytope defined by feasible solutions of GAP. Finally, we show that when m = 2, this inequality, along with trivial facets completely describe the polytope associated with the un-capacitated version of GAP.
Bio: Ishwar Murthy is a Professor in Decision Sciences and Information Systems Area at the Indian Institute of Management (IIM) Bangalore, India. He is on leave from IIM Bangalore and is currently visiting Bilkent University. His research interests are in Discrete and Stochastic Optimization and their applications in operations, marketing and finance. His teaching interests are in Business Analytics and Spreadsheet based Decision Models.
He holds a B. Tech in Mechanical Engineering from IIT Kanpur, India and a M.B.A. from North-East Louisiana University, USA. He obtained his PhD in Management Science from Texas A&M University, USA.
He has publications in leading journals such as Management Science, Operations Research, Naval Research Logistics, Networks and INFORMS Journal on Computing. Prior to joining IIM Bangalore, he was a tenured faculty member at Louisiana State University, USA. He has also served as a visiting faculty at the Indian Institute of Management, Ahmedabad, Krannert Graduate School of Management at Purdue University, USA, the Chinese University of Hong Kong, Georgia Tech. University, USA and University of Texas, Dallas, USA