Multi-objective matroid optimization with ordinal weights

DOI10.1016/J.DAM.2022.07.017MaRDI QIDQ6046136zbMATH OpenOpenAlexFDO

Authors Kathrin Klamroth, Michael Stiglmayr, Julia Sudhoff

Publication date 15 May 2023

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2109.13804

zbMATH Keywords

matroid intersectionmulti-objective combinatorial optimizationmulti-objective minimum spanning treeordinal weights

Mathematics Subject Classification ID

Multi-objective and goal programming (90C29) Combinatorial optimization (90C27)

Abstract: Bi-objective optimization problems on matroids are in general intractable and their corresponding decision problems are in general NP-hard. However, if one of the objective functions is restricted to binary cost coefficients the problem becomes efficiently solvable by an exhaustive swap algorithm. Binary cost coefficients often represent two categories and are thus a special case of ordinal coefficients that are in general non-additive. In this paper we consider ordinal objective functions with more than two categories in the context of matroid optimization. We introduce several problem variants that can be distinguished w.r.t. their respective optimization goals, analyze their interrelations, and derive a polynomial time solution method that is based on the repeated solution of matroid intersection problems. Numerical tests on minimum spanning tree problems and on partition matroids confirm the efficiency of the approach.

Recommendations

• On matroids with multiple objectives
• Maximizing Classes of Two-Parameter Objectives Over Matroids
• Optimal matroid partitioning problems
• Optimal matroid partitioning problems
• On a discrete optimization problem

Cites work

• scientific article; zbMATH DE number 3862930 (Why is no real title available?)
• scientific article; zbMATH DE number 1953186 (Why is no real title available?)
• scientific article; zbMATH DE number 5873618 (Why is no real title available?)
• scientific article; zbMATH DE number 3249395 (Why is no real title available?)
• A GRASP algorithm for the multi-criteria minimum spanning tree problem
• A local analysis to determine all optimal solutions of \(p\)-\(k\)-\(\max\) location problems on networks
• A survey and annotated bibliography of multiobjective combinatorial optimization
• A weighted matroid intersection algorithm
• Connectedness of efficient solutions in multiple criteria combinatorial optimization
• Efficient algorithms for a family of matroid intersection problems
• Matroids and the greedy algorithm
• Multicriteria Optimization
• Multiple objective optimization and implications for single objective optimization.
• Network flows. Theory, algorithms, and applications.
• On matroids with multiple objectives
• On spanning tree problems with multiple objectives
• Shortest paths with ordinal weights
• The binary knapsack problem with qualitative levels
• The multi-criteria minimum spanning tree problem based genetic algorithm
• Two algorithms for weighted matroid intersection

Cited in

(3)

• Computation in multicriteria matroid optimization
• Ordinal optimization through multi-objective reformulation
• Biobjective optimization problems on matroids with binary costs

This page was built for publication: Multi-objective matroid optimization with ordinal weights

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6046136)