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 solutions can support an assessment of trade-offs between competing objectives;

  • if the optimization formulation may be inaccurate or untrustworthy, then comparisons amongst alternative solutions provide additional insights into the reliability of these model predictions; or

  • the user may have unexpressed objectives or constraints, which only are realized in later stages of model analysis.

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 list of solutions for the pyomo model. However, these functions are independent of pyomo’s solver interface because they return a custom solution 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 a (mixed-integer) linear program.

  • enumerate_linear_solutions_soln_pool

    • Finds alternative optimal solutions for a (mixed-binary) linear program using Gurobi’s solution pool feature.

  • 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.

Usage Example

Many of 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 90.

>>> import pyomo.environ as pyo

>>> values = [10, 40, 30, 50]
>>> weights = [5, 4, 6, 3]
>>> 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)

We can execute the enumerate_binary_solutions function to generate a list 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) == 10

Each Solution object contains information about the objective and variables, and it includes various methods to access this information. For example:

>>> print(solns[0])
{
    "fixed_variables": [],
    "objective": "o",
    "objective_value": 90.0,
    "solution": {
        "x[0]": 0,
        "x[1]": 1,
        "x[2]": 0,
        "x[3]": 1
    }
}

Interface Documentation

pyomo.contrib.alternative_solutions.enumerate_binary_solutions(model, *, num_solutions=10, variables=None, rel_opt_gap=None, abs_opt_gap=None, search_mode='optimal', solver='gurobi', solver_options={}, tee=False, seed=None)[source]

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

Parameters:

  • model (ConcreteModel) – A concrete Pyomo model

  • num_solutions (int) – The maximum number of solutions to generate.

  • variables (None or a collection of Pyomo _GeneralVarData variables) – The variables for which bounds will be generated. None indicates that all variables will be included. Alternatively, a collection of _GenereralVarData variables can be provided.

  • rel_opt_gap (float or None) – The relative optimality gap for the original objective for which variable bounds will be found. None indicates that a relative gap constraint will not be added to the model.

  • abs_opt_gap (float or None) – The absolute optimality gap for the original objective for which variable bounds will be found. None indicates that an absolute gap constraint will not be added to the model.

  • search_mode ('optimal', 'random', or 'hamming') – Indicates the mode that is used to generate alternative solutions. The optimal mode finds the next best solution. The random mode finds an alternative solution in the direction of a random ray. The hamming mode iteratively finds solution that maximize the hamming distance from previously discovered solutions.

  • solver (string) – The solver to be used.

  • solver_options (dict) – Solver option-value pairs to be passed to the solver.

  • tee (boolean) – Boolean indicating that the solver output should be displayed.

  • seed (int) – Optional integer seed for the numpy random number generator

Returns:

A list of Solution objects. [Solution]

Return type:

solutions

pyomo.contrib.alternative_solutions.enumerate_linear_solutions(model, *, num_solutions=10, rel_opt_gap=None, abs_opt_gap=None, zero_threshold=1e-05, search_mode='optimal', solver='gurobi', solver_options={}, tee=False, seed=None)[source]

Finds alternative optimal solutions a (mixed-integer) linear program.

This function implements the technique described here:

S. Lee, C. Phalakornkule, M.M. Domach, and I.E. Grossmann, “Recursive MILP model for finding all the alternative optima in LP models for metabolic networks”, Computers and Chemical Engineering, 24 (2000) 711-716.

Parameters:

  • model (ConcreteModel) – A concrete Pyomo model

  • num_solutions (int) – The maximum number of solutions to generate.

  • rel_opt_gap (float or None) – The relative optimality gap for the original objective for which variable bounds will be found. None indicates that a relative gap constraint will not be added to the model.

  • abs_opt_gap (float or None) – The absolute optimality gap for the original objective for which variable bounds will be found. None indicates that an absolute gap constraint will not be added to the model.

  • zero_threshold (float) – The threshold for which a continuous variables’ value is considered to be equal to zero.

  • search_mode ('optimal', 'random', or 'norm') – Indicates the mode that is used to generate alternative solutions. The optimal mode finds the next best solution. The random mode finds an alternative solution in the direction of a random ray. The norm mode iteratively finds solution that maximize the L2 distance from previously discovered solutions.

  • solver (string) – The solver to be used.

  • solver_options (dict) – Solver option-value pairs to be passed to the solver.

  • tee (boolean) – Boolean indicating that the solver output should be displayed.

  • seed (int) – Optional integer seed for the numpy random number generator

