In [1] a question was asked about a solve status in CVXR when we hit a time limit. Hopefully, we obtain the best solution found so far. But do we also get some indication about the status of this solution? CVXR only has the following status codes [2]:

status The status of the solution. Can be "optimal", "optimal_inaccurate", "infeasible", "infeasible_inaccurate", "unbounded", "unbounded_inaccurate", or "solver_error".

That looks wholly inadequate to properly describe this situation.

I tried a few scenarios for a MIP model.

- Optimal. There is no problem with this. I get:

> result$status

[1] "optimal" - Time limit, no integer solution found.

> result$status

[1] "unbounded"

This is somewhat of a surprise. Anyway, it is wrong. However, there is no good status that would describe this situation. - Time limit, integer solution found.

> result$status

[1] "optimal" "optimal_inaccurate"

Warning messages:

1: In if (solution[[STATUS]] %in% SOLUTION_PRESENT) { :

the condition has length > 1 and only the first element will be used

2: In if (status %in% SOLUTION_PRESENT) { :

the condition has length > 1 and only the first element will be used

3: In if (!(solution@status %in% SOLUTION_PRESENT)) return(Solution(solution@status, :

the condition has length > 1 and only the first element will be used

4: In if (solution@status %in% SOLUTION_PRESENT) { :

the condition has length > 1 and only the first element will be used

This is problematic. I see two status codes and none of them really covers this case. There are also a number of warning messages. This just looks like a bug.

Model Status | Solver Status | ||
---|---|---|---|

1 | OPTIMAL | 1 | NORMAL COMPLETION |

2 | LOCALLY OPTIMAL | 2 | ITERATION INTERRUPT |

3 | UNBOUNDED | 3 | RESOURCE INTERRUPT |

4 | INFEASIBLE | 4 | TERMINATED BY SOLVER |

5 | LOCALLY INFEASIBLE | 5 | EVALUATION INTERRUPT |

6 | INTERMEDIATE INFEASIBLE | 6 | CAPABILITY PROBLEMS |

7 | FEASIBLE SOLUTION | 7 | LICENSING PROBLEMS |

8 | INTEGER SOLUTION | 8 | USER INTERRUPT |

9 | INTERMEDIATE NON-INTEGER | 9 | ERROR SETUP FAILURE |

10 | INTEGER INFEASIBLE | 10 | ERROR SOLVER FAILURE |

12 | LIC PROBLEM - NO SOLUTION | 11 | ERROR INTERNAL SOLVER FAILURE |

13 | ERROR NO SOLUTION | 12 | SOLVE PROCESSING SKIPPED |

14 | NO SOLUTION RETURNED | 13 | ERROR SYSTEM FAILURE |

15 | SOLVED UNIQUE | ||

16 | SOLVED | ||

17 | SOLVED SINGULAR | ||

18 | UNBOUNDED - NO SOLUTION | ||

19 | INFEASIBLE - NO SOLUTION |

The total number of combinations is quite large. Of course, this still does not cover all possible return codes. A famously confusing return code is "Model is infeasible or unbounded" (Gurobi, without a solution). This cannot be mapped perfectly to any of these codes.

#### What can we expect in a MIP solver?

#### References

- CVXR in R: What happens when no solution is found within the time limit?, https://stackoverflow.com/questions/69982620/cvxr-in-r-what-happens-when-no-solution-is-found-within-the-time-limit
- Package CVXR, https://cran.r-project.org/web/packages/CVXR/CVXR.pdf

#### Appendix: model code

library(CVXR) installed_solvers() set.seed(1234) m <- 100 n <- 50 A <- matrix(runif(m*n,min=0,max=10),nrow=m,ncol=n) b <- runif(m,min=10,max=20) x <- Variable(n) r <- Variable(m) d <- Variable(n,boolean=T) k <- Parameter() obj <- Minimize(sum(abs(r))) constr <-list(A %*% x - b == r, x >= -d*1000, x <= d*1000, sum(d) == k) prob <- Problem(obj,constr) # find optimal solution value(k) <- 2 # easy problem result <- solve(prob, solver="GLPK", verbose=T) result$status # time limit before we have an integer solution value(k) <- 10 # difficult problem result <- solve(prob, solver="GLPK", verbose=T, tm_limit = 1) result$status # find integer solution (non-optimal) result <- solve(prob, solver="GLPK", verbose=T, tm_limit = 1000) result$status

This is unfortunately a known issue in the CVX family (had the same problem with CVXPY); not sure why that is. Maybe a pull request is due.

ReplyDelete