Opened 13 years ago
Closed 12 years ago
#438 closed enhancement (fixed)
Optional iteration limit in HowardMmc
Reported by: | Peter Kovacs | Owned by: | Peter Kovacs |
---|---|---|---|
Priority: | major | Milestone: | LEMON 1.3 release |
Component: | core | Version: | hg main |
Keywords: | Cc: | ||
Revision id: |
Description
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.
Attachments (2)
Change History (11)
comment:1 Changed 13 years ago by
Status: | new → assigned |
---|
Changed 13 years ago by
Attachment: | 438-ee2fe24de015-howard-limit.patch added |
---|
comment:2 Changed 13 years ago by
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.
comment:3 Changed 12 years ago by
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.
comment:4 follow-up: 5 Changed 12 years ago by
- 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?
comment:5 follow-up: 6 Changed 12 years ago by
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:
- Merge these two functions as Alpar suggested and modify the enum type so that
NO_CYCLE==0
andOPTIMAL==1
hold. It would not brake the previous typical use cases of the function. - 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.
comment:6 follow-up: 7 Changed 12 years ago by
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 withbool
return type.)Two possible solutions:
- Merge these two functions as Alpar suggested and modify the enum type so that
NO_CYCLE==0
andOPTIMAL==1
hold. It would not brake the previous typical use cases of the function.- 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.
comment:7 Changed 12 years ago by
Replying to alpar:
I think, Option 1. is just perfect.
I attached a new patch file containing this solution. Thank you for the suggestion.
Changed 12 years ago by
Attachment: | 438-new-21a9f829ab68.patch added |
---|
comment:9 Changed 12 years ago by
Resolution: | → fixed |
---|---|
Status: | assigned → closed |
[21a9f829ab68] is merged to the main branch.
This ticket is actually a follow-up of the discussion in #436.