Returns:

A list of Solution objects. [Solution]

Return type:

solutions

pyomo.contrib.alternative_solutions.gurobi_generate_solutions(model, *, num_solutions=10, rel_opt_gap=None, abs_opt_gap=None, solver_options={}, tee=False)[source]

Finds alternative optimal solutions for discrete variables using Gurobi’s built-in Solution Pool capability. See the Gurobi Solution Pool documentation for additional details.

Parameters:

  • model (ConcreteModel) – A concrete Pyomo model.

  • num_solutions (int) – The maximum number of solutions to generate. This parameter maps to the PoolSolutions parameter in Gurobi.

  • rel_opt_gap (non-negative float or None) – The relative optimality gap for allowable alternative solutions. None implies that there is no limit on the relative optimality gap (i.e. that any feasible solution can be considered by Gurobi). This parameter maps to the PoolGap parameter in Gurobi.

  • abs_opt_gap (non-negative float or None) – The absolute optimality gap for allowable alternative solutions. None implies that there is no limit on the absolute optimality gap (i.e. that any feasible solution can be considered by Gurobi). This parameter maps to the PoolGapAbs parameter in Gurobi.

  • solver_options (dict) – Solver option-value pairs to be passed to the Gurobi solver.

  • tee (boolean) – Boolean indicating that the solver output should be displayed.

Returns:

A list of Solution objects. [Solution]

Return type:

solutions

pyomo.contrib.alternative_solutions.obbt_analysis_bounds_and_solutions(model, *, variables=None, rel_opt_gap=None, abs_opt_gap=None, refine_discrete_bounds=False, warmstart=True, solver='gurobi', solver_options={}, tee=False)[source]

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.

modelConcreteModel

A concrete Pyomo model.

variables: None or a collection of Pyomo _GeneralVarData variables

The variables for which bounds will be generated. None indicates that all variables will be included. Alternatively, a collection of _GenereralVarData variables can be provided.

rel_opt_gapfloat or None

The relative optimality gap for the original objective for which variable bounds will be found. None indicates that a relative gap constraint will not be added to the model.

abs_opt_gapfloat or None

The absolute optimality gap for the original objective for which variable bounds will be found. None indicates that an absolute gap constraint will not be added to the model.

refine_discrete_boundsboolean

Boolean indicating that new constraints should be added to the model at each iteration to tighten the bounds for discrete variables.

warmstartboolean

Boolean indicating that the solver should be warmstarted from the best previously discovered solution.

solverstring

The solver to be used.

solver_optionsdict

Solver option-value pairs to be passed to the solver.

teeboolean

Boolean indicating that the solver output should be displayed.

variable_ranges

A Pyomo ComponentMap containing the bounds for each variable. {variable: (lower_bound, upper_bound)}. An exception is raised when the solver encountered an issue.

solutions

[Solution]

class pyomo.contrib.alternative_solutions.Solution(model, variable_list, include_fixed=True, objective=None)[source]

A class to store solutions from a Pyomo model.

variables

A map between Pyomo variables and their values for a solution.

Type:

ComponentMap

fixed_vars

The set of Pyomo variables that are fixed in a solution.

Type:

ComponentSet

objective

A map between Pyomo objectives and their values for a solution.

Type:

ComponentMap

pprint():

Prints a solution.

get_variable_name_values(self, ignore_fixed_vars=False):

Get a dictionary of variable name-variable value pairs.

get_fixed_variable_names(self):

Get a list of fixed-variable names.

get_objective_name_values(self):

Get a dictionary of objective name-objective value pairs.