Generating Alternative (Near-)Optimal Solutions

Optimization solvers are generally designed to return a feasible solution to the user. However, there are many applications where a user needs more context than this result. For example,

  • alternative optimal solutions can be used to assess trade-offs between competing objectives;

  • comparisons amongst alternative solutions provide insights into the efficacy of model predictions with inaccurate or untrusted optimization formulations; or

  • alternative optimal solutions create an opportunity to understand a design space, including assessments of unexpressed objectives and constraints;

  • alternative solutions can be identified to support the future analysis of model revisions (e.g. to account for previously unexpressed constraints).

The alternative-solutions library provides a variety of functions that can be used to generate optimal or near-optimal solutions for a pyomo model. Conceptually, these functions are like pyomo solvers. They can be configured with solver names and options, and they return a pool of solutions for the pyomo model. However, these functions are independent of pyomo’s solver interfaces because they return a custom pool manager object.

The following functions are defined in the alternative-solutions library:

  • enumerate_binary_solutions()

    • Finds alternative optimal solutions for a binary problem using no-good cuts.

  • enumerate_linear_solutions()

    • Finds alternative optimal solutions for continuous variables in a (mixed-integer) linear program using iterative solutions of an integer programming formulation.

  • gurobi_enumerate_linear_solutions()

    • Finds alternative optimal solutions for a (mixed-binary) linear program using Gurobi to generate lazy cuts.

  • gurobi_generate_solutions()

    • Finds alternative optimal solutions for discrete variables using Gurobi’s built-in solution pool capability.

  • obbt_analysis_bounds_and_solutions()

    • Calculates the bounds on each variable by solving a series of min and max optimization problems where each variable is used as the objective function. This can be applied to any class of problem supported by the selected solver.

A Simple Example

Many of the functions in the alternative-solutions library have similar options, so we simply illustrate the enumerate_binary_solutions() function.

We define a simple knapsack example whose alternative solutions have integer objective values ranging from 0 to 70.

>>> import pyomo.environ as pyo

>>> values = [20, 10, 60, 50]
>>> weights = [5, 4, 6, 5]
>>> capacity = 10

>>> m = pyo.ConcreteModel()
>>> m.x = pyo.Var(range(4), within=pyo.Binary)
>>> m.o = pyo.Objective(expr=sum(values[i] * m.x[i] for i in range(4)), sense=pyo.maximize)
>>> m.c = pyo.Constraint(expr=sum(weights[i] * m.x[i] for i in range(4)) <= capacity)

The function enumerate_binary_solutions() generates a pool of Solution objects that represent alternative optimal solutions:

>>> import pyomo.contrib.alternative_solutions as aos
>>> solns = aos.enumerate_binary_solutions(m, num_solutions=100, solver="glpk")
>>> assert len(solns) == 9
>>> print( [soln.objective().value for soln in solns] )
[70.0, 70.0, 60.0, 60.0, 50.0, 30.0, 20.0, 10.0, 0.0]

Enumerating Near-Optimal Solutions

The previous example enumerated all feasible solutions. However optimization models are typically used to identify optimal or near-optimal solutions. The abs_opt_gap and rel_opt_gap arguments are used to limit the search to these solutions:

  • rel_opt_gap : non-negative float or None

    • The relative optimality gap for allowable alternative solutions. Specifying a gap of None indicates that there is no limit on the relative optimality gap (i.e. that any feasible solution can be considered).

  • abs_opt_gap : non-negative float or None

    • The absolute optimality gap for allowable alternative solutions. Specifying a gap of None indicates that there is no limit on the absolute optimality gap (i.e. that any feasible solution can be considered).

For example, we can generate all optimal solutions as follows:

>>> solns = aos.enumerate_binary_solutions(m, num_solutions=100, solver="glpk", abs_opt_gap=0.0)
>>> print( [soln.objective().value for soln in solns] )
[70.0, 70.0]

Similarly, we can generate the six solutions within 40 of the optimum:

>>> solns = aos.enumerate_binary_solutions(m, num_solutions=100, solver="glpk", abs_opt_gap=40.0)
>>> print( [soln.objective().value for soln in solns] )
[70.0, 70.0, 60.0, 60.0, 50.0, 30.0]