linear solver time limit

[Alberto Manzini]

Hi everyone, is there a way to set time limit in the solutions search for solver pywraplp.Solver.CBC_MIXED_INTEGER_PROGRAMMING or some other linear solvers?

Can i use these linear solvers also to search solutions iteratively, as it can be done with other non linear solver by the solver.NextSolution command?

Thanks,

    Alberto

[Laurent Perron]

LinearSolver::set_time_limit in C++

LinearSolver::SetTimeLimit in python. The argument is a int64 that represents ms.

Iterative: no. Few solvers support it natively. And we never wrote the glue code.

--
You received this message because you are subscribed to the Google Groups "or-tools-discuss" group.
To unsubscribe from this group and stop receiving emails from it, send an email to or-tools-discu...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Marianne Hoogeveen]

Dear Laurent,

I have a question about SetTimeLimit in pywraplp: are there any guarantees -assuming a feasible solution exists- that the solver outputs any solution? And that the solution is feasible?

Kind regards,

Marianne

[Laurent Perron]

Your question in ambiguous, assuming you find the feasible solution within the time limit, the yes the solver will output it,.

And for the second part, the linear solver (as the CP-SAT solver) always checks solution.

Laurent Perron | Operations Research | lpe...@google.com | (33) 1 42 68 53 00

[Marianne Hoogeveen]

What I meant was: if for some reason the solver takes longer than the set time even though there is a feasible solution, will it output some feasible solution that is not optimal?

[Laurent Perron]

When the solver stops, it outputs the best solution found so far.

--Laurent

[Marianne Hoogeveen]

Thanks, what I meant to ask was: are there any properties of the best solution that are guaranteed? Would it only output a solution that satisfied all constraints?

[Paul Trow]

If you're asking whether there is anything you can say about how close the best solution found by the time limit is to the optimal solution (as a ratio), the answer is no.

To put it another way, the LP algorithm starts at an initial solution, x_init, and ends at the optimal solution, x_opt, but it can take an arbitrarily long time to get there. Whatever time limit L you set, there is an LP problem for which the progress of the algorithm by time L can look like this (assuming it's a maximization problem):

x_init    x_best_sol_by_L                                                                                                                                                                                            x_opt      

                                                                                                                                                                                                          

Specifically, the ratio  of the distances (x_best_sol_by_L - x_init) / (x_opt - x_init)  can be arbitrarily close to 0.