poolsearch.py#

#!/usr/bin/env python3.11

# Copyright 2025, Gurobi Optimization, LLC

# We find alternative epsilon-optimal solutions to a given knapsack
# problem by using PoolSearchMode

from __future__ import print_function
import gurobipy as gp
from gurobipy import GRB
import sys

try:
    # Sample data
    Groundset = 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 model
    model = gp.Model("poolsearch")

    # Create dicts for tupledict.prod() function
    objCoefDict = dict(zip(Groundset, objCoef))
    knapsackCoefDict = dict(zip(Groundset, knapsackCoef))

    # Initialize decision variables for ground set:
    # x[e] == 1 if element e is chosen
    Elem = model.addVars(Groundset, vtype=GRB.BINARY, name="El")

    # Set objective function
    model.ModelSense = GRB.MAXIMIZE
    model.setObjective(Elem.prod(objCoefDict))

    # Constraint: limit total number of elements to be picked to be at most
    # Budget
    model.addConstr(Elem.prod(knapsackCoefDict) <= Budget, name="Budget")

    # Limit how many solutions to collect
    model.setParam(GRB.Param.PoolSolutions, 1024)
    # Limit the search space by setting a gap for the worst possible solution
    # that will be accepted
    model.setParam(GRB.Param.PoolGap, 0.10)
    # do a systematic search for the k-best solutions
    model.setParam(GRB.Param.PoolSearchMode, 2)

    # save problem
    model.write("poolsearch.lp")

    # Optimize
    model.optimize()

    model.setParam(GRB.Param.OutputFlag, 0)

    # Status checking
    status = model.Status
    if status in (GRB.INF_OR_UNBD, GRB.INFEASIBLE, GRB.UNBOUNDED):
        print("The model cannot be solved because it is infeasible or unbounded")
        sys.exit(1)

    if status != GRB.OPTIMAL:
        print(f"Optimization was stopped with status {status}")
        sys.exit(1)

    # Print best selected set
    print("Selected elements in best solution:")
    print("\t", end="")
    for e in Groundset:
        if Elem[e].X > 0.9:
            print(f" El{e}", end="")
    print("")

    # Print number of solutions stored
    nSolutions = model.SolCount
    print(f"Number of solutions found: {nSolutions}")

    # Print objective values of solutions
    for e in range(nSolutions):
        model.setParam(GRB.Param.SolutionNumber, e)
        print(f"{model.PoolObjVal:g} ", end="")
        if e % 15 == 14:
            print("")
    print("")

    # print fourth best set if available
    if nSolutions >= 4:
        model.setParam(GRB.Param.SolutionNumber, 3)

        print("Selected elements in fourth best solution:")
        print("\t", end="")
        for e in Groundset:
            if Elem[e].Xn > 0.9:
                print(f" El{e}", end="")
        print("")

except gp.GurobiError as e:
    print(f"Gurobi error {e.errno}: {e.message}")

except AttributeError as e:
    print(f"Encountered an attribute error: {e}")