Biobjective optimization problems on matroids with binary costs
From MaRDI portal
Publication:6132760
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.
Recommendations
Cites work
- scientific article; zbMATH DE number 420868 (Why is no real title available?)
- scientific article; zbMATH DE number 3961631 (Why is no real title available?)
- scientific article; zbMATH DE number 4010155 (Why is no real title available?)
- scientific article; zbMATH DE number 1423920 (Why is no real title available?)
- A Survey on Multiple Objective Minimum Spanning Tree Problems
- A local analysis to determine all optimal solutions of \(p\)-\(k\)-\(\max\) location problems on networks
- A matroid algorithm and its application to the efficient solution of two optimization problems on graphs
- A multiply constrained matroid optimization problem
- Bioinspired computation in combinatorial optimization. Algorithms and their computational complexity
- Color constrained combinatorial optimization problems
- Comments on bases in dependence structures
- Computation in multicriteria matroid optimization
- Connectedness of efficient solutions in multiple objective combinatorial optimization
- Efficient algorithms for a family of matroid intersection problems
- Empirical study of exact algorithms for the multi-objective spanning tree
- Genetic algorithm approach on multi-criteria minimum spanning tree problem
- Laplacian matrices of graphs: A survey
- Matroid optimization with generalized constraints
- Matroid optimization with the interleaving of two ordered sets
- Multicriteria Optimization
- Multiple objective optimization and implications for single objective optimization.
- New approaches to multi-objective optimization
- Nonlinear multiobjective optimization
- On \(k\)-Max-optimization
- On matroids with multiple objectives
- On possibly optimal tradeoffs in multicriteria spanning tree problems
- On spanning tree problems with multiple objectives
- On the bicriterion - minimal cost/minimal label - spanning tree problem
- The minimum labeling spanning trees
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)
