Solving large Multiple Knapsack Assignment problems with Gurobi

Two of my Kutztown University colleagues (Yun Lu and Myung Soon Song) and I assisted by our students are on a “mission” to demonstrate that operations researchers (especially practitioners) can obtain state of the art results for many difficult combinatorial optimization problems (especially binary integer programming problems) using Gurobi in either a single pass or in an iterative mode.  These solutions are generated very quickly by Gurobi and the small gaps guarantee that these solutions are very close to the optimums.  As an example, I we published in International Transactions in Operational Research an article in which we demonstrate that using Gurobi either in single pass or iterative mode can generate solutions in a timely manner comparable to the best published algorithms for the Multiple-Choice Multi-dimensional Knapsack Problem.  We have published several other articles that show similar results for other binary integer programs (BIP). 

My reason for writing is because we have been using Gurobu to solve Multiple Knapsack Assignment Problems (MKAP) discussed in the 2020 Omega article by Martello and Monaci and we have been getting unexpected results for a few of the largest MKAP instances.  The unexpected results occur when we use our simple sequential increasing tolerance (SSIT) method in which after a fixed amount of execution time the termination tolerance is loosened and Gurobi is executed for a fixed amount of time before the tolerance is loosened again.  SSIT has worked very well to get tightly bounded solutions (small gaps) quickly for a variety of BIP.  Details of SSIT are discussed in our ITOR article and. 

Specifically, for problem probT4_10e3_0U_R50_T100_M800_N8000_seed04 from SET4 with 8000 items, 800 knapsacks, and 100 item classes (the 8000 items are partitioned into 100 classes and only items from the same class can be put in a knapsack) running Gurobi for 3600 seconds at the default tolerance of 0.0001 resulted in a solution with objective function value of 3,205,675 and a final gap of 1.5% (most of our other results have gaps of less than 0.2% and are executed in less than two minutes).  However, when we used SSIT and loosened the tolerance after 600 seconds, the gap did not decrease and was still 83.7% after 1800 seconds which was the total execution time for SSIT.  Also, the objective function for the SSIT run was only 1,772,101 (this is a maximization problem).  The SSIT run had a tolerance of 0.001 for 600 seconds, then 0.005 for 600 seconds, then 0.01 for 300 seconds, and finally 0.02 for 300 seconds.  However, the gap calculated by Gurobi never dropped below 83.7%.  In contrast, by the time Gurobi had executed for 1200 seconds using the default tolerance of 0.0001, the gap had been reduced to 2.9% and as stated before, the gap was 1.5% after 3600 seconds executing Gurobi at 0.0001 tolerance.  We do not understand why the gap is not reduced in the SSIT run.  We have used Gurobi and the SSIT strategy to solve literally over 1000 BIP and this never happened before.  In fact, even for these large MKAPs it only happens when there are 8000 items to be packed into 800 knapsacks.  The number of classes can be either 50 or 100.  This means that for probT4_10e3_0U_R50_T100_M800_N8000_seed04 there are mn+mr = 800x8000 +800x100 = 6,480,000 variables and n+m+mr = 8000+800+800x100 = 88,800 constraints. 

We would very much appreciate if someone could comment on what is happening in this situation.  If you need to examine any files associated with this problem such as engine logs, etc., we will have our graduate student, Emre Shively-Ertas, who executed all the Gurobi runs communicate directly (ccing Lu, Song, and myself) with you.  Please let us know if anyone can assist us with understanding what is going on with the situation described above and how to rectify it. 

Thank you for your assistance, 

Fran Vasko