  Like most multiobjective combinatorial optimization problems, biobjective
optimization problems on matroids are in general intractable and their
corresponding decision problems are in general NP-hard. In this paper, we
consider biobjective optimization problems on matroids where one of the
objective functions is restricted to binary cost coefficients. We show that in
this case the problem has a connected efficient set with respect to a natural
definition of a neighborhood structure and hence, can be solved efficiently
using a neighborhood search approach. This is, to the best of our knowledge,
the first non-trivial problem on matroids where connectedness of the efficient
set can be established.
  The theoretical results are validated by numerical experiments with
biobjective minimum spanning tree problems (graphic matroids) and with
biobjective knapsack problems with a cardinality constraint (uniform matroids).
In the context of the minimum spanning tree problem, coloring all edges with
cost 0 green and all edges with cost 1 red leads to an equivalent problem where
we want to simultaneously minimize one general objective and the number of red
edges (which defines the second objective) in a Pareto sense.
