{'fraction_non_alphanumeric': 0.016288951841359773, 'fraction_numerical': 0.0035410764872521247, 'mean_word_length': 5.826086956521739, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Optimal Lagrangian Multipliers for the Multidimensional Knapsack Problem: a Bayesian Optimisation Approach

This paper considers the Lagrangian relaxation approach for the well-known multidimensional knapsack problem which maximises the total profits of selected items within the capacities of multiple resources. By relaxing “hard” constraints using Lagrangian multipliers, the Lagrangian relaxation approach provides a systematic framework for obtaining both the upper bound and the lower bound for hard combinatorial optimisation problems. Although tremendous efforts, both theoretical and computational, have been put into the study of the upper bound (assuming maximisation for the objective) for the Lagrangian relaxation approach, little attention has been drawn to the study of the impact of Lagrangian multipliers on the quality of the lower bound, or feasible solutions of the studied problem. In this paper, the lower bound problem is framed as an optimisation problem which chooses the best Lagrangian multipliers to obtain strong lower bound, i.e., good feasible solutions. A Bayesian optimisation approach is employed to solve this unconventional nonlinear optimisation problem. Computational experiments are carried out on the widely used benchmark instances with up to 250 items and 30 knapsack constraints. The preliminary results demonstrate the effectiveness of the proposed solution approach.