Optional iteration limit in HowardMmc

[Peter Kovacs]

Howard's algorithm performs several iterations that successively approximates the minimum cycle mean. After a finite number of iterations, the algorithm finds the optimal solution. It is quite efficient in practice, but no polynomial bound is known for the number of iterations.

Therefore, it seems to be practical if an optional limit for the number of iterations could be passed to the algorithm.

[Peter Kovacs]

This ticket is actually a follow-up of the discussion in #436.

[Peter Kovacs]

The attached patch [ee2fe24de015] adds this new option to HowardMmc. The current API is not modified (of course), only a new overloaded version of the findCycleMean() function is added that takes an int parameter (iteration limit). The old version calls this new function without iteration limit (-1). The corresponding test file is also extended with a simple test case for correct termination causes.

An important use case of this enhancement is discussed in #436. Moreover, it allows the usage of the algorithm as a quick heuristic/approximation method.

[Alpar Juttner]

Why not use std::numeric_limits<int>::max() instead of -1? The declaration of findCycleMean() could simply be

TerminationCause findCycleMean(int limit = std::numeric_limits<int>::max())

Besides, the different return values (type and semantic) of the two overloaded versions of findCycleMean() seems very odd to me.

[Balazs Dezso]

• I agree with Alpar, that overloading a function with different return is not a good idea.
• If we have more components and iteration limit, is it a good idea to process the components in the predefined order?

[Peter Kovacs]

Replying to deba:

• I agree with Alpar, that overloading a function with different return is not a good idea.

I also agree. However, I thought that it is more problematic to change the return type of an exisiting function than introducing an overloaded version with different return type. (Note that the other two MMC algorithms also have a findCycleMean() function with bool return type.)

Two possible solutions:

1. Merge these two functions as Alpar suggested and modify the enum type so that NO_CYCLE==0 and OPTIMAL==1 hold. It would not brake the previous typical use cases of the function.
2. Rename the new function to avoid overloading with different return type.

What do you think? Would the first one be suitable? Could you suggest a better solution?

• If we have more components and iteration limit, is it a good idea to process the components in the predefined order?

I have no idea to predict a good processing order of the components. In fact, such a strategy can be introduced later without changing the API.

[Alpar Juttner]

Replying to kpeter:

Replying to deba:

• I agree with Alpar, that overloading a function with different return is not a good idea.

I also agree. However, I thought that it is more problematic to change the return type of an exisiting function than introducing an overloaded version with different return type. (Note that the other two MMC algorithms also have a findCycleMean() function with bool return type.)

Two possible solutions:

1. Merge these two functions as Alpar suggested and modify the enum type so that NO_CYCLE==0 and OPTIMAL==1 hold. It would not brake the previous typical use cases of the function.
2. Rename the new function to avoid overloading with different return type.

What do you think? Would the first one be suitable? Could you suggest a better solution?

I think, Option 1. is just perfect.

[Peter Kovacs]

Replying to alpar:

I think, Option 1. is just perfect.

I attached a new patch file containing this solution. Thank you for the suggestion.

[Peter Kovacs]

The new patch is [21a9f829ab68].

[Alpar Juttner]

[21a9f829ab68] is merged to the main branch.