A linear bound on the number of scalarizations needed to solve discrete tricriteria optimization problems
From MaRDI portal
Publication:2342947
Abstract: General multi-objective optimization problems are often solved by a sequence of parametric single objective problems, so-called scalarizations. If the set of nondominated points is finite, and if an appropriate scalarization is employed, the entire nondominated set can be generated in this way. In the bicriteria case it is well known that this can be realized by an adaptive approach which, given an appropriate initial search space, requires the solution of a number of subproblems which is at most two times the number of nondominated points. For higher dimensional problems, no linear methods were known up to now. We present a new procedure for finding the entire nondominated set of tricriteria optimization problems for which the number of scalarized subproblems to be solved is at most three times the number of nondominated points of the underlying problem. The approach includes an iterative update of the search space that, given a (sub-)set of nondominated points, describes the area in which additional nondominated points may be located. In particular, we show that the number of boxes, into which the search space is decomposed, depends linearly on the number of nondominated points.
Recommendations
- Adaptive parametric scalarizations in multicriteria optimization
- Scalarizations for adaptively solving multi-objective optimization problems
- Solvability of 3-nondegenerate discrete multicriterion problems by the scalarization algorithm
- A coverage-based box-algorithm to compute a representation for optimization problems with three objective functions
- On the number of non-dominated points of a multicriteria optimization problem
Cites work
- K-PPM: a new exact method to solve multi-objective combinatorial optimization problems
- A method for finding the set of non-dominated vectors for multiple objective integer linear programs
- A new algorithm for generating all nondominated solutions of multiobjective discrete optimization problems
- A two phase method for multi-objective integer programming and its application to the assignment problem with three objectives
- Adaptive parametric scalarizations in multicriteria optimization
- Algorithms for nonlinear integer bicriterion problems
- An algorithm for the bi-criterion integer programming problem
- An algorithm for the multiple objective integer linear programming problem
- An augmented weighted Tchebycheff method with adaptively chosen parameters for discrete bicriteria optimization problems
- An efficient, adaptive parameter variation scheme for metaheuristics based on the epsilon-constraint method
- An improved algorithm for solving biobjective integer programs
- An interactive weighted Tchebycheff procedure for multiple objective programming
- Bicriteria Transportation Problem
- Computation of ideal and Nadir values and implications for their use in MCDM methods.
- Finding all nondominated points of multi-objective integer programs
- Finding representative systems for discrete bicriterion optimization problems
- Generating the noninferior set in mixed integer biobjective linear programs: An application to a location problem
- scientific article; zbMATH DE number 915988 (Why is no real title available?)
- Multi-objective integer programming: a general approach for generating all non-dominated solutions
- Multi-objective integer programming: an improved recursive algorithm
- Multicriteria Optimization
- Nonlinear multiobjective optimization
- The multiobjective discrete optimization problem: a weighted min-max two-stage optimization approach and a bicriteria algorithm
Cited in
(39)- Numerical analysis of tricriteria tree and assignment problems
- Bilevel programming for generating discrete representations in multiobjective optimization
- A box decomposition algorithm to compute the hypervolume indicator
- An interactive approximation algorithm for multi-objective integer programs
- Efficient computation of the search region in multi-objective optimization
- Finding a representative nondominated set for multi-objective mixed integer programs
- A bicriteria perspective on \(L\)-penalty approaches -- a corrigendum to Siddiqui and Gabriel's \(L\)-penalty approach for solving MPECs
- Half-open polyblock for the representation of the search region in multiobjective optimization problems: its application and computational aspects
- Decomposition of loosely coupled integer programs: a multiobjective perspective
- An approximation algorithm for multi-objective optimization problems using a box-coverage
- Distribution based representative sets for multi-objective integer programs
- Representing the nondominated set in multi-objective mixed-integer programs
- An exact parallel objective space decomposition algorithm for solving multi-objective integer programming problems
- FPBH: a feasibility pump based heuristic for multi-objective mixed integer linear programming
- Split algorithms for multiobjective integer programming problems
- Branch-and-bound and objective branching with three or more objectives
- The \(L\)-shape search method for triobjective integer programming
- On the representation of the search region in multi-objective optimization
- A multi-objective military system of systems architecting problem with inflexible and flexible systems: formulation and solution methods
- Multiobjective Integer Programming: Synergistic Parallel Approaches
- An adaptive patch approximation algorithm for bicriteria convex mixed-integer problems
- Branch-and-Bound for Biobjective Mixed-Integer Linear Programming
- Network Models for Multiobjective Discrete Optimization
- Monomial Tropical Cones for Multicriteria Optimization
- A coverage-based box-algorithm to compute a representation for optimization problems with three objective functions
- A Feasibility Pump and Local Search Based Heuristic for Bi-Objective Pure Integer Linear Programming
- A New Exact Algorithm to Optimize a Linear Function over the Set of Efficient Solutions for Biobjective Mixed Integer Linear Programs
- Comments on: ``Static and dynamic source locations in undirected networks
- Algorithms for generating Pareto fronts of multi-objective integer and mixed-integer programming problems
- A criterion space decomposition approach to generalized tri-objective tactical resource allocation
- Effective anytime algorithm for multiobjective combinatorial optimization problems
- Optimizing a linear function over the nondominated set of multiobjective integer programs
- Outer approximation algorithms for convex vector optimization problems
- Augmenting bi-objective branch and bound by scalarization-based information
- A fast and robust algorithm for solving biobjective mixed integer programs
- A simple, efficient and versatile objective space algorithm for multiobjective integer programming
- Generating representative sets for multiobjective discrete optimization problems with specified coverage errors
- Engineering and evaluating multi-objective pseudo-Boolean optimizers
- A method to identify a representation of the set of non-dominated points for discrete tri-objective optimization problems
This page was built for publication: A linear bound on the number of scalarizations needed to solve discrete tricriteria optimization problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2342947)
