Retrieve Solution pool with AMPL and Gurobi#

solution_pool.ipynb Open In Colab Kaggle Gradient Open In SageMaker Studio Lab Hits

Description: This notebook describes how to retrieve multiple solutions from the solver’s solution pool. Optimization problems usually have several optimal solutions, one is returned by the solver but the others are discarded. These alternative solutions can also be retrieved by AMPL.

Tags: solution pool, gurobi, cplex, xpress, mip, mixed-integer-linear, mp

Notebook author: Marcos Dominguez Velad <marcos@ampl.com>, Gleb Belov <gleb@ampl.com>

Model author: Marcos Dominguez Velad <marcos@ampl.com>

# Install dependencies
%pip install -q amplpy

# Google Colab & Kaggle integration
from amplpy import AMPL, ampl_notebook

ampl = ampl_notebook(
    modules=["gurobi", "xpress", "cplex", "copt"],  # modules to install
    license_uuid="default",  # license to use
)  # instantiate AMPL object and register magics

Solution pool#

More often than not, optimization problems have more than one optimal solution; moreover, during the solution process, MIP solvers usually find sub-optimal solutions, which are normally discarded. They can be however be kept, and in most cases there are solver-specific options to control how the search for additional solutions is performed.

The main (and generic) options that controls the search are sol:stub and sol:count, which control respectively the base-name for the files where additional solution will be stored and if to count additional solutions and return them in the nsol problem suffix. Specifying a stub name automatically enables the solutions count; found solutions are written to files [solutionstub1.sol’, … solutionstub.sol].

This is one of the features of the MP drivers, see other advanced modeling in:

https://mp.ampl.com/features-guide.html

To illustrate this behavior, a simple model with random weights and multiple solutions is proposed. After that, different solvers supporting Solution Pool are used, and the different solutions are retrieved by AMPL once the problem is solved.

Solvers that allow multiple solutions: gurobi, xpress, cplex, copt, scip.

Model#

%%writefile weights.mod
param n;
set I := 1..n;
var x{I} integer >= 0 <= 2;
param w{i in I} := 10 + floor(Uniform(0,500)) mod 200;

maximize profit:
    sum{i in I} w[i] * x[i];

s.t. capacity:
    sum{i in I} x[i] <= 133;

Overwriting weights.mod

Activate solution pool#

Each solution will go into a separated “.sol” file.

  • sol:stub option controls the base name of the solution files (synonym for ams_stub, solstub, solutionstub).

  • sol:poollimit is the maximum of solutions that can be retrieved (synonym for ams_limit, poollimit, solnlimit).

  • sol:poolgap is the relative tolerance for reporting alternate MIP solutions (default: Infinity, no limit) (synonym for ams_eps, poolgap).

  • sol:poolgapabs is absolute tolerance for reporting alternate MIP solutions (default: Infinity, no limit) (synonym for ams_epsabs, poolgapabs).

  • sol:count: 0*/1: Whether to count the number of solutions and return it in the “.nsol” problem suffix. The number and kind of solutions are controlled by the sol:pool… parameters. Value 1 implied by sol:stub.

  • sol:poolmode search mode for MIP solutions when sol:stub/sol:count are specified to request finding several alternative solutions:

    • 0 - Just collect solutions during normal solve, and sort them best-first

    • 1 - Make some effort at finding additional solutions

    • 2 - Seek “poollimit” best solutions (default). ‘Best solutions’ are defined by the poolgap(abs) parameters.

There may be more options to customize the behavior of the solution pool, please, check the specific options of your solver to know more:

  • Gurobi options: https://dev.ampl.com/solvers/gurobi/options.html

  • Xpress options: https://dev.ampl.com/solvers/xpress/options.html

  • Cplex options: https://dev.ampl.com/solvers/cplex/options.html

from amplpy import AMPL


