A matheuristic for tri-objective binary integer linear programming
From MaRDI portal
Abstract: Many real-world optimisation problems involve multiple objectives. When considered concurrently, they give rise to a set of optimal trade-off solutions, also known as efficient solutions. These solutions have the property that neither objective can be improved without deteriorating another objective. Motivated by the success of matheuristics in the single-objective domain, we propose a linear programming-based matheuristic for tri-objective binary integer programming. To achieve a high-quality approximation of the optimal set of trade-off solutions, a lower bound set is first obtained using the vector linear programming solver Bensolve. Then, feasibility pump-based ideas in combination with path relinking are applied in novel ways so as to obtain a high quality upper bound set. Our matheuristic is compared to a recently-suggested algorithm that is, to the best of our knowledge, the only existing matheuristic method for tri-objective integer programming. In an extensive computational study, we show that our method generates a better approximation of the true Pareto front than the benchmark method on a large set of tri-objective benchmark instances. Since the developed approach starts from a potentially fractional lower bound set, it may also be used as a primal heuristic in the context of linear relaxation-based multi-objective branch-and-bound algorithms.
Cites work
- A Feasibility Pump and Local Search Based Heuristic for Bi-Objective Pure Integer Linear Programming
- A feasibility pump heuristic for general mixed-integer problems
- A heuristic two-phase solution approach for the multi-objective dial-a-ride problem
- A new algorithm for generating all nondominated solutions of multiobjective discrete optimization problems
- A survey on matheuristics for routing problems
- An Algorithm for Multiobjective Zero-One Linear Programming
- Bi-objective branch-and-cut algorithms based on LP relaxation and bound sets
- Bicriteria Transportation Problem
- Boosting the feasibility pump
- Bound sets for biobjective combinatorial optimization problems
- Branch-and-bound and objective branching with three or more objectives
- Branch-and-Bound for Biobjective Mixed-Integer Linear Programming
- Connectedness of efficient solutions in multiple criteria combinatorial optimization
- Connectedness of efficient solutions in multiple objective combinatorial optimization
- Enumeration of the Nondominated Set of Multiobjective Discrete Optimization Problems
- Evolutionary Multi-Criterion Optimization
- Exploring relaxation induced neighborhoods to improve MIP solutions
- Feasibility pump 2.0
- FPBH: a feasibility pump based heuristic for multi-objective mixed integer linear programming
- Heuristic approaches for biobjective mixed 0-1 integer linear programming problems
- scientific article; zbMATH DE number 1054674 (Why is no real title available?)
- scientific article; zbMATH DE number 1975101 (Why is no real title available?)
- ILP heuristics and a new exact method for bi-objective 0/1 ILPs: application to fttx-network design
- Improving the feasibility pump
- Local branching
- MIPLIB 2017: data-driven compilation of the 6th mixed-integer programming library
- Multi- and many-objective path-relinking: a taxonomy and decomposition approach
- Multicriteria Optimization
- On a Bicriterion Formulation of the Problems of Integrated System Identification and System Optimization
- The feasibility pump
- The quadrant shrinking method: a simple and efficient algorithm for solving tri-objective integer programs
- The vector linear program solver \textit{Bensolve} -- notes on theoretical background
- Variable neighborhood search: Principles and applications
- Warm-starting lower bound set computations for branch-and-bound algorithms for multi objective integer linear programs
Cited in
(2)
This page was built for publication: A matheuristic for tri-objective binary integer linear programming
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6065590)
