Fenchel-type duality for matroid valuations

The weighted matroid intersection problem has recently been extended to the valuated matroid intersection problem: Given a pair of valuated matroids Mi = (V, ℬi, ωi) (i = 1,2) defined on a common ground set V, find a common base B ∈ ℬ1 ∩ ℬ2 that maximizes ω1(B) + ω2(B). This paper develops a Fenchel-type duality theory related to this problem with a view to establishing a convexity framework for nonlinear integer programming. A Fenchel-type min–max theorem and a discrete separation theorem are given. Furthermore, the subdifferentials of matroid valuations are investigated.