def run_problem(solver):
    ampl = AMPL()
    # read model
    ampl.read("weights.mod")
    ampl.param["n"] = 1200

    # enable solution pool
    ampl.option[
        "mp_options"
    ] = f"sol:stub=savesol_{solver} sol:poollimit=5 sol:poolmode=2"
    # call the solver
    ampl.solve(solver=solver)

    # retrieve solutions as a dictionary
    solution_pool = []
    for i in range(1, ampl.get_value("profit.npool") + 1):
        ampl.eval(f"solution savesol_{solver}{i}.sol;")
        sol = ampl.get_solution(flat=False, zeros=False)
        solution_pool.append(sol)
    return solution_pool

Run with Gurobi#

solver = "gurobi"
solutions = run_problem(solver=solver)
for i, sol in enumerate(solutions):
    print(f"Solution {i}:")
    print(sol["x"])

Gurobi 12.0.1:   sol:stub = savesol_gurobi
  sol:poollimit = 5
  sol:poolmode = 2
Gurobi 12.0.1: optimal solution; objective 27061
60 simplex iterations
551 branching nodes
 
5 alternative solution(s)
  with objective values 27061..27059
  written to 'savesol_gurobi1.sol' ... 'savesol_gurobi5.sol'.

suffix nsol OUT;
suffix npool OUT;
Gurobi 12.0.1: Alternative solution 1, objective 27061
Gurobi 12.0.1: Alternative solution 2, objective 27061
Gurobi 12.0.1: Alternative solution 3, objective 27061
Gurobi 12.0.1: Alternative solution 4, objective 27059
Gurobi 12.0.1: Alternative solution 5, objective 27059
Solution 0:
{19: 2, 37: 2, 45: 2, 48: 2, 61: 2, 71: 2, 97: 2, 107: 2, 145: 2, 167: 2, 183: 2, 206: 2, 256: 2, 263: 2, 266: 2, 272: 2, 305: 2, 369: 2, 379: 2, 399: 2, 401: 2, 416: 2, 434: 2, 444: 2, 449: 2, 452: 2, 496: 2, 507: 2, 520: 2, 563: 2, 568: 2, 583: 2, 585: 2, 623: 2, 630: 2, 644: 2, 646: 2, 649: 2, 661: 2, 680: 2, 681: 2, 712: 2, 758: 2, 771: 2, 810: 2, 827: 2, 829: 2, 831: 2, 858: 2, 860: 2, 871: 2, 925: 2, 926: 2, 928: 2, 931: 2, 949: 2, 993: 1, 999: 2, 1020: 2, 1088: 2, 1092: 2, 1104: 2, 1105: 2, 1142: 2, 1165: 2, 1176: 2, 1197: 2}
Solution 1:
{19: 2, 37: 2, 45: 2, 48: 2, 61: 2, 71: 2, 97: 1, 107: 2, 145: 2, 167: 2, 183: 2, 206: 2, 256: 2, 263: 2, 266: 2, 272: 2, 305: 2, 369: 2, 379: 2, 399: 2, 401: 2, 416: 2, 434: 2, 444: 2, 449: 2, 452: 2, 496: 2, 507: 2, 520: 2, 563: 2, 568: 2, 583: 2, 585: 2, 623: 2, 630: 2, 644: 2, 646: 2, 649: 2, 661: 2, 680: 2, 681: 2, 712: 2, 758: 2, 771: 2, 810: 2, 827: 2, 829: 2, 831: 2, 858: 2, 860: 2, 871: 2, 925: 2, 926: 2, 928: 2, 931: 2, 949: 2, 993: 2, 999: 2, 1020: 2, 1088: 2, 1092: 2, 1104: 2, 1105: 2, 1142: 2, 1165: 2, 1176: 2, 1197: 2}
Solution 2:
{19: 2, 37: 2, 45: 2, 48: 2, 61: 2, 71: 2, 107: 2, 145: 2, 167: 2, 183: 2, 206: 2, 256: 2, 263: 2, 266: 2, 272: 2, 305: 2, 369: 2, 379: 2, 399: 2, 401: 2, 416: 2, 434: 2, 444: 2, 449: 2, 452: 2, 496: 2, 507: 2, 520: 2, 563: 2, 568: 2, 583: 2, 585: 2, 623: 2, 630: 2, 644: 2, 646: 2, 649: 2, 661: 2, 680: 2, 681: 2, 712: 2, 758: 2, 771: 2, 810: 2, 827: 2, 829: 2, 831: 2, 858: 2, 860: 2, 871: 2, 889: 1, 925: 2, 926: 2, 928: 2, 931: 2, 949: 2, 993: 2, 999: 2, 1020: 2, 1088: 2, 1092: 2, 1104: 2, 1105: 2, 1142: 2, 1165: 2, 1176: 2, 1197: 2}
Solution 3:
{19: 2, 37: 2, 45: 2, 48: 2, 61: 2, 71: 2, 107: 2, 145: 2, 167: 2, 183: 1, 206: 2, 256: 2, 263: 2, 266: 2, 272: 2, 305: 2, 369: 2, 379: 2, 399: 2, 401: 2, 416: 2, 434: 2, 444: 2, 449: 2, 452: 2, 496: 2, 507: 2, 520: 2, 563: 2, 568: 2, 583: 2, 585: 2, 623: 2, 630: 2, 644: 2, 646: 2, 649: 2, 661: 2, 680: 2, 681: 2, 712: 2, 758: 2, 771: 2, 810: 2, 827: 2, 829: 2, 831: 2, 858: 2, 860: 2, 871: 2, 889: 2, 925: 2, 926: 2, 928: 2, 931: 2, 949: 2, 993: 2, 999: 2, 1020: 2, 1088: 2, 1092: 2, 1104: 2, 1105: 2, 1142: 2, 1165: 2, 1176: 2, 1197: 2}
Solution 4:
{19: 2, 37: 2, 45: 2, 48: 2, 61: 2, 71: 2, 97: 2, 107: 2, 145: 2, 167: 2, 183: 1, 206: 2, 256: 2, 263: 2, 266: 2, 272: 2, 305: 2, 369: 2, 379: 2, 399: 2, 401: 2, 416: 2, 434: 2, 444: 2, 449: 2, 452: 2, 496: 2, 507: 2, 520: 2, 563: 2, 568: 2, 583: 2, 585: 2, 623: 2, 630: 2, 644: 2, 646: 2, 649: 2, 661: 2, 680: 2, 681: 2, 712: 2, 758: 2, 771: 2, 810: 2, 827: 2, 829: 2, 831: 2, 858: 2, 860: 2, 871: 2, 925: 2, 926: 2, 928: 2, 931: 2, 949: 2, 993: 2, 999: 2, 1020: 2, 1088: 2, 1092: 2, 1104: 2, 1105: 2, 1142: 2, 1165: 2, 1176: 2, 1197: 2}

