COIN-OR::LEMON - Graph Library

Opened 8 years ago

Closed 7 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)

438-ee2fe24de015-howard-limit.patch (4.4 KB) - added by Peter Kovacs 8 years ago.
438-new-21a9f829ab68.patch (4.5 KB) - added by Peter Kovacs 7 years ago.

Download all attachments as: .zip

Change History (11)

comment:1 Changed 8 years ago by Peter Kovacs

Status: newassigned

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

Changed 8 years ago by Peter Kovacs

comment:2 Changed 8 years ago by 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.

comment:3 Changed 7 years ago by 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.

comment:4 Changed 7 years ago by 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?

comment:5 in reply to:  4 ; Changed 7 years ago by 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.

comment:6 in reply to:  5 ; Changed 7 years ago by 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.

comment:7 in reply to:  6 Changed 7 years ago by 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.

Changed 7 years ago by Peter Kovacs

Attachment: 438-new-21a9f829ab68.patch added

comment:8 Changed 7 years ago by Peter Kovacs

The new patch is [21a9f829ab68].

comment:9 Changed 7 years ago by Alpar Juttner

Resolution: fixed
Status: assignedclosed

[21a9f829ab68] is merged to the main branch.

Note: See TracTickets for help on using tickets.