COIN-OR::LEMON - Graph Library

Opened 9 years ago

Closed 9 years ago

#314 closed enhancement (done)

Fractional matching and jumpstart initialization for general matchings

Reported by: Balazs Dezso Owned by: Balazs Dezso
Priority: major Milestone: LEMON 1.2 release
Component: core Version: hg main
Keywords: Cc:
Revision id:

Description

The fractional matching is a relaxed version of general matching algorithm if the odd set constraints are omitted from the LP formulation. It can be used to generate an initial solution of a general matching problem and in bipartite graphs it can calculate matchings directly.

Attachments (5)

0513ccfea967.patch (25.5 KB) - added by Balazs Dezso 9 years ago.
Improvements in matching.h
636dadefe1e6.patch (82.0 KB) - added by Balazs Dezso 9 years ago.
Fractional matching algorithms
61120524af27.patch (16.4 KB) - added by Balazs Dezso 9 years ago.
Jumpstart heuristic for fractional matching
86613aa28a0c.patch (4.2 KB) - added by Balazs Dezso 9 years ago.
Fix doc issues
41d7ac528c3a.patch (5.9 KB) - added by Balazs Dezso 9 years ago.
PrimalScale? = 2

Download all attachments as: .zip

Change History (14)

Changed 9 years ago by Balazs Dezso

Attachment: 0513ccfea967.patch added

Improvements in matching.h

Changed 9 years ago by Balazs Dezso

Attachment: 636dadefe1e6.patch added

Fractional matching algorithms

Changed 9 years ago by Balazs Dezso

Attachment: 61120524af27.patch added

Jumpstart heuristic for fractional matching

comment:1 Changed 9 years ago by Balazs Dezso

Status: newassigned

Three patches are uploaded (they can be applied sequentially):

  • The patch [0513ccfea967] contains minor changes in the matching.h.
  • The patch [636dadefe1e6] contains the fractional matching algorithms, especially one push-relabel max fractional matching algorithm and two max weighted matching algorithms (perfect and non-perfect).
  • The patch [61120524af27] integrates the fractional matching algorithms into the initial phase of the matching algorithms.

comment:2 Changed 9 years ago by Balazs Dezso

Milestone: LEMON 1.2 release

comment:3 in reply to:  1 ; Changed 9 years ago by Alpar Juttner

Replying to deba:

Three patches are uploaded (they can be applied sequentially):

Looking at the diff it is far from being minor. What does the sentence "The solved problems did not cause wrong solution." mean in the commit log?

comment:4 in reply to:  3 Changed 9 years ago by Balazs Dezso

Replying to alpar:

Replying to deba:

Three patches are uploaded (they can be applied sequentially):

Looking at the diff it is far from being minor. What does the sentence "The solved problems did not cause wrong solution." mean in the commit log?

The patch does not solve bug, it just improve and simplify the matching implementation.

comment:5 Changed 9 years ago by Alpar Juttner

The implementation is based on extensive use of priority queues and provides $O(nm\log n)$ time complexity.

This text appears both at the doc of the Edmonds weighted matching algs and also in the doc of fractional mathcing algs. I doubt it is correct at both places.

Also, a strange /// appears in the doc of the fractional matching algs.

Finally, the doc says

If the value type is integer, then the primal and the dual solutions are multiplied by 2 and 4 respectively.

Firstly, I guess it is in order to ensure that the solutions are also integer. However it makes the results a bit inconsistent. What about also multiplying the values in the floating point cases?

Secondly, the "4" in the text became a link somehow, which is quite strange.

Changed 9 years ago by Balazs Dezso

Attachment: 86613aa28a0c.patch added

Fix doc issues

comment:6 in reply to:  5 Changed 9 years ago by Balazs Dezso

Replying to alpar:

I have fixed some of the mentioned issues in [86613aa28a0c].

The implementation is based on extensive use of priority queues and provides $O(nm\log n)$ time complexity.

This text appears both at the doc of the Edmonds weighted matching algs and also in the doc of fractional mathcing algs. I doubt it is correct at both places.

Both algorithms are using priority queues, but maybe this is not so special for fractional matching algorithms.

Also, a strange /// appears in the doc of the fractional matching algs.

It is fixed.

Finally, the doc says

If the value type is integer, then the primal and the dual solutions are multiplied by 2 and 4 respectively.

Firstly, I guess it is in order to ensure that the solutions are also integer. However it makes the results a bit inconsistent. What about also multiplying the values in the floating point cases?

It can be a reasonable option.

Secondly, the "4" in the text became a link somehow, which is quite strange.

It is intended, but I wanted to make link also from 2. They must refer to the static const int members of primalScale and dualScale.

Changed 9 years ago by Balazs Dezso

Attachment: 41d7ac528c3a.patch added

comment:7 Changed 9 years ago by Balazs Dezso

The patch [41d7ac528c3a] change primalScale to 2 in every fractional matching algorithms.

comment:8 in reply to:  7 ; Changed 9 years ago by Alpar Juttner

Replying to deba:

The patch [41d7ac528c3a] change primalScale to 2 in every fractional matching algorithms.

Is there any reason why dualScale is still different for integer vs. floating point values?

comment:9 in reply to:  8 Changed 9 years ago by Alpar Juttner

Resolution: done
Status: assignedclosed

Replying to alpar:

Replying to deba:

The patch [41d7ac528c3a] change primalScale to 2 in every fractional matching algorithms.

Is there any reason why dualScale is still different for integer vs. floating point values?

Alas, we did the same in the matching classes (which have already been released in branch 1.1), thus we need it for the coherence with those classes.

As of [d8ea85825e02], all the changesets are in main brain.

Note: See TracTickets for help on using tickets.