Run with Cplex#

solver = "cplex"
solutions = run_problem(solver=solver)
for i, sol in enumerate(solutions):
    print(f"Solution {i}:")
    if "x" in sol:  # cplex may have the trivial solution in the pool, that it's empty
        print(sol["x"])
    else:
        print("Trivial solution")

CPLEX 22.1.1:   sol:stub = savesol_cplex
  sol:poollimit = 5
  sol:poolmode = 2
CPLEX 22.1.1: optimal solution; objective 27061
1 simplex iterations
 
5 alternative solution(s)
  with objective values 27061..0
  written to 'savesol_cplex1.sol' ... 'savesol_cplex5.sol'.

suffix nsol OUT;
suffix npool OUT;
CPLEX 22.1.1: Alternative solution 1, objective 27061
CPLEX 22.1.1: Alternative solution 2, objective 26538
CPLEX 22.1.1: Alternative solution 3, objective 26512
CPLEX 22.1.1: Alternative solution 4, objective 0
CPLEX 22.1.1: Alternative solution 5, objective 26680
Solution 0:
{19: 2, 37: 2, 45: 2, 48: 2, 61: 2, 71: 2, 97: 2, 107: 2, 145: 2, 167: 2, 183: 2, 206: 2, 256: 2, 263: 2, 266: 2, 272: 2, 274: 1, 305: 2, 369: 2, 379: 2, 399: 2, 401: 2, 416: 2, 434: 2, 444: 2, 449: 2, 452: 2, 496: 2, 507: 2, 520: 2, 563: 2, 568: 2, 583: 2, 585: 2, 623: 2, 630: 2, 644: 2, 646: 2, 649: 2, 661: 2, 680: 2, 681: 2, 712: 2, 758: 2, 771: 2, 810: 2, 827: 2, 829: 2, 831: 2, 858: 2, 860: 2, 871: 2, 925: 2, 926: 2, 928: 2, 931: 2, 949: 2, 999: 2, 1020: 2, 1088: 2, 1092: 2, 1104: 2, 1105: 2, 1142: 2, 1165: 2, 1176: 2, 1197: 2}
Solution 1:
{1: 1, 2: 2, 3: 2, 19: 2, 37: 2, 45: 2, 48: 2, 61: 2, 71: 2, 107: 2, 145: 2, 167: 2, 183: 2, 206: 2, 256: 2, 263: 2, 266: 2, 272: 2, 305: 2, 369: 2, 379: 2, 399: 2, 401: 2, 416: 2, 434: 2, 444: 2, 449: 2, 452: 2, 507: 2, 520: 2, 563: 2, 568: 2, 583: 2, 585: 2, 623: 2, 630: 2, 644: 2, 646: 2, 649: 2, 661: 2, 680: 2, 681: 2, 712: 2, 758: 2, 771: 2, 810: 2, 827: 2, 829: 2, 831: 2, 858: 2, 860: 2, 871: 2, 925: 2, 926: 2, 928: 2, 931: 2, 949: 2, 999: 2, 1020: 2, 1088: 2, 1092: 2, 1104: 2, 1105: 2, 1142: 2, 1165: 2, 1176: 2, 1197: 2}
Solution 2:
{2: 2, 3: 2, 4: 1, 19: 2, 37: 2, 45: 2, 48: 2, 61: 2, 71: 2, 107: 2, 145: 2, 167: 2, 183: 2, 206: 2, 256: 2, 263: 2, 266: 2, 272: 2, 305: 2, 369: 2, 379: 2, 399: 2, 401: 2, 416: 2, 434: 2, 444: 2, 449: 2, 452: 2, 507: 2, 520: 2, 563: 2, 568: 2, 583: 2, 585: 2, 623: 2, 630: 2, 644: 2, 646: 2, 649: 2, 661: 2, 680: 2, 681: 2, 712: 2, 758: 2, 771: 2, 810: 2, 827: 2, 829: 2, 831: 2, 858: 2, 860: 2, 871: 2, 925: 2, 926: 2, 928: 2, 931: 2, 949: 2, 999: 2, 1020: 2, 1088: 2, 1092: 2, 1104: 2, 1105: 2, 1142: 2, 1165: 2, 1176: 2, 1197: 2}
Solution 3:
Trivial solution
Solution 4:
{1: 1, 2: 2, 7: 1, 19: 2, 37: 2, 45: 2, 48: 2, 61: 2, 71: 2, 107: 2, 145: 2, 167: 2, 183: 2, 206: 2, 256: 2, 263: 2, 266: 2, 272: 2, 305: 2, 369: 2, 379: 2, 399: 2, 401: 2, 416: 2, 434: 2, 444: 2, 449: 2, 452: 2, 496: 1, 507: 2, 520: 2, 563: 2, 568: 2, 583: 2, 585: 2, 623: 2, 630: 2, 644: 2, 646: 2, 649: 2, 661: 2, 680: 2, 681: 2, 712: 2, 758: 2, 771: 2, 810: 2, 827: 2, 829: 2, 831: 2, 858: 2, 860: 2, 871: 2, 925: 2, 926: 2, 928: 2, 931: 2, 949: 2, 999: 2, 1020: 2, 1088: 2, 1092: 2, 1104: 2, 1105: 2, 1142: 2, 1165: 2, 1176: 2, 1197: 2}

AMPL Website | AMPL Colab | Community Edition | Twitter | LinkedIn