Finding and Exploring Promising Search Space for the 0-1 Multidimensional Knapsack Problem Jitao Xu Hongbo Li Minghao Yin

2025-04-27 0 0 892.42KB 19 页 10玖币

侵权投诉

Finding and Exploring Promising Search Space for the 0-1 Multidimensional

Knapsack Problem

Jitao Xu, Hongbo Li, Minghao Yin

College of Information Science and Technology, Northeast Normal University, Changchun, China.

Abstract

The 0-1 Multidimensional Knapsack Problem (MKP) is a classical NP-hard combinatorial optimization problem with

many engineering applications. In this paper, we propose a novel algorithm combining evolutionary computation

with the exact algorithm to solve the 0-1 MKP. It maintains a set of solutions and utilizes the information from

the population to extract good partial assignments. To ﬁnd high-quality solutions, an exact algorithm is applied to

explore the promising search space speciﬁed by the good partial assignments. The new solutions are used to update

the population. Thus, the good partial assignments evolve towards a better direction with the improvement of the

population. Extensive experimentation with commonly used benchmark sets shows that our algorithm outperforms

the state-of-the-art heuristic algorithms, TPTEA and DQPSO, as well as the commercial solver CPlex. It ﬁnds better

solutions than the existing algorithms and provides new lower bounds for 10 large and hard instances.

Keywords: 0-1 Multidimensional Knapsack Problem, Evolutionary Computation, Heuristic, Exact Algorithm,

Large Neighbourhood Search

1. Introduction

The 0-1 Multidimensional Knapsack Problem (MKP) is a well-known combinatorial optimization problem that

has been applied in different practical domains. Given a set

