Biobjective optimization problems on matroids with binary costs
From MaRDI portal
Publication:6132760
DOI10.1080/02331934.2022.2044479arXiv2108.00709OpenAlexW3188085113MaRDI QIDQ6132760FDOQ6132760
Authors: Jochen Gorski, Kathrin Klamroth, Julia Sudhoff 
Publication date: 14 July 2023
Published in: Optimization (Search for Journal in Brave)
Abstract: 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.
Full work available at URL: https://arxiv.org/abs/2108.00709
Recommendations
Cites Work
- Nonlinear multiobjective optimization
- Title not available (Why is that?)
- Multicriteria Optimization
- Laplacian matrices of graphs: A survey
- Title not available (Why is that?)
- Title not available (Why is that?)
- Bioinspired computation in combinatorial optimization. Algorithms and their computational complexity
- On spanning tree problems with multiple objectives
- The minimum labeling spanning trees
- Efficient algorithms for a family of matroid intersection problems
- On the bicriterion - minimal cost/minimal label - spanning tree problem
- Connectedness of efficient solutions in multiple objective combinatorial optimization
- New approaches to multi-objective optimization
- A matroid algorithm and its application to the efficient solution of two optimization problems on graphs
- Genetic algorithm approach on multi-criteria minimum spanning tree problem
- On \(k\)-Max-optimization
- Color constrained combinatorial optimization problems
- On matroids with multiple objectives
- Comments on bases in dependence structures
- Multiple objective optimization and implications for single objective optimization.
- On possibly optimal tradeoffs in multicriteria spanning tree problems
- A local analysis to determine all optimal solutions of \(p\)-\(k\)-\(\max\) location problems on networks
- Title not available (Why is that?)
- Computation in multicriteria matroid optimization
- Matroid optimization with the interleaving of two ordered sets
- A Survey on Multiple Objective Minimum Spanning Tree Problems
- A multiply constrained matroid optimization problem
- Matroid optimization with generalized constraints
- Empirical study of exact algorithms for the multi-objective spanning tree
Cited In (3)
This page was built for publication: Biobjective optimization problems on matroids with binary costs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6132760)
