Improving Hinting (Documentation)

[adamrauh]

This issue is intended to document some recent work on the nodeprices branch in this fork of the package.

Summary

The most recent batch of commits, concluding with this attempts move the needle on improving functionality around providing hints. Specifically, they contain some updates to how feasibility is tracked and returned to users. These updates, as they stand, should be seen as experimental and a work in progress for reasons detailed below. These updates are primarily targeted at this issue on the main repo.

I should note that these changes do not explicitly address the linked issue, but upon resolving the issues of these updates, a fix to subproblemSuccess() should become trivial. As of now, the current version of the nodeprices branch also passes existing tests.

Major features of these updates

This round of updates offers the following set of features

1. Explicit tracking of subproblem feasibility. That is, there is always a subproblems table and it always returns TRUE or FALSE regarding feasibility. This subproblems table should be reliable, even in the code's current form. One other selling point here is that feasibility is now set only within fmatch.R and not higher up the stack anywhere.
2. fullmatch() and pairmatch() always return and MCFSolutions attribute with reliable information about subproblem feasibility.

Issues with these updates

Prior code had a multi-pronged approach for dealing with feasibility. Specified subproblems could be either 1) feasible 2) infeasible and never handed to the solver or 3) infeasible but passed to the solver. If a subproblem fell into (1) or (3), an MCFSolutions object was passed back to the end user. If it fell into (2), there was not. As such, checking feasibility using just this metadata required checking the existence of an MCFSolutions object, as well as explicitly checking the subproblems table if it did exist.

I opted to try implementing a UI where an MCFSolutions object is always returned with a result and where feasibility is always explicitly listed in the subproblems table. The logic here was to streamline the internal logic about feasibility and the UI -- no broader wisdom at work here.

It turns out that explicitly returning an MCFSolutions raises some questions and problems that I've only hastily papered over here. A (likely incomplete) list of some things to be dealt with:

1. It's unclear if there should be any difference between subproblems that are determined to be infeasible prior to being passed to the solver and infeasible problems that are determined to be so by the solver. For one, subproblems in the former camp might be ill-specified to the point of not being able to create a sensible MCFSolutions object. As an example, what should be done if a subproblem with no viable treatment or control units is passed? More generally, should nodes/arc/bookkeeping always be returned when the subproblem is infeasible?

2. It's possible that existing constructors/class definitions will need to be updated to deal with the implications of (1). For instance, in certain cases, I've opted to set both flow and capacity to 0 when the subproblem is infeasible in order to please the class-checking standards. Another example: MCFSolutions objects that only contain a filled out subproblems table seem to break at the concatenation stage. For now, I've used workarounds to please the existing class definitions/constructors, but some of these choices might not make substantive sense. For instance, Including nonsensical arcs from end and sink nodes to themselves in the "bookkeeping" table when subproblems are empty. While the subproblems table can be trusted, the other slots currently cannot be (unless the problem is feasible).

Instances of where 1 and 2 are relevant should be documented with comments in the code, primarily in fmatch.R, solve_reg_fm_prob.R and fullmatch.R

In short, we need to think through what to return -- either as an MCFSolutions object or something similar -- when problems are infeasible.

[benthestatistician]

0. Thanks for this excellent progress, and for this nice summary of where things now stand! (I take it that the summary refers to the current state of the local nodeprices branch -- pls correct if this is mistaken.)
1. In fmatch(), some nonsensical inputs provoke a stop(), whereas others lead to the function returning an object encoding the absence of matches. In specific cases we can consider stop-ing rather than returning an NA match, but we should be loathe to do this in cases where it will indirectly lessen the user experience.
2. Instead, let's be open to adjusting the validity checkers. For instance, in the case of a subproblem with no treatments or no controls, perhaps the validity checker should allow us to pass back @arcinfo@matches and @arcinfo@bookkeeping tables that have no rows, consisting of just 0-length factors bearing levels as called for in the MCFSolutions vignette (and integer(0)'s in the case of @arcinfo@bookkeeping). I'd think that the @nodeinfo table should have rows, as the MCFSolutions vignette indirectly stipulates by saying that its row names attrribute should be non-null. In general I'd follow that spec vignette over the validity checkers when trying to decide what the rules ought to be. The MCFSolutions spec is also negotiable, if need be.

Other:

• I'd suggest keeping line widths for inline comments to around 80, ie breaking them up with EOL's then or sooner. (Here and elsewhere there are currently comments to going out nearly 800 chars, making them difficult to read on GH.)
• How about we use this thread to discuss additional specific problem cases?

[benthestatistician]

More detailed comments, around the theme of handling infeasible subproblems.

1. Currently the feasible column of a SubProbInfo is Boolean, but I'm thinking it should be factor instead. Then we can define levels distinguishing scenarios where infeasibility was decided by the solver vs discovered even before that. There may also eventually be different flavors of solver-determined infeasibility. We might call this new column "feasibility" rather than "feasible". Its levels might be:

   • "infeas_prob_spec";
   • "infeas_per_<...>", where "<...>" is the value returned by optmatch:::handleSolver(), e.g. "RELAX-IV" or "LEMON.CycleCancelling"; and
   • "feasible".

   Note that this calls for us to keep maintain a list of permissible values for this field, keeping it up-to-date with whatever solver options the package is currently offering. I'd propose to do this by exploring the range of values that optmatch:::handleSolver() can return, with both rrelaxiv and rlemon loaded and excessible, then
   a. Hard-coding it into our SubProbInfo makers and validity checkers;
   b. Adding tests to the package that aim to check that these are all and only the values that handleSolver() returns. (So that when we add solver functionality and forget to update the SubProbInfo maker, we get warned once we start testing stuff.)
   Let's add a "solver" column (character) to the SubProbInfo table, retaining the structure as it exists otherwise. If the problem was found infeasible before be passed to a solver, this is a ""; otherwise, it records the value optmatch::handleSolver() will have returned.

2. When a subproblem is passed to the solver and found infeasible, what to store? I say:

   • SubProbInfo: There should be groups, flipped, hashed_dist and feasible/feasibility values as otherwise. Each of resolution, primal_value, dual_value and exceedance should each have a value: the value returned by the solver, if the solver was called and returned a value; NA_real_ otherwise.
   • NodeInfo: Let's return a full table here. The mix of meaningful node names and meaningless supplies and prices that node_shell_fmatch() generates, if that's the best we've got; but more if we have it.
     If a solver was called, then we should also pass back meaningful supply values, namely those that were given to the solver.
     Some solvers will return node prices for infeasible problems whereas others won't; if we get them, let's return them. If no node prices were returned, let's put 0s in the price column, not NAs.
   • ArcInfo@matches, ArcInfo@bookkeeping: These can be data frames with no rows. Their length-0 columns can still observe the rules for them (about type and level sets) set out in MCFSolutions.Rmd. (Including "The @bookkeeping d.f. must have a row for each of the bookkeeping arcs of the problem": If the problem wasn't feasible, then the problem solution has no bookkeeping arcs.)

[adamrauh]

(Documenting some updates and questions here, as it is relevant to the above thread, as well as multiple issues on the original repository -- I'll try to cross link everything.)

Some updates

As of the commit 3fcbaa4, we have a mix of features in working order in the nodeprices branch:

1. An MCFSolutions object with at least some useful information is always returned from a call to pairmatch() or fullmatch(). The implementation mirrors pretty much exactly what was discussed above.

An MCFSolutions object is always returned. Users can rely on subproblem and node price information being returned via the "subproblems" and "nodes" slots, respectively. This information is always present, regardless of feasibility. Information in the "nodes" slot is returned to the best of the program's ability. If a subproblem is feasible, then the results of that computation are returned. If the subproblem is infeasible, then there are two possibilities for what gets returned as one might expect. If the subproblem was determined to be infeasible before being passed to the solver, then the results from node_shell_fmatch() are returned. If the subproblem is passed to the solver, then the results from the solver are returned. Data from the subproblems slot can be extracted via a new function get_subproblem_info(). That function has documentation and basic tests, but things are also laid out with examples in the MCFSolutions.Rmd vignette here: 3fcbaa4.

2. Users can specify subproblem level resolution values to pairmatch() and fullmatch() to get passed down to the solver. I've updated the documentation for these functions to describe the relevant resolution argument and included some basic tests for this functionality. Examples can also be found in the MCFSolutions.Rmd vignette. I do have some lingering questions, but I will mark those below.

3. I've added documentation for the hint argument in pairmatch() and fullmatch(), in an attempt to daylight this functionality as described in issue 76.

4. Just noting that the potentially relevant updates in this issue are not in this nodeprices branch at all.

So, what needs to be done?

I think (1) is more or less "done" for now. I'm fairly happy with the implementation -- no existing current rules or expectations were broken, so nothing to retrofit or patch there. There are some bare bones tests here and documentation in the vignette, as mentioned above. Of course, these things can be fleshed out more, but I have no tangible to-dos on it aside from that.

I think (2) is also in fairly good shape, but I'd like to understand more about what the broader use case is. I think we had discussed that this functionality would likely be used by fairly sophisticated optmatch users, but I don't have a great grasp over what those use cases might be. What do we anticipate a workflow for a user leveraging this feature to look like? I suspect some additional testing and refinement will be needed to bring things into alignment with that vision. But, as it stands, the functionality seems to work nicely.

On (3), I think issue 76 can be checked off soon, with some additional clarifications and polish. Regarding the to-dos laid out there:

• daylight arguments to fullmatch()/pairmatch() that would be used to pass the hints.

I've added some documentation about the hint argument, as well as examples in the vignette, as described above. Is the MCFSolutions vignette an appropriate place for these examples? Or should that be put elsewhere?

• clarify wherever appropriate that this requires the relax solver

Is this still true? Hints are accepted using LEMON (at least for me), but the comment here suggests that maybe only RELAX is relevant?

• (Do we have checks that the hint MCFSolutions has the same subproblems structure as the current problem?)

My look appears to suggest yes. If the subproblem structure is different, the hint gets ignored. I added an explicit test for this below. So, I think we're good here.

• add tests of user-level functionality

This appears to exist -- I made one minor addition to this test, but I'm seeing relevant tests for fullmatch() and pairmatch(). I think this is also set.

• add examples

Same question as above -- where's a good spot for this aside from MCFSolutions.Rmd?

Question: Do we need to dissuade users from changing fullmatch arguments other than the tolerance? Or is it just as well to let them change whatever, as long as we can retrieve a node price for each of the relevant arguments?

I have the same question... From a technical standpoint, the code seems to run if different arguments are changed, but I'm not sure that this is desirable.

(4) could be similarly close to close-out, depending on priorities. The solution outlined there isn't particularly sophisticated or future proofed, but it does do the job of storing node prices and tracking subproblem IDs. I think I'd like to better understand the use case for these features before closing it out.

[benthestatistician]

Thanks for the overview of these nice contributions, Adam!

1.

Where to put the relevant examples? I put some in MCFSolutions.Rmd, but I'm not sure if that's the best place.

-- It would be great to have an example or two in each of inst/examples/fullmatch.R and inst/examples/pairmatch.R.

2.

Are these changes still only relevant to RELAX?

-- If the LEMON solver appears to be taking hints, then no it's relevant to them too. No need to state a restriction to RELAX-IV that I can see.

3.

Question: Do we need to dissuade users from changing fullmatch arguments other than the tolerance? Or is it just as well to let them change whatever, as long as we can retrieve a node price for each of the relevant arguments?
I have the same question... From a technical standpoint, the code seems to run if different arguments are changed, but I'm not sure that this is desirable.

-- I do not currently think we need to dissuade users from changing other fullmatch args when passing a hint.

(4) could be similarly close to close-out, depending on priorities. The solution outlined markmfredrickson#161 isn't particularly sophisticated or future proofed, but it does do the job of storing node prices and tracking subproblem IDs. I think I'd like to better understand the use case for these features before closing it out.

If these changes are currently in this fork, leave 'em in for the pull request and see what the rest of us have to say. I wouldn't be surprised if that turns out to be closer to ready to go than you think. If they're elsewhere, then maybe it's as well to give us a PR of the remaining material first, then follow up with that stuff. (Either later on the same PR after a round or so of review and adjustment, or in a new PR.). Out of curiosity, are the remaining optmatch#161 to-do's just the ones discussed in this comment of yours from back in June?

Next steps are for me & perhaps other optmatch people to take a closer look. I.e., it'll soon be time for a PR. (Exciting!)

[adamrauh]

Thanks for sifting through this!

I added some examples to the locations you mentioned (inst/examples/). Given your other answers, I don't think I have any additional changes in mind for closing out issue 76 -- perhaps just giving things a general once-over. Things seem in alignment!

Out of curiosity, are the remaining optmatch#161 to-do's just the ones discussed in markmfredrickson#161 (comment) of yours from back in June?

Yep, I think that is right. Those changes are not in this fork, but are relatively siloed and small, so a future merge shouldn't be too painful.

Let me know if I should issue a PR for the stuff related to 76 (or whatever the best way is to move that forward)!

[benthestatistician]

Thanks for adding those examples, Adam. With that, I think that it's high time for a PR!

But rather than requesting pull into the master branch, could you request it into the proj1-nodeprices branch? This will call for a first merging/reconciling changes on that branch, one of which I only just now found and pushed up from a local remote. Come to think of it, perhaps first it should be checked that tests are passing on the current version of that branch, something I have yet to look into. So, if you're willing to check on that, please do so, merge the resulting proj1-nodeprices material up into your fork, and then post a PR for your fork to come into proj1-nodeprices on the base optmatch repo. (If that's too much to take on right now, I can put checking and touching up the proj1-nodeprices branch back into my queue.)

[adamrauh]

Sounds good! I was able to merge proj1-nodeprices with the forked nodeprices fairly easily. Everything should be in the nodeprices branch now and pushed up to the repo here.

On my end, devtools::test() looks to pass without any errors. This includes any of the new tests I've put in over the past few months. Are there other tests to throw at it before issuing the PR?

[benthestatistician]

That's all I meant to ask for in the way of tests, thanks! It's finally time for that PR! (At your convenience.)

[adamrauh]

I realized that we may now be in a position to also check off issue 178 with the new guarantees about MCFSolutions objects. I'll give that a go and if the change is straightforward, I'll issue the PR then!