{

1, 2, ...,

of items with proﬁts

pi>0

and a set

{

1, 2, ...,

of resources with a capacity

bj>0

for each resource. Each item

consumes a given amount of

each resource

rij >0

. The 0-1 MKP is to select a subset of items that maximize the sum of the proﬁts without

exceeding the capacity of each resource. The problem is formally stated as:

Maximize f=

i=1

pixi

s.t.

i=1

rij xi≤bj, j ∈M={1,2, ..., m}

xi∈ {0,1}, i ∈N={1,2, ..., n}

where each

is a binary variable indicating whether the item

is selected, i.e.,

= 1 if the item is selected, and 0

otherwise.

The 0-1 MKP has many real-world engineering applications, such as resource allocation [

], cutting

stock [

], portfolio-selection [

], obnoxious facility location[

], slice admission control problem[

], food order

optimization problems[

], and multi-unit combinatorial auction[

]. Due to its NP-hard characteristic, solving

the MKP is computationally challenging. The exact algorithms for the MKP are usually based on branch and

bound(B&B) algorithms, such as the CORAL algorithm [

]. However, the modern exact algorithms could solve

only the MKP instances of relatively small and moderate size, i.e., the instances with less than 250 items and less

than 10 resource constraints. For larger instances with more than 500 items and more than 30 resource constraints,

the heuristic algorithms are usually better choices.

There exist a number of heuristic algorithms for the problem. For instance, the single-solution based local

search algorithms maintain a solution during the search process and iteratively optimize it. The representative

of these algorithms include Tabu Search[

], Simulated Annealing [

], Kernel Search[

], and Core Problem

Algorithm[

]. In recent years, the population-based evolutionary algorithms are more popular for the problem,

such as Particle Swarm Optimization(PSO)[

]. Ant Colony Optimization[

], Moth

Search Optimization[

], Pigeon Inspired Optimization[

], Bee Colony Algorithm[

], Quantum Cuckoo

Search Algorithm[

], Fruit Fly Optimization Algorithm[

] and Grey Wolf Optimizer[

]. Chih et al.

[15]

Email address: lihb905@nenu.edu.cn (Hongbo Li)

Preprint submitted to Applied Soft Computing May 28, 2024

arXiv:2210.03918v3 [cs.AI] 27 May 2024

introduced two algorithms based on binary PSO to address the MKP. Building upon this research, Chih

[16]

further

improved the efﬁcacy of PSO in handling the MKP by incorporating the self-adaptive check and repair operator

(SACRO) mechanism. This enhancement was subsequently reﬁned in 2018 by introducing an advanced SACRO

concept integrating three pseudo-utility ratios to augment efﬁciency [

]. In a different approach, Haddar et al.

[18]

adopts quantum particle swarm optimization (QPSO) to address the MKP, while Lai et al.

[19]

innovated a

diversity-preserving mechanism aimed at enhancing the diversity of the population in QPSO. Hybrid algorithms

have also been proposed, such as the NP+BAS+LP algorithm introduced by Al-Shihabi and

Olafsson

[21]

. This

hybrid approach integrates Binary Ant System (BAS) within a Nested Partition (NP) framework, leveraging Linear

Programming (LP) relaxations to guide partitioning and improve solution quality. BAS facilitates the generation of

feasible solutions within each partition, thereby enhancing search efﬁciency. On the nature-inspired optimization

front, Feng and Wang

[23]

proposed a binary moth search algorithm speciﬁcally designed for the MKP. Additionally,

Setiawan et al.

[24]

introduced Pigeon-Inspired Optimization (PIO) for solving the MKP. Further contributions

include an enhanced binary heuristic algorithm based on the Artiﬁcial Bee Colony (ABC) method by Wei

[26]

Binary Fruit Fly Optimization Algorithm (bFOA) proposed by Wang et al.

[29]

, and an enhanced version of Fruit

Fly Optimization Algorithm (IFFOA) by Meng and Pan

[28]

. Each of these algorithms brings unique strategies

to the table, such as utilizing binary strings to represent solutions, incorporating various search processes, and

employing repair operators to ensure solution feasibility. Moreover, Luo and Zhao

[30]

utilized The Binary Grey

Wolf Optimizer (GWO) for solving the MKP. This approach combines critical elements, including an initial elite

population generator, a quick repair operator based on pseudo-utility, and a novel evolutionary mechanism featuring

a differentiated position updating strategy, to achieve improved performance in solving the MKP. Recently, machine

learning assisted methods[

], along with probability learning-based algorithms[

] emerged. Rezoug

et al.

[31]

tested different machine learning methods to predict each item of the knapsack and select the items

that have a higher score predicted by the model. Garc

ıa and Maureira

[27]

combines nearest K-neighbors (KNN)

and cuckoo search. They use KNN to improve the diversiﬁcation of cuckoo search. Garc

ıa et al.

[33]

adopted

db-scan to perform the binarization process on solutions generated by swarm intelligence algorithms. Although

these algorithms provide a new perspective, they are less efﬁcient than the heuristic algorithms when solving large

MKP instances. Therefore, heuristics algorithms are still a popular choice when solving some large and hard MKP

instances in practice. Among these heuristic algorithms, the TPTEA[

] algorithm and DQPSO [

] algorithm can

be considered as the state of the art for the MKP. TPTEA incorporates tabu search techniques into a population-based

evolutionary framework, creating a two-phase search algorithm that guarantees both effective intensiﬁcation and

diversiﬁcation across the search space. To our best knowledge, the TPTEA algorithm provided the last updates

of the lower bounds of the commonly used benchmark set containing the large instances with 500 items and 30

resource constraints. DQPSO integrates a diversity-preserving mechanism to ensure a robust variety within the

quantum particle swarm, preventing premature convergence of the algorithm. Compared with TPTEA, the DQPSO

algorithm loses a little in the ﬁnal solution quality, but it ﬁnds high-quality solutions earlier than TPTEA.

The population-based evolutionary algorithms have good prospects in solving the 0-1 Multidimensional Knap-

sack Problem. In this paper, we propose a novel algorithm for the 0-1 MKP. The algorithm ﬁnds promising

partial assignments by an adapted evolutionary algorithm and explores the promising search space speciﬁed by the

partial assignments with an exact algorithm. It utilizes the advantages of Evolutionary Computation and Large

Neighbourhood Search (LNS) [

] in its major components. It eliminates those search spaces when the exact

algorithm is searching, both items that are likely to be selected and unlikely to be chosen. During each search of the

exact algorithm, we keep a solution population to avoid wastage. Consequently, it performs well when solving some

large and hard 0-1 MKP benchmark instances. Our experiments run with 281 commonly used benchmark instances

show that our algorithm performs better than the state-of-the-art heuristic algorithms including TPTEA and DQPSO.

Our contribution can be summarized as, (1) We propose to combine Evolutionary Computation with exact algorithm

to solve the 0-1 MKP. (2) We adopt and adapt the TPTEA algorithm to ﬁnd promising partial assignments from the

population. (3) Our algorithm provides new a lower bound for 8 hard and large instances.

The paper is organized as follows. We ﬁrst introduce the motivation and the raw idea of our algorithm in

Section 2. The details of the proposed algorithm, including the framework of the new algorithm, and the adaption

of the TPTEA algorithm for ﬁnding good partial assignments, a customized LNS, are present in Section 3. The

experimental results are shown in Section 4. We discussed our algorithm with some closely related methods in

Section 5. Finally, Section 6 is the conclusion.

2. The Motivation

An assignment

to items

I⊆N

is a set of instantiations of the form (

xi=vi

), one for each

i∈N

to assign

where

vi∈ {0,1}

. If

I=N

, then

is a complete assignment; otherwise a partial assignment. A complete

assignment

that satisﬁes all resource constraints is a feasible solutions to the instance, or a solution for short. A

solution

is an optimal solution if its objective value

f(s)

is larger than or equal to that of any other solution to the

instance. A partial assignment is an optimal one if it can be extended to an optimal solution.

Given an MKP instance

with

items, the size of the search space of ﬁnding an optimal solution for

Given a partial assignment

. Fixing the values of

will result in a sub-problem

P′

whose search space

is 2n−|A|. The search space of P′can be considered as a sub search space of Pwhich is speciﬁed by A. If we are

given an optimal partial assignment

A∗

, then we can ﬁnd an optimal solution for

in a search space of size

2n−|A∗|

instead of the entire search space of size

. However, as far as we know, there is no existing method that

identiﬁes optimal partial assignment for general 0-1 MKP before solving it exactly. Thus, the aim of our algorithm

is to ﬁnd good partial assignments that have a large possibility of being an optimal one, or can be extended to a

high-quality solution whose objective value is close to that of an optimal solution. Then exploring the promising

search space speciﬁed by the good partial assignments may ﬁnd high-quality solutions efﬁciently.

Evolutionary Algorithms (EA) are powerful techniques for solving combinatorial optimization problems based

on the simulation of biological evolution. They start from a population of individuals (representing solutions) and

produces offspring (new solutions) by utilizing the information of the population. Guided by a ﬁtness function

measuring the quality of a solution, the new solutions with high-quality are usually used to update the population.

As a result, the population evolves towards the direction of better ﬁtness function. One of the advantages of EA

is to identify and keep some high-quality patterns (partial assignments) in the population, so they can produce

high-quality solutions through crossover and mutation operations. Thus, we propose a novel algorithm that combines

Evolutionary Algorithm with exact algorithm for the 0-1 MKP. The main idea of the algorithm is shown in Algorithm

Algorithm 1: The main idea

Input: a MKP instance P;

Output: current best solution s∗;

1population ←initPopulation(P);

2s∗←the best solution in population;

3while the termination condition is not reached do

4pa ←extract(population);

5s←explore(P, pa);

6updatePopulation(s);

7if f(s)> f(s∗)then

8s∗←s;

9return s∗;

At the beginning, the population of Evolutionary Algorithm, a set of solutions recorded in

population

initialized at line 1. The

s∗

records the best solution found so far. The loop at lines 3-8 is the main procedure, e.g., a

promising partial assignment pa is extracted from the population by an Evolutionary Algorithm at line 4 and the

promising search space is explored by an exact algorithm at line 5. The new solution is used to update the population

at line 6. If a better solution is found,

s∗

will be updated accordingly at lines 7-8, The procedure repeats until a

termination condition is reached and the best found solution is returned. There are various termination conditions

that can be used in the algorithm, such as a time limit or the number of iterations.

3. Related Work

There exist some methods combining Evolutionary Computation with exact algorithms for solving combinatorial

optimization problems. We refer those ones related to our method in the following, and then discuss the differences

at the end of next section.

Kernel Search Angelelli et al.

[13]

can be applied in solving the MKP. It divides the item set into two parts, the

kernel, and the buckets, and then applies an exact algorithm in the kernel. Kernel Search ﬁnds the solution of the

continuous relaxation problem, and sorts the items according to the information provided by the continuous solution.

Then it selects the ﬁrst Citems as a kernel

. The items belonging to

N\Λ

construct a sequence

{Bi}

of buckets.

Finally, an exact algorithm is iteratively applied in the kernel. In each iteration, some of the items in buckets are

selected and added into the kernel. There are two additional constraints in each run of the exact algorithm: (1) the

lower bound is the current best solution; (2) at least one of the latest added items should be selected in the solution.

The Generate And Solve framework (GAS) [

] was originally designed for solving the container loading

problem. The framework suggests decomposing the original problem into several sub-instances whose solutions are

also the solutions of the original one, and then applying some exact algorithms in the sub-instances. Besides the

GAS framework, the Construct, Merge, Solve

Adapt algorithm (CMSA) [

] suggests to generates sub-instances

by merging different solution components found in probabilistically constructed solutions. The algorithm has been

applied in solving the minimum common string partition (MCSP) problem, and a minimum covering arborescence

(MCA) problem.

Gallardo et al.

[40]

propose a hybrid algorithm that combines exact algorithm with evolutionary computation

for the MKP. It runs an evolutionary algorithm and an exact algorithm alternately. The two algorithm components

share a single solution. Whenever one algorithm component Aﬁnds a new solution better than the current best

solution, the other algorithm component Btakes over and the new solution is used to assist algorithm component B.

More speciﬁcally, when the exact algorithm ﬁnds a better solution, the solution is used to replace the worst one in

the population of the evolutionary computation. On the other hand, when the evolutionary algorithm ﬁnds a better

solution, the objective of the solution is used to update the lower bound of the exact algorithm.

4. Combining Evolutionary Algorithm with Integer Programming for the MKP

Based on the idea proposed in last section, we introduce the detailed algorithm for solving the 0-1 MKP, namely

ﬁnding and exploring promising search space (FEPSS). The framework of the algorithm is presented ﬁrst.

4.1. The Framework

The main procedure of FEPSS is present in Algorithm 2. At the beginning, the population, a set of solutions, is

initialized at line 1 and the current best solution is initialized to the best one of the initial population. There are two

cases to ﬁnd and explore good partial assignments. In the ﬁrst case (lines 10-12), the good partial assignments are

extracted from the population at line 11 and the search space speciﬁed by

is explored at line 12. In the second

case (lines 6-8), we run a customized Large Neighbourhood Search procedure to reﬁne current best solution. Each

of the two cases returns a new solution

, which is used to update the population at line 13 and update the current

best solution at lines 14-16. A counter num is used to record the number of the ﬁrst case is executed. If the counter

reaches a predeﬁned parameter lnsLimit or the best solution is updated, the second case will be executed once. The

details of the procedures called in the framework will be introduced in the following subsections.

Algorithm 2: The framework

Input: a MKP instance P;

Output: current best solution s∗;

1population ←initPopulation(P);

2s∗←the best solution in population;

3num ←0;

4while the termination condition is not reached do

5if iterationNum = lnsLimit or bestUpdated then

6bestUpdated ←false;

7num ←0;

8s←LNS(P,s∗);

9else

10 num ←num + 1;

11 pa ←extractFromPopulation(P);

12 s←explore(P,pa);

13 updatePopulation(s);

14 if f(s)> f(s∗)then

15 bestUpdated ←true;

16 s∗←s;

17 return s∗;

Note that there is a preprocessing step ahead of the algorithm, e.g., all the items are preprocessed and renumbered

in an ascending order of the surrogate relaxation ratio[41] evaluation of the items, which is deﬁned as follows.

ci=pi

j=1

rij

,∀i∈ {1,2, ..., n}(1)

After the items are renumbered, the corresponding

and

rij

are adjusted accordingly. In the following, all the

items will be used with their new numbering. An item

is selected (not selected) in a solution means that the value

of the corresponding variable

is 1 (0), and vice versa.

population[k]

is the

solution in

population

and

s[i]

is the value of variable xiin solution s.

In the following subsections, we will introduce the initPopulation,extractFromPopulation,LNS,explore and

updatePopulation procedures in details.

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

10 玖币 0人已下载

立即下载

摘要：

FindingandExploringPromisingSearchSpaceforthe0-1MultidimensionalKnapsackProblemJitaoXu,HongboLi,MinghaoYinCollegeofInformationScienceandTechnology,NortheastNormalUniversity,Changchun,China.AbstractThe0-1MultidimensionalKnapsackProblem(MKP)isaclassicalNP-hardcombinatorialoptimizationproblemwithmanyen...

展开>> 收起<<

Finding and Exploring Promising Search Space for the 0-1 Multidimensional Knapsack Problem Jitao Xu Hongbo Li Minghao Yin.pdf

共19页,预览4页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

Finding and Exploring Promising Search Space for the 0-1 Multidimensional Knapsack Problem Jitao Xu Hongbo Li Minghao Yin

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: