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.

Basic Usage 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 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
    }
}

Gap Usage Example

When we only want some of the solutions based off a tolerance away from optimal, this can be done using the abs_opt_gap parameter. This is shown in the following simple knapsack examples where the weights and values are the same.

>>> import pyomo.environ as pyo
>>> import pyomo.contrib.alternative_solutions as aos

>>> values = [10,9,2,1,1]
>>> weights = [10,9,2,1,1]

>>> K = len(values)
>>> capacity = 12

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

>>> solns = aos.enumerate_binary_solutions(m, num_solutions=10, solver="glpk", abs_opt_gap = 0.0)
>>> assert(len(solns) == 4)

In this example, we only get the four Solution objects that have an objective_value of 12. Note that while we wanted only those four solutions with no optimality gap, using a gap of half the smallest value (in this case .5) will return the same solutions and avoids any machine precision issues.

>>> import pyomo.environ as pyo
>>> import pyomo.contrib.alternative_solutions as aos

>>> values = [10,9,2,1,1]
>>> weights = [10,9,2,1,1]

>>> K = len(values)
>>> capacity = 12

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

>>> solns = aos.enumerate_binary_solutions(m, num_solutions=10, solver="glpk", abs_opt_gap = 0.5)
>>> assert(len(solns) == 4)
>>> for soln in sorted(solns, key=lambda s: str(s.get_variable_name_values())):
...     print(soln)
{
    "fixed_variables": [],
    "objective": "o",
    "objective_value": 12.0,
    "solution": {
        "x[0]": 0,
        "x[1]": 1,
        "x[2]": 1,
        "x[3]": 0,
        "x[4]": 1
    }
}
{
    "fixed_variables": [],
    "objective": "o",
    "objective_value": 12.0,
    "solution": {
        "x[0]": 0,
        "x[1]": 1,
        "x[2]": 1,
        "x[3]": 1,
        "x[4]": 0
    }
}
{
    "fixed_variables": [],
    "objective": "o",
    "objective_value": 12.0,
    "solution": {
        "x[0]": 1,
        "x[1]": 0,
        "x[2]": 0,
        "x[3]": 1,
        "x[4]": 1
    }
}
{
    "fixed_variables": [],
    "objective": "o",
    "objective_value": 12.0,
    "solution": {
        "x[0]": 1,
        "x[1]": 0,
        "x[2]": 1,
        "x[3]": 0,
        "x[4]": 0
    }
}

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.

This function implements a no-good cuts technique inheriting from Balas’s work on Canonical Cuts [BJ72].

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.lp_enum_solnpool.enumerate_linear_solutions_soln_pool(model, num_solutions=10, rel_opt_gap=None, abs_opt_gap=None, zero_threshold=1e-05, solver_options={}, tee=False)[source]

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

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.
zero_threshold (float) – The threshold for which a continuous variables’ value is considered to be equal to zero.
solver_options (dict) – Solver option-value pairs to be passed to the 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.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.

Parameters:

model (ConcreteModel) – 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_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.
refine_discrete_bounds (boolean) – Boolean indicating that new constraints should be added to the model at each iteration to tighten the bounds for discrete variables.
warmstart (boolean) – Boolean indicating that the solver should be warmstarted from the best previously discovered solution.
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.

Returns:

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]