Information Technology Reference
In-Depth Information
formulation of a Moco problem
some theoretical concepts
A MOCO problem is a discrete optimization prob-
lem, where each feasible solution
X
has
n
variables,
x
i
, constrained by a specific structure, and there
are
K
objective functions,
z
k
, to be optimized.
Without loss of generality we can formulate the
problem as follows:
A general result for Multi-Objective Linear
Programming (MLP) problems is that the set of
efficient solutions to
min{
c
X
: A
X
=
b,
X
≥0}
( )
=
is exactly the set of solutions to
Min z X k
,
1
, ...,
K
k
X D
∈
1,...
min{
l
j
c X
: A
X
=
b,
X
≥0}
,
j
j
=
K
where functions
z
k
are the objectives,
X
is the vec-
tor that represents a feasible solution (a sequence
for the flow-shop scheduling problem), and
D
is
the set of feasible solutions, a discrete set.
The criteria (reviewed in section 2.2) are of
two different kinds:
where
∑
1
l
j
=
,
l
j
>0,
j
=1, …
K
.
j
=
1,...
K
å
•
sum function:
f
i
It is important to point out that we are dealing
with a CO problem, which means that the trans-
formation of the objective functions into a linear
function (aggregating into weighted sums) does
not transform the problem into a Linear Program-
ming (LP) one. Except in some special cases,
e.g.
preemption allowance, or where idle time
insertion is advantageous, for which LP can be
applied, the discrete structure of a MOCO problem
persists. An important consequence is the fact that
the previous result for MLP is not valid, so there
could be some efficient solutions not optimal for
any weighted sum of the objectives (Ehrgott &
Gandibleux, 2002). The set of these solutions are
named Non-supported Efficient (NE) solutions,
whereas the set of the remaining ones are called
Supported Efficient (SE) solutions.
The cardinality of the NE set depends on the
number of sum objective functions. For a problem
with more than one sum objective function, NE
has many more solutions than SE.
•
bottleneck function:
f
max
= max{
f
1
, f
2
,..., f
n
}
D
efficient,
non-dominated, or Pareto optimal, if there is no
other feasible solution
X
We call a feasible solution
X
(
e
)
∈
D
such that,
∈
( )
≤
(
)
∀
z X
z X
( )
e
,
k
k
k
with at least one strict inequality.
The corresponding vector of objective values,
{
}
(
)
=
(
)
(
)
(
)
( )
e
( )
e
( )
e
( )
e
z X
z X
,
z X
, ...,
z X
1
2
K
is called non-dominated vector.
The set of feasible Efficient solutions,
X
(
e
)
,
is denoted by E, and the set of non-dominated
vectors by ND.
Search WWH ::
Custom Search