5
$\begingroup$

Is there a way to make Gurobi output (an estimate of) how much of the search space has already been cut off as infeasible?

If not with Gurobi are you aware of any binary only (912 of them) ILP solver that does provide that information?

I suspect the problem i have is infeasible and i would like to get an idea how much progress has been made or ideally an estimate how much time remaining until infeasibility is proven (which should be quiet predictable unless terminating earlier in case of stumbling into a feasible solution).

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ I don't have a direct answer to your question. But I'm not sure that "progress" is a meaningful concept in this context, in the sense that model size is a poor predictor of solution time. Even cutting off part of the solution space doesn't necessarily speed up the process - e.g. I recently worked on a model where adding some cutting plane constraints increased the solution time in most cases. $\endgroup$
    – Solver Max
    Nov 17, 2021 at 0:17
  • $\begingroup$ @worldsmithhelper, some of the solver's pre-solving methods, by emphasizing, might detect infeasibility before running the B&B process. $\endgroup$
    – A.Omidi
    Nov 17, 2021 at 8:13
  • $\begingroup$ Something like this? youtube.com/watch?v=KHOsGfSOBuc doi.org/10.1609/aaai.v33i01.33011427 $\endgroup$
    – fontanf
    Nov 17, 2021 at 8:20
  • $\begingroup$ @fontanf Yes that looks good although some metrics introduced behave pathological incase of feasibility. For my usecase even an sum of infeasible 2^(912-binaries assigned when detected infeasibility) /2^912 would be be helpful. I guess SCIP and FICE XPRESS provide some estimates but they tend to perform worse on infeasible problems. I hoped i missed something in the Gurobi documentation. $\endgroup$
    – worldsmithhelper
    Nov 17, 2021 at 10:36
  • $\begingroup$ @SolverMax In case of infeasible problems you are mathematically wrong. When "proving" infeasibility the only way to make progress is cutting of search space. $\endgroup$
    – worldsmithhelper
    Nov 17, 2021 at 10:43

1 Answer 1

Reset to default
1
$\begingroup$

I would expect the measure of Xpress (and SCIP) to work reasonably well for infeasible problems. They take into account at which levels nodes have been pruned during search and that directly relates to the search space size.

For a feasibility problem, where finding a solution can terminate the whole search at any time, this is different, of course.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.