An issue for optmatch is how the various LEMON algorithms handle infeasible problems. As discussed in optmatch #216, it seems that the methods other than Cycle Cancelling report solutions to a modified problem when offered an infeasible one.
I see something lower down in the man pages to these functions that suggests they may each be reporting on feasiblity, but perhaps not in a place where we've been looking. The below is taken from the bottom of the CapacityScaling Class Template Reference, but an identical block also appears on the CycleCanceling Class Template Reference and the references for the other two. Does rlemon support extracting the INFEASIBLE field from the solved problem? If so, then we might use its value to decide whether the problem was feasible or not. (If infeasible, we might in the immediate term return NAs, for back-consistency. Later, once we've understood what's being returned by the algorithms that forge ahead in the face of infeasiblity, we might adjust this policy and in some cases report out a less ambitious match that the solver delivered for us.)
Member Enumeration Documentation
Enum type containing the problem type constants that can be returned by the run() function of the algorithm.
Enumerator
INFEASIBLE
The problem has no feasible solution (flow).
OPTIMAL
The problem has optimal solution (i.e. it is feasible and bounded), and the algorithm has found optimal flow and node potentials (primal and dual solutions).
UNBOUNDED
The digraph contains an arc of negative cost and infinite upper bound. It means that the objective function is unbounded on that arc, however, note that it could actually be bounded over the feasible flows, but this algroithm cannot handle these cases.
An issue for optmatch is how the various LEMON algorithms handle infeasible problems. As discussed in optmatch #216, it seems that the methods other than Cycle Cancelling report solutions to a modified problem when offered an infeasible one.
I see something lower down in the man pages to these functions that suggests they may each be reporting on feasiblity, but perhaps not in a place where we've been looking. The below is taken from the bottom of the CapacityScaling Class Template Reference, but an identical block also appears on the CycleCanceling Class Template Reference and the references for the other two. Does rlemon support extracting the
INFEASIBLEfield from the solved problem? If so, then we might use its value to decide whether the problem was feasible or not. (If infeasible, we might in the immediate term return NAs, for back-consistency. Later, once we've understood what's being returned by the algorithms that forge ahead in the face of infeasiblity, we might adjust this policy and in some cases report out a less ambitious match that the solver delivered for us.)Member Enumeration Documentation
Enum type containing the problem type constants that can be returned by the run() function of the algorithm.
The problem has no feasible solution (flow).
The problem has optimal solution (i.e. it is feasible and bounded), and the algorithm has found optimal flow and node potentials (primal and dual solutions).
The digraph contains an arc of negative cost and infinite upper bound. It means that the objective function is unbounded on that arc, however, note that it could actually be bounded over the feasible flows, but this algroithm cannot handle these cases.
I'd welcome anyone's thoughts on this, but wrote it with @josherrickson in mind.
Returning the status of the enum should be easy enough. @arav-agarwal2 or @atewari7, whenever you get a chance.
I've made a PR with what I think handles the changes, #26 . Once someone adds tests we can close the issue.