Pareto suboptimal solutions to large-scale multiobjective multidimensional knapsack problems with assessments of Pareto suboptimality gaps

2017/08/23 by Ignacy Kaliszewski, Kaliszewski, Ignacy
Mathematics · #90 #FOS: Mathematics #Optimization and Control (math.OC) #math.OC #msc:90

paper · pdf · doi:10.48550/arxiv.1708.07069

Section 6.1 needs major corrections. 28 pages, 5 figures,8 tables, 31 referencs

arxiv created 2017/11/10 · arxiv updated 2017/11/13

Abstract

When solving large-scale multiobjective optimization problems, solvers can get stuck with the memory or time limit. In such cases, one is left with no information how far is the best feasible solution, found before the optimization process has stopped, to the true Pareto optimal solution. In this work, we show how to provide such information when solving multiobjective multidimensional knapsack problems by a commercial mixed-integer linear solver. We illustrate the proposed approach on biobjective multidimensional knapsack problems derived from singleobjective multidimensional knapsack problems from the Beasley OR Library.

Related

• The multiobjective multidimensional knapsack problem: a survey and a new approach
• Randomized heuristic repair for large-scale multidimensional knapsack problem
• A general framework for providing interval representations of Pareto optimal outcomes for large-scale bi- and tri-criteria MIP problems
• Knapsack Problems: A Parameterized Point of View
• Efficiently Tackling Million-Dimensional Multiobjective Problems: A Direction Sampling and Fine-Tuning Approach