| We create a test set of hard generalized assignment problems (GAP) that cannot be solved to optimality in less than one hour of CPU time by either CPLEX or GUROBI. We investigate alternate approaches that, when used in conjunction with an optimizer, either allow optimal solutions or improved feasible solutions to be generated in a reasonable amount of time. Good feasible solutions to GAP problems are generally easy to generate within 2-3 minutes of CPU time using GUROBI or CPLEX. We use this generated upper bound to solve variants of the LP relaxation of the GAP where we iteratively find the minimum and maximum cardinality possible in any optimal solution to the GAP. We also find the minimum possible resource used by each agent in any optimal solution. We add these constraints (among others) to the original problem and resolve with CPLEX and GUROBI. We present computational results that improve upon the standard CPLEX or GUROBI results. |
Updated 02/23/2014