Add alternative sub problem extraction methods

[adam-douglass]

Add a method for extracting sub problems from the complete problem that is less sensitive to the current global state. In cases where the sub problem size is much smaller that the full problem the number of incoming edges can overwhelm the sub problem itself.

[bellert]

Email from Fred Glover to Mike Booth:

Mike,

Here's a thought about a possible way to refine the "partitioning with clamping" approach. As we discussed in our Zoom meeting (where I'll add a little notation to help make things clearer) we could keep an elite list for each variable x(j) of high impact cross product coefficients c(k,j) -- to identify associated high impact variables x(k) (dependent on x(j)) to pair with x(j). To be more precise, we choose a value h (such as h = 20) and then let N[j: h] = {k: c(k,j) is one of the h largest coefficients for x(j).} (I'm assuming we are maximizing, and that we restrict attention to positive coefficients in determining N[j: h].) Then the coefficient c(j) for x(j) is increased by the amount Sum(c(k,j): k lies in a different partition than j and k is in N[j: h]). As also mentioned in our discussion, we can optionally run Qbsolv multiple times with this approach, to generate multiple candidate "starting solutions" (since each run will identify different variables set to 1 and we can use these to produce different cross product terms to "turn on" to give new updated diagonal coefficients).

Now consider a refinement of the procedure of running Qbsolve multiple times, which takes effect after running it some initial number of times to generate a set of candidate solutions. Suppose we keep track of this candidate set of solutions, as we do with path relinking variants, and use the variables set to 1 in these solutions as a guide to creating a refined list of high impact cross product terms. Instead of evaluating impact just in terms of the size of the coefficients c(k,j), we can now identify high impact cross products for each variable x(j) based on how many times x(k) receives a value of 1 in the set of saved candidate solutions. (If x(k) equals 1 in all these candidate solutions we might just set it to 1 automatically for further runs of Qbsolv, unless the number of candidate solutions initially generated is not very large.)

This gives us a heuristic choice of a threshold value V for how many times x(k) = 1 should occur to qualify x(k) to be regarded as a high impact pair for other variables x(j). That is, we create a set N(V) = {k in N: x(k) = 1 in at least V of the candidate solutions}. Then the coefficient c(j) for x(j) is increased by Sum(c(k,j): k lies in a different partition than j and k is in N(V)). Or we may use a method that considers both the membership in N(V) and the size of the coefficients c(k,j) to create a set N(V: j) unique to each x(j) that is the intersection of N(V) and N[j: h]. In this case we may want to make h larger than in the initial determination of N[j: h]. Moreover, we may want to allow N[j: h] to include coefficients that are not positive. For instance, suppose we have a second larger V, call it V+, defined in the same way as N(V) to give N(V+) = {k in N: x(k) = 1 in at least V+ of the candidate solutions}. Then we can use a set for x(j) denoted by N(V, V+: j) equal to the union of N(V: j) and N(V+) (since there may be coefficients c(k,j) for j in N(V+) that are negative). (V+ doesn't necessarily have to be larger than V. It could be the same size or even smaller, all of which depends on how large V is chosen to begin with.)

I've probably made this sound more complicated than it should be. Anyway, I thought it might give you something you'd like to check out.

Fred