Multi-objective matroid optimization with ordinal weights

DOI10.1016/J.DAM.2022.07.017zbMATH Open1519.90222arXiv2109.13804OpenAlexW3204440896MaRDI QIDQ6046136FDOQ6046136

Authors: Kathrin Klamroth, Michael Stiglmayr, Julia Sudhoff 

Publication date: 15 May 2023

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

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.

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

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

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)

Cites Work

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

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)