Getting the upper bound of an objective function (MILP with HiGHS)

Specific Domains Optimization (Mathematical)
1

I’m working on an assignment problem where the solver maximizes

@objective(model, Max, sum(B[u] for u in U))

where B is a binary vector of entities satisfying some conditions in the assignment plan A[u, f, t], which denotes a task assigned to user u at factory f at a time t.

In some cases, I’m not interested in getting the actual allocation plan but just to know how many users will actually satisfy my set of other constraints. I’d typically set a time limit or iteration limit, and HiGHS seems to be doing a good job at computing this upper bound, as I can tell when reading the “BestBound” column from the output.

However, I cannot find anything in the API that could return that value, as JuMP / HiGHS would trigger an error as the set of solutions is empty.

Did I miss anything?

I had a look at the HiGHS source code, and I believe I’d need to access this value:

// HighsMipSolverData.cpp

  std::array<char, 16> lb_string =
      convertToPrintString((int)mipsolver.orig_model_->sense_ * lb);
2

There a function ObjectiveBound in MathOptInterface. I typically use something like:

using MathOptInterface
const MOI = MathOptInterface
...
bestbound = MOI.get(model, MOI.ObjectiveBound())

This works at least with CPLEX.

3

Thanks. I’m actually already using the objective_bound() function from the wrapper, but this fails if there’s no best solution found. e,g,

        Nodes      |    B&B Tree     |            Objective Bounds              |  Dynamic Constraints |       Work
     Proc. InQueue |  Leaves   Expl. | [BestBound]       BestSol              Gap |   Cuts   InLp Confl. | LpIters     Time

         0       0         0   0.00%   (72             ) -inf                 inf        0      0      0         0    17.8s

Then, if I try to access MOI.ObjectiveBound()) after the solver stops, I get

BestBound: Inf

ERROR: LoadError: Result index of attribute MathOptInterface.ObjectiveValue(1) out of bounds. There are currently 0 solution(s) in the model.
4

Unfortunately, I forgot to mention that I only check for bounds if an integer solution already exists by if result_count( model ) > 0 ... end.
I had several times a similar problem, namely to obtain the LP relaxation, for which I have not yet found a solution other then computing it manually by relaxing the integers constraints.

5

I’m working on a patch to extend the HiGHS API.
Will report the results here.