JuliaGraphs / JuliaGraphs/GraphsMatching.jl

[BUG] different JuMP optimizers give different results in `maximum_weight_matching`

Open
#24 0 comments 0 reactions 1 assignee View on GitHub

@Krastanov is already working on this.

Since Jul 14, 2025.

bug
Dominant language
Julia
Stars
20
Forks
8
Avg merge
9h 15m
Merged PRs (30d)
1

Description

Description of bug

In edge cases with poorly defined matching problems (e.g. empty graphs), JuMP behaves differently depending on the solver being used, leading to unhelpful errors instead of returning an empty matching.

How to reproduce

using Graphs
using GraphsMatching
using JuMP: optimizer_with_attributes, MOI
using HiGHS: HiGHS
using Cbc: Cbc
# try either one of these two
opt = optimizer_with_attributes(HiGHS.Optimizer, MOI.Silent() => true)
opt = optimizer_with_attributes(Cbc.Optimizer, MOI.Silent() => true)
g = SimpleGraph{Int64}(0, [Int64[]])
w = [0;;]
maximum_weight_matching(g,opt,w)

Expected behavior

Return an empty matching.

Actual behavior

For some optimizers, an error is raised.

Contributor guide

No contributing guide indexed for this repository

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.