Or-tools: Is there a way to get intermediate results from the MPSolver?

[JeroenGar]

Hello,

I've been using the MPSolver (CBC) to solve a MIP and I've been wondering if there is any way to get intermediary results while it's running? Is there a way to set a callback or another way to get information about the current best found solution?

I've been searching through the documentation and API but wasn't able to find anything.

Thanks!

Edit: in Java

[Mizux]

Which language do you use ? (c++, python, C#, java )

[Mizux]

AFAIK the MPSolver is only a wrapping the CBC solver
see: https://github.com/google/or-tools/blob/stable/ortools/linear_solver/cbc_interface.cc so unfortunately there is no callback.

If you can use the CP-SAT solver instead then you'll have solution callback support...

[ryan-chien]

Hey @JeroenGar ,

This solution is a bit hacky, but it works:

1. Set a time limit on the solver via set_time_limit that is _less than the known solve time_, or simply very small.
2. Write a solve loop that queries if the solution is optimal, and if not, adds an additional time increment onto the time limit.

A lot of code left out, but you can see the strategy below. For full code, go to https://github.com/rychien-official/payoff/blob/33b0c5b7ecde300dfb535e9e261a0f56b2ae4558/source.py#L103.

    # Solve ----------------------
    if verbose[0]==True:
        status = solver.NOT_SOLVED   # set status flag to not solved
        i = 1   # set index flag
        while status != solver.OPTIMAL:
            status = solver.Solve()   # query solver status
            wall_time = solver.wall_time()  # query current solver time
            if status in (solver.FEASIBLE, solver.OPTIMAL):
                interest_cost = \
                    solver.Objective().Value() - sum(principal_initial) - sum(
                        [remnant[i,t].solution_value()
                            for i in range(0, num_loans)
                            for t in range(0, term_months[i])])    # interest cost w/ optimal schedule
            else:
                interest_cost = "__not_solved__"
            print("Optimal solution is: $" + str(interest_cost) 
                + " after " + str(wall_time/1000) + " milliseconds.")
            i = i+1   # update flag
            solver.set_time_limit(time_limit_milliseconds * i)   # update time limit
    else:
        status = solver.Solve()

The full code results in:

>>> opt_pay_schedule()
Optimal solution is: $__not_solved__ after 0.125 milliseconds.
Optimal solution is: $__not_solved__ after 0.192 milliseconds.
Optimal solution is: $6059.492170638128 after 0.326 milliseconds.
Optimal solution is: $6055.741729656031 after 0.51 milliseconds.
Optimal solution is: $6055.741729656031 after 0.736 milliseconds.
Optimal solution is: $6055.741729656031 after 1.017 milliseconds.
Optimal solution is: $6055.741729656031 after 1.346 milliseconds.
Optimal solution is: $6055.741729656031 after 1.743 milliseconds.
Optimal solution is: $6055.741729656031 after 2.193 milliseconds.
Optimal solution is: $6055.741729656031 after 2.638 milliseconds.

Python 3.7.3 and Coin OR CBC.

BR,
Ryan

[JeroenGar]

Thanks for the responses! I'm using Java.

@Mizux I'll check if I can use the CP-SAT solver.

@rychien-official This could also be a good solution. Would there be a significant performance penalty if the search is interrupted every few seconds? Or does it restart the search every time?

[ryan-chien]

@JeroenGar there definitely is a performance penalty:

# Import
import sys
sys.path.append("C:/gitrepo/payoff/")
from source import *
import numpy as numpy
import timeit

def verbose_opt():
    opt_pay_schedule(verbose=[True, 50])

def silent_opt():
    opt_pay_schedule(verbose=[False, 50])

verbose_opt_time = timeit.timeit(verbose_opt, number=10)
print(verbose_opt_time)

silent_opt_time = timeit.timeit(silent_opt, number=10)
print(silent_opt_time)

We get these timings:

>>> verbose_opt_time
26.80526470000001
>>> silent_opt_time
5.457788499999992

So the verbose option with interrupts to get intermediate results is 5x slower, given interrupts every 50 milliseconds.

Perhaps the smarter strategy is to run a solve without interrupts first, query the total runtime, then set the interrupts based on that, to limit performance degredation. Maybe using a weighted time formula, such that we let the solver get _very close to optimal_ before starting to interrupt.

Run on a cheap laptop, Intel 7200u processor and 8gb ram.

Edit: I don't know if the solver starts the search from scratch every time.

[ryan-chien]

Based on the following math, I _interpret_ that the solver starts from scratch each time.

Given interrupts of 50 ms and 500ms for an optimal solve:
2750ms = 50+100+150+200+250+300+350+400+450+500

The above is approximately equal to 2.6 seconds, which over a sample of 10 runs would sum to approximately 26 seconds.

[JeroenGar]

@rychien-official
Thanks, but I think this approach is not ideal for my particular use-case since I'm dealing with models that often require a bit of time to solve.

@Mizux
I've modified the problem to use the CP-SAT solver and the callback functionality works flawless!