Exact algorithms for OWA-optimization in multiobjective spanning tree problems
From MaRDI portal
Abstract: This paper deals with the multiobjective version of the optimal spanning tree problem. More precisely, we are interested in determining the optimal spanning tree according to an Ordered Weighted Average (OWA) of its objective values. We first show that the problem is weakly NP-hard. In the case where the weights of the OWA are strictly decreasing, we then propose a mixed integer programming formulation, and provide dedicated optimality conditions yielding an important reduction of the size of the program. Next, we present two bounds that can be used to prune subspaces of solutions either in a shaving phase or in a branch and bound procedure. The validity of these bounds does not depend on specific properties of the weights (apart from non-negativity). All these exact resolution algorithms are compared on the basis of numerical experiments, according to their respective validity scopes.
Recommendations
Cites work
- scientific article; zbMATH DE number 3936534 (Why is no real title available?)
- scientific article; zbMATH DE number 3679573 (Why is no real title available?)
- scientific article; zbMATH DE number 3694968 (Why is no real title available?)
- scientific article; zbMATH DE number 795222 (Why is no real title available?)
- scientific article; zbMATH DE number 1394671 (Why is no real title available?)
- scientific article; zbMATH DE number 3894826 (Why is no real title available?)
- A branch and bound algorithm for Choquet optimization in multicriteria problems
- A decision-theoretic approach to robust optimization in multivalued graphs
- A flexible model and efficient solution strategies for discrete location problems
- A fully polynomial bicriteria approximation scheme for the constrained spanning tree problem.
- A multiobjective branch-and-bound framework: application to the biobjective spanning tree problem
- A new approach to computing optimal schedules for the job-shop scheduling problem
- A survey and annotated bibliography of multiobjective combinatorial optimization
- An Algorithm for Finding K Minimum Spanning Trees
- An implementation of Shor's \(r\)-algorithm
- Approximating Min-Max (Regret) Versions of Some Polynomial Problems
- Approximation of min-max and min-max regret versions of some combinatorial optimization problems
- Approximative solution methods for multiobjective combinatorial optimization. With discussion and a rejoinder by the authors.
- Beyond preference information based multiple criteria decision making
- Computing all efficient solutions of the biobjective minimum spanning tree problem
- Exact procedures for solving the discrete ordered median problem
- Inequality measures and equitable approaches to location problems
- Integral Representation Without Additivity
- Location theory. A unified approach
- Min-max and min-max regret versions of combinatorial optimization problems: A survey
- Min-max optimization of several classical discrete optimization problems
- Minimizing the sum of the \(k\) largest functions in linear time.
- Minmax combinatorial optimization
- Multicriteria Optimization
- Multicriteria planar ordered median problems
- On bicriterion minimal spanning trees: An approximation
- On efficient WOWA optimization for decision support under risk
- On ordered weighted averaging aggregation operators in multicriteria decisionmaking
- On solving linear programs with the ordered weighted averaging objective.
- On spanning tree problems with multiple objectives
- Properties of thek-centra in a tree network
- Robust discrete optimization and its applications
- Solving biobjective combinatorial max-ordering problems by ranking methods and a two-phases approach
- Subjective Probability and Expected Utility without Additivity
- The application of fuzzy integrals in multicriteria decision making
- The problem of the optimal biobjective spanning tree
- The robust spanning tree problem with interval data
- The weighted OWA operator
- Worst case analysis of greedy and related heuristics for some min-max combinatorial optimization problems
Cited in
(10)- Single machine scheduling problems with uncertain parameters and the OWA criterion
- Ordered weighted average combinatorial optimization: formulations and their properties
- Ordered weighted average optimization in multiobjective spanning tree problem
- Looking for edge-equitable spanning trees
- Approximating combinatorial optimization problems with the ordered weighted averaging criterion
- Using the WOWA operator in robust discrete optimization problems
- Combinatorial optimization problems with uncertain costs and the OWA criterion
- A weighted-sum method for solving the bi-objective traveling thief problem
- Bottleneck combinatorial optimization problems with uncertain costs and the OWA criterion
- Alternative formulations for the ordered weighted averaging objective
This page was built for publication: Exact algorithms for OWA-optimization in multiobjective spanning tree problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1762141)
