#!/usr/bin/env python3# Copyright 2025, Gurobi Optimization, LLC# We find alternative epsilon-optimal solutions to a given knapsack# problem by using PoolSearchModeimportgurobipyasgpfromgurobipyimportGRBimportsystry:# Sample dataGroundset=range(10)objCoef=[32,32,15,15,6,6,1,1,1,1]knapsackCoef=[16,16,8,8,4,4,2,2,1,1]Budget=33# Create initial modelmodel=gp.Model("poolsearch")# Create dicts for tupledict.prod() functionobjCoefDict=dict(zip(Groundset,objCoef))knapsackCoefDict=dict(zip(Groundset,knapsackCoef))# Initialize decision variables for ground set:# x[e] == 1 if element e is chosenElem=model.addVars(Groundset,vtype=GRB.BINARY,name="El")# Set objective functionmodel.ModelSense=GRB.MAXIMIZEmodel.setObjective(Elem.prod(objCoefDict))# Constraint: limit total number of elements to be picked to be at most# Budgetmodel.addConstr(Elem.prod(knapsackCoefDict)<=Budget,name="Budget")# Limit how many solutions to collectmodel.setParam(GRB.Param.PoolSolutions,1024)# Limit the search space by setting a gap for the worst possible solution# that will be acceptedmodel.setParam(GRB.Param.PoolGap,0.10)# do a systematic search for the k-best solutionsmodel.setParam(GRB.Param.PoolSearchMode,2)# save problemmodel.write("poolsearch.lp")# Optimizemodel.optimize()model.setParam(GRB.Param.OutputFlag,0)# Status checkingstatus=model.Statusifstatusin(GRB.INF_OR_UNBD,GRB.INFEASIBLE,GRB.UNBOUNDED):print("The model cannot be solved because it is infeasible or unbounded")sys.exit(1)ifstatus!=GRB.OPTIMAL:print(f"Optimization was stopped with status{status}")sys.exit(1)# Print best selected setprint("Selected elements in best solution:")print("\t",end="")foreinGroundset:ifElem[e].X>0.9:print(f" El{e}",end="")print("")# Print number of solutions storednSolutions=model.SolCountprint(f"Number of solutions found:{nSolutions}")# Print objective values of solutionsforeinrange(nSolutions):model.setParam(GRB.Param.SolutionNumber,e)print(f"{model.PoolNObjVal:g} ",end="")ife%15==14:print("")print("")# print fourth best set if availableifnSolutions>=4:model.setParam(GRB.Param.SolutionNumber,3)print("Selected elements in fourth best solution:")print("\t",end="")foreinGroundset:ifElem[e].PoolNX>0.9:print(f" El{e}",end="")print("")exceptgp.GurobiErrorase:print(f"Gurobi error{e.errno}:{e.message}")exceptAttributeErrorase:print(f"Encountered an attribute error:{e}")