# Example of enumerating the n-best solutions when solving a MIP.
#
# The program reads a problem from a file and collects solutions into a pool.
# Depending on the setting of a search_method parameter, it will enumerate
# additional solutions. There is an optional parameter to specify the maximum
# number of solutions to collect.
#
# The parameter search_method can be "collect", "extended" or "n-best". For
# "collect" it just collects solutions without changing the branch and bound
# search behaviour. For a value of "extended" it adjusts the branch and bound
# cutoff so that the algorithm searches suboptimal nodes for additional
# solutions. The value of "n-best" uses branching directives to force branching
# on integer feasible nodes, fully enumerating the tree and finding the best
# solutions.
#
# The example implements its own solution pool with solutions stored in order
# of objective value, and implements duplication checks. Almost all the
# interesting work happens within the preintsol callback. It collects
# solutions, checks for duplicates and adjusts the cutoff for the remaining
# search. The adjustment of the cutoff is crucial to ensure additional
# solutions are found.
#
# (C) 2025-2026 Fair Isaac Corporation
import xpress as xp
import numpy as np
import argparse
import math
COLLECT = "collect" # Collect solutions with no change to branch and bound
EXTENDED = "extended" # Extend the branch and bound search by adjusting the cutoff to keep suboptimal nodes
N_BEST = "n-best" # Use branching directives to fully enumerate the branch and bound tree
def hash_solution(solution, col_is_enumerated):
"""Calculates a simple hash across the solution values of enumerated columns
"""
return hash(tuple(round(x) for x, ifenum in zip(solution, col_is_enumerated) if ifenum))
class Solution:
"""Solution class for solutions in a pool
"""
def __init__(self, col_is_enumerated, x, objval):
self.x = x
self.col_is_enumerated = col_is_enumerated
self.hash = hash_solution(x, col_is_enumerated)
self.objval = objval
def __eq__(self, other):
"""Compares solutions for equality based on the integer columns
"""
for col in range(len(self.x)):
if self.col_is_enumerated[col] == 1:
# integral value of should be the same
if math.fabs(self.x[col] - other.x[col]) > 0.5:
return False
return True
def __hash__(self):
return self.hash
class SolutionPool:
"""SolutionPool class for storing a set of distinct best solutions
"""
def __init__(self, ncols, obj_sense, max_solutions, objgap):
self.sol_list = [] # Solutions ordered from best to worst
self.sol_dict = dict() # For identifying duplicate solutions
self.ncols = ncols
self.obj_sense = obj_sense
self.max_solutions = max_solutions
self.objgap = objgap
def is_sol_better(self, sol1, sol2):
return self.obj_sense * sol1.objval < self.obj_sense * sol2.objval
def del_solution(self, sol):
del self.sol_dict[sol]
self.sol_list.remove(sol)
def add_solution(self, sol):
if sol in self.sol_dict:
# The solution is already known, keep the duplicate with the best objective
duplicate_sol = self.sol_dict[sol]
if not self.is_sol_better(sol, duplicate_sol):
return
# Previous solution had worse objective value, delete it from the pool
self.del_solution(duplicate_sol)
# Add solution to the pool
self.sol_dict[sol] = sol
# Insert the solution in the correct position in the list
idx = 0
while idx < len(self.sol_list) and not self.is_sol_better(sol, self.sol_list[idx]):
idx += 1
self.sol_list.insert(idx, sol)
# Remove the worst solutions if we have too many
while len(self.sol_list) > self.max_solutions:
self.del_solution(self.sol_list[-1])
# If we are using an objective gap, drop any solutions which are too poor
if self.objgap is not None:
cutoff_obj = self.get_cutoff_obj()
while len(self.sol_list) > 0 and self.sol_list[-1].objval * self.obj_sense > cutoff_obj * self.obj_sense:
self.del_solution(self.sol_list[-1])
def get_cutoff_obj(self):
"""Returns the worst objective that should be accepted"""
if self.objgap is not None and len(self.sol_list) > 0:
# Reject solutions that are objgap worse than the best solution found
best_obj = self.sol_list[0].objval
return best_obj + self.obj_sense * (abs(best_obj) * self.objgap)
elif len(self.sol_list) >= self.max_solutions:
# We already have the required number of solutions, so set the
# cutoff such that we only search for improving solutions
worst_obj = self.sol_list[-1].objval
return worst_obj
else:
# No cutoff: search for any solution
return self.obj_sense * xp.infinity
class CallbackData:
"""Callback data
"""
def __init__(self):
self.pool = None
self.col_is_enumerated = None
self.obj_sense = xp.minimize
self.search_method = N_BEST
def preintsol_callback(prob, cb_data, soltype, cutoff):
# Collect the new solution.
# We have to use prob.getCallbackSolution() to retrieve the solution since
# it has not been installed as the incumbent yet
x = prob.getCallbackSolution()
# Get solution objective value
objval = prob.attributes.lpobjval
# Add the new solution to our pool.
sol = Solution(cb_data.col_is_enumerated, x, objval)
cb_data.pool.add_solution(sol)
if cb_data.search_method == COLLECT:
# We just collect the solutions and don't adjust the search.
newcutoff = cutoff
else:
# Adjust the cutoff so we continue finding solutions.
newcutoff = cb_data.pool.get_cutoff_obj() + (-1e-6 * cb_data.obj_sense)
return (0, newcutoff)
def select_enumeration_columns(prob, ncols, col_is_enumerated):
coltype = prob.getColType()
# Identify the integer restricted columns.
for col in range(ncols):
if (coltype[col] == 'B') or (coltype[col] == 'I'):
col_is_enumerated[col] = 1
else:
col_is_enumerated[col] = 0
def enforce_enumeration_columns(prob, ncols, col_is_enumerated):
# We use the Xpress branch directives to force Xpress to continue branching
# on any column that we want enumerated.
colSelect = []
for col in range(ncols):
if col_is_enumerated[col] == 1:
colSelect.append(col)
prob.loadBranchDirs(colSelect)
def main():
parser = argparse.ArgumentParser(
description='Enumerates and collects multiple solutions to a MIP'
)
parser.add_argument('filename', help='MPS or LP file to solve')
parser.add_argument('search_method', help='How to collect solutions',
choices=[COLLECT, EXTENDED, N_BEST])
parser.add_argument('--maxsols', help='Maximum number of solutions to collect',
type=int, default=10)
parser.add_argument('--objgap', help='If specified, solutions more than objgap worse than the best solution will be discarded',
type=float, required=False)
args = parser.parse_args()
# Create the problem
prob = xp.problem(f'solenum {args.filename}')
# Read the file
prob.readProb(args.filename)
# Set up the callback data for the preintsol callback
ncols = prob.attributes.cols
cb_data = CallbackData()
cb_data.obj_sense = prob.attributes.objsense
cb_data.pool = SolutionPool(ncols, cb_data.obj_sense, max(1, args.maxsols), args.objgap)
cb_data.search_method = args.search_method
# Set up the enumeration columns
cb_data.col_is_enumerated = np.zeros(ncols, dtype=np.int8)
select_enumeration_columns(prob, ncols, cb_data.col_is_enumerated)
if args.search_method == N_BEST:
enforce_enumeration_columns(prob, ncols, cb_data.col_is_enumerated)
# Add the callback
prob.addPreIntsolCallback(preintsol_callback, cb_data, 0)
# Set important controls
prob.controls.serializepreintsol = 1
prob.controls.miprelstop = 0
if args.search_method == N_BEST:
prob.controls.mipdualreductions = 0
# Optimize
prob.optimize()
# Print out results
print()
if len(cb_data.pool.sol_list) == 0:
print('No solutions collected!')
else:
print(f'Collected {len(cb_data.pool.sol_list)} solutions with objective values:')
for sol in cb_data.pool.sol_list:
print(f' {sol.objval}')
main()
|
