International Transactions in Operational Research,
Год журнала:
2022,
Номер
31(3), С. 1890 - 1916
Опубликована: Окт. 1, 2022
Abstract
We
consider
the
multiple
knapsack
problem
(KP)
with
setup
(MKPS),
which
is
an
extension
of
KP
(KPS).
propose
a
new
solving
approach
denoted
by
LP&DP‐VNS
that
combines
linear
programming
(LP)
relaxation
and
dynamic
(DP)
to
enhance
variable
neighborhood
search
(VNS).
The
tailored
characteristics
MKPS
reduced
LP&DP
solve
KPS.
tested
on
200
KPS
360
benchmark
instances.
Computational
experiments
show
effectiveness
LP&DP‐VNS,
compared
integer
(using
CPLEX)
best
state‐of‐the‐art
algorithms.
It
reaches
299/342
optimal
solutions
316/318
best‐known
provides
127
solutions.
An
additional
computational
study
shows
scales
up
extremely
well,
optimally
near‐optimally
very
large
instances
families
300,000
items
in
reasonable
amount
time.
Journal of the Operational Research Society,
Год журнала:
2023,
Номер
75(3), С. 423 - 617
Опубликована: Дек. 27, 2023
Throughout
its
history,
Operational
Research
has
evolved
to
include
methods,
models
and
algorithms
that
have
been
applied
a
wide
range
of
contexts.
This
encyclopedic
article
consists
two
main
sections:
methods
applications.
The
first
summarises
the
up-to-date
knowledge
provides
an
overview
state-of-the-art
key
developments
in
various
subdomains
field.
second
offers
wide-ranging
list
areas
where
applied.
is
meant
be
read
nonlinear
fashion
used
as
point
reference
by
diverse
pool
readers:
academics,
researchers,
students,
practitioners.
entries
within
applications
sections
are
presented
alphabetical
order.
authors
dedicate
this
paper
2023
Turkey/Syria
earthquake
victims.
We
sincerely
hope
advances
OR
will
play
role
towards
minimising
pain
suffering
caused
future
catastrophes.
Annals of Operations Research,
Год журнала:
2023,
Номер
326(1), С. 137 - 156
Опубликована: Апрель 1, 2023
Abstract
We
consider
three
new
knapsack
problems
with
variable
weights
or
profits
of
items,
where
the
weight
profit
an
item
depends
on
position
in
sequence
items
packed
knapsack.
show
how
to
solve
exactly
using
dynamic
programming
algorithms
pseudo-polynomial
running
times
and
propose
fully
polynomial-time
approximation
schemes
for
their
approximate
solution.
Annals of Operations Research,
Год журнала:
2024,
Номер
unknown
Опубликована: Май 13, 2024
Abstract
The
efficient
management
of
complex
production
systems
is
a
challenge
in
today’s
logistics.
In
the
field
intelligent
and
sustainable
logistics,
optimization
batches,
especially
context
rapidly
changing
product
range,
requires
fast
precise
computational
solutions.
This
paper
explores
potential
quantum
computers
for
solving
these
problems.
Traditional
methods
are
often
limited
when
it
comes
to
optimizing
logistics
systems.
response
challenges,
proposes
use
hybrid
algorithm
that
combines
technologies
with
classical
methods.
Such
integration
allows
power
both
types
be
harnessed,
leading
faster
more
identification
optimal
this
work,
we
consider
knapsack
problem,
classic
NP-hard
problem
commonly
used
verify
effectiveness
new
construction
presented
based
on
Branch
Bound
method
aims
ensure
solution
optimality
non-determinism
computers.
Within
algorithm,
computations
performed
alternately
processor
processor.
addition,
lower
upper
bounds
objective
function
computed
constant
time
using
D-Wave
machine.
Mathematics,
Год журнала:
2025,
Номер
13(7), С. 1097 - 1097
Опубликована: Март 27, 2025
The
Knapsack
Problem
belongs
to
the
best-studied
classical
problems
in
combinatorial
optimization.
Multiple-choice
(MCKP)
represents
a
generalization
of
problem,
with
various
application
fields
such
as
industry,
transportation,
telecommunication,
national
defense,
bioinformatics,
finance,
and
life.
We
found
lack
survey
papers
on
MCKP.
This
paper
overviews
MCKP
presents
its
variants,
solution
methods,
applications.
Traditional
operational
research
methods
solving
knapsack
dynamic
programming,
greedy
heuristics,
branch-and-bound
algorithms,
can
be
adapted
Only
few
algorithms
appear
have
solved
problem
recent
years.
related
during
literature
study
explored
broad
spectrum
areas.
intend
inspire
into
motivate
experts
from
different
domains
apply
