Second best choice with Solver

Solver is usually used to find the "best" solution. We aim to maximize value in a knapsack problem, or maybe minimize the scheduling time required for a set of jobs to be completed on some machines, and so on.

But what if we would like to know the second, or third best choice? Maybe we can gain some insights into our problem exploring suboptimal solutions. There are some caveats, but with a bit of VBA this is a feasible problem (pun intended).

Let's start with a simple setup: we manage a business and want to choose from a list of people those that would maximize customers satisfaction. In this respect, each person has been rated from 0 to 20, and expects a pay that is known. Our maximum affordable payment is the only constraint on our choices. Just to make things a bit more interesting, we assume that there are 6 different roles, each one with a given number of persons to be hired.

Worksheet setup

The core of the VBA code is as follows.

For i = 1 To 5

SolverReset

SolverOk SetCell:=Max_satisfaction.Address, MaxMinVal:=1, ByChange:=bin_vars.Address, Engine:=2

SolverAdd CellRef:=Total_payment.Address, Relation:=1, FormulaText:=Affordable.Address

SolverAdd CellRef:=constr_kind.Address, Relation:=2, FormulaText:=req_roles.Address

SolverAdd CellRef:=bin_vars.Address, Relation:=5

If i > 1 Then

    SolverAdd CellRef:=Max_satisfaction.Address, Relation:=1, FormulaText:=curr_max & delta

End If

SolverOptions IntTolerance:=0, Scaling:=True

SolverSolve UserFinish:=True

curr_max = Range("Max_satisfaction").Value

delta = -curr_max * (10 ^ -6)

Next i

At each run of Solver, a small delta is calculated. Then it is subtracted from the previuos maximum, and we add a constraint that limits the new optimum, thus finding a 2nd, 3rd, and so on, best.

In this example the maximum satisfaction can only be an integer value, so our delta is small enough to find all the best choices. If we had to optimize a continuous function with real values, it may happen that our delta was too big, and we miss one (or even many) optimal solutions.

However, we cannot set it too small, unless we change also the constraint precision (default at 0.000001). Precision is a relative value, and this is why delta is multiplied by the maximum before adding the constraint to the model. A smaller delta will require a higher precision, and increase solving time.

File