or-tools ResultStatus Question: ABNORMAL and NOT_SOLVED

[Polo]

Hi guys,

Could you help me understand in what circumstances or-tools solver would return ABNORMAL, and NOT_SOLVED?

Thanks a lot!

best,

Polo

[Mizux Seiha]

from ortools/linear_solver/linear_solver.proto i.e. https://github.com/google/or-tools/blob/b77bd3ac69b7f3bb02f55b7bab6cbb4bab3917f2/ortools/linear_solver/linear_solver.proto#L465-L540

// Status returned by the solver. They follow a hierarchical nomenclature, to

// allow us to add more enum values in the future. Clients should use

// InCategory() to match these enums, with the following C++ pseudo-code:

//

// bool InCategory(MPSolverResponseStatus status, MPSolverResponseStatus cat) {

//   if (cat == MPSOLVER_OPTIMAL) return status == MPSOLVER_OPTIMAL;

//   while (status > cat) status >>= 4;

//   return status == cat;

// }

enum MPSolverResponseStatus {

  // Normal responses -- the model was valid, and the solver ran.

  // These statuses should be "somewhat" repeatable, modulo the fact that the

  // solver's time limit makes it undeterministic, and could change a FEASIBLE

  // model to an OPTIMAL and vice-versa (the others, except NOT_SOLVED, should

  // normally be deterministic). Also, the solver libraries can be buggy.

  // The solver found the proven optimal solution. This is what should be

  // returned in most cases.

  //

  // WARNING: for historical reason, the value is zero, which means that this

  // value can't have any subcategories.

  MPSOLVER_OPTIMAL = 0x0;

  // The solver had enough time to find some solution that satisfies all

  // constraints, but it did not prove optimality (which means it may or may

  // not have reached the optimal).

  //

  // This can happen for large LP models (Linear Programming), and is a frequent

  // response for time-limited MIPs (Mixed Integer Programming). In the MIP

  // case, the difference between the solution 'objective_value' and

  // 'best_objective_bound' fields of the MPSolutionResponse will give an

  // indication of how far this solution is from the optimal one.

  MPSOLVER_FEASIBLE = 0x1;

  // The model does not have any solution, according to the solver (which

  // "proved" it, with the caveat that numerical proofs aren't actual proofs),

  // or based on trivial considerations (eg. a variable whose lower bound is

  // strictly greater than its upper bound).

  MPSOLVER_INFEASIBLE = 0x2;

  // There exist solutions that make the magnitude of the objective value

  // as large as wanted (i.e. -infinity (resp. +infinity) for a minimization

  // (resp. maximization) problem.

  MPSOLVER_UNBOUNDED = 0x3;

  // An error (most probably numerical) occurred.

  // One likely cause for such errors is a large numerical range among variable

  // coefficients (eg. 1e-16, 1e20), in which case one should try to shrink it.

  MPSOLVER_ABNORMAL = 0x4;

  // The solver did not have a chance to diagnose the model in one of the

  // categories above.

  MPSOLVER_NOT_SOLVED = 0x6;

[Polo]

Thank you so much Mizux! 

A follow-up question I have is do you (or anyone) know the difference between solver type SCIP_MIXED_INTEGER_PROGRAMMING and CBC_MIXED_INTEGER_PROGRAMMING in https://github.com/google/or-tools/blob/b77bd3ac69b7f3bb02f55b7bab6cbb4bab3917f2/ortools/linear_solver/linear_solver.proto#L406 ? Why is the recommended default for MIP problems, and what are the pros and cons when we compare SCIP_MIXED_INTEGER_PROGRAMMING with CBC_MIXED_INTEGER_PROGRAMMING?

Thanks again!

best,

Polo

[Laurent Perron]

SCIP is a much faster MIP solver. But it is not free for commercial use.

CBC can be very unreliable on some problems, but the license is permissive.

If your problem does not use continuous variables, I recommend using CP-SAT with 8 threads (or more).

--

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

--
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.
To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/80140e9d-e515-43fb-b6c0-b91d4730f996n%40googlegroups.com.

[Polo]

Thank you so much Laurent! Do I just change the solver to CP-SAT instead of CBC_MIXED_INTEGER_PROGRAMMING and then it would work? I have this question since I don't see CP-SAT in the list of enum SolverType {} in message MPModelRequest {} here: https://github.com/google/or-tools/blob/b77bd3ac69b7f3bb02f55b7bab6cbb4bab3917f2/ortools/linear_solver/linear_solver.proto#L389

Thanks again for your help!

best,

Polo

[Laurent Perron]

It is the sat integer programming flag.

To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/5a49a0db-1ee5-4c3c-9594-d3d8bccfa5c4n%40googlegroups.com.

[Polo]

Hi Laurent,

I am following up on the open-source solvers. Besides, SCIP and CBC, there is GLPK on the github page you shared with me earlier. How does GLPK compare to SCIP and CBC? And does it have permissible license like CBC which is free for commercial usage? 

Thank you so much for your help!

best,

Polo

[Laurent Perron]

Glpk is very bad. 

To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/1f84ecaa-a984-4335-869f-6e45058b7cc2n%40googlegroups.com.

[Polo]

Thanks! :D