How to define a multiobjective optimization problem in DESDEO¶
In this example, we show how multiobjective optimization problems can be defined in DESDEO. We showcase multiple types of variables, constraints, and objective functions. We then show how these can be combined to formulate a multiobjective optimization problem.
Vehicle design problem¶
In this example, we consider a vehicle design problem with three objective functions. The goal is to minimize cost $C(x_1, x_2, \mathbf{y})$, minimize emissions $E(x_1, x_2, \mathbf{y})$, and maximize a performance index $P(x_1, x_2, \mathbf{y})$ of the vehicle being designed. These objective functions are functions of the engine size ($x_1$, in liters), the number of cylinders ($x_2$), and the percentage material composition of the vehicle ($\mathbf{y}=[y_1, y_2]$; $y_1$ percentage of aluminum, $y_2$ percentage of steel). These variables are also subject to two constraints: the safety rating of the vehicle $g(\mathbf{y})$ must meet or exceed a specific value ($S=35$), and the fuel efficiency $f(x_1, x_2, \mathbf{y})$ must meet or exceed a specific threshold ($FE=20$). All the variables values must in addition be positive. The variable $x_1$ must be greater or equal than 4, and not exceed the value 30; and the variable $x_2$ must be greater or equal than 2, and not exceed the value 24. In addition, when calculating performance, there is an ideal number of cylinders $IC=8$. Deviating from this value will result in a performance penalty. Finally, the composition percentages must sum to $100$, i.e., $y_1 + y_2 = 100$.
With some mock functions, we can define the vehicle design problem as follows:
$$ \begin{aligned} \text{Minimize} \quad & C(x_1, x_2, \mathbf{y}) = 5000x_1 + 2000x_2 + 100y_1 + 50y_2 \\ \text{Minimize} \quad & E(x_1, x_2, \mathbf{y}) = 0.5x_1^2 + 0.3x_2^2 + 0.1y_1 + 0.05y_2 + |x_1 - IC| \\ \text{Maximize} \quad & P(x_1, x_2, \mathbf{y}) = 10x_1 + 5x_2 - 0.2y_2 \\ \text{Subject to} \quad & f(x_1, x_2, \mathbf{y}) = 25 - 0.2x_1 - 0.1x_2 + 0.05y_1 + 0.03y_2 \geq FE \\ & g(\mathbf{y}) = 0.8y_1 + 0.6y_2 \geq S \\ & 0 \leq x_1 \leq 30, \quad 0 \leq x_2 \leq 24 \\ & y_1 + y_2 = 100 \\ & y_1 \geq 0, \quad y_2 \geq 0. \end{aligned} $$
Basic variables¶
By basic variable, we refer to variables that can be represented by a scalar variable. In the vehicle design problem,these
correspond to $x_1$ and $x_2$. To define these variables, we use the class Variable from the desdeo.problem module as follows:
from desdeo.problem import Variable, VariableTypeEnum
x_1 = Variable(
name="Engine size",
symbol="x_1",
variable_type=VariableTypeEnum.real,
lowerbound=4.0,
upperbound=30.0,
initial_value=4.0,
)
x_2 = Variable(
name="Number of cylinders",
symbol="x_2",
variable_type=VariableTypeEnum.integer,
lowerbound=2,
upperbound=24,
initial_value=2,
)
Let us look closer to the attributes we have provided when defining a
Variable. First, we have provided the variable's name, which should be
descriptive, but short. The symbol attribute is a very central one, since it
will be used to refer to the variable when, e.g., defining objective functions
and constraints, as we will see later. The symbol should be unique across the
whole problem definition. The variable_type attribute is also of interest,
since it can be used to provide additional information about the type of the
variable, i.e., whether it is an integer, real-valued, or binary. Similarly, the
lowerbound and upperbound attributes can be used to define the
box-constraints (if any) of the variable. If no bounds are provided, it is
assumed that the variable is unbounded, either by its lower or upper value, or
both. Lastly, we may provide the initial value (initial_value) of the
variable, which can be useful when the resulting multiobjective optimization
problem is solved with an optimization method that either requires a starting
guess of an optimal solution, or can make use of such information by other
means.
Note
We will see the `symbol` attribute later in almost all components defining a problem. It is an important identifier that can be used in many different places in DESDEO to specify on what parts of a multiobjective optimization problem to perform various operations. In each problem definition in DESDEO, the `symbol` attribute is assumed to be unique across all the components of the problem.
Tensor and vector variables¶
Apart from scalar variables, DESDEO support tensor and vector variables, that
is, variables with multiple dimensions. In the case of the vehicle design
problem, we have one such variable, the material composition of the vehicle
$\mathbf{y}$. This can be defined similarly to a scalar variable, but using the
TensorVariable class instead:
from desdeo.problem import TensorVariable
y = TensorVariable(
name="Material composition",
symbol="y",
shape=[2],
variable_type=VariableTypeEnum.real,
lowerbounds=[0.0, 0.0], # Bounds may be specified for each element separately...
upperbounds=100.0, # ...or one value can be provided, which will be used for all elements.
initial_values=[50.0, 50.0],
)
A TensorVariable is thus defined very similarly to a Variable, but it comes
with some small differences and extra attributes. We have already covered the
purpose of the name, symbol, and variable_type attributes. As a new
important new attribute, we have shape which is used to define the dimensions
of the variable being defined. In this case, the dimension is [2], which means
the variable has two elements with no particular orientation. If we wanted to
define a similar row vector, we would provide the shape [1, 2], or in the case
of a column vector, the shape [2, 1]. Similarly, if our variable was a matrix
with, for instance, five rows and four columns, the shape would be [5, 4]. It
is important to note that the shape attribute becomes very important when
variables are utilized in vector and matrix calculations, but we will not cover
those in this example. A vector with no particular orientation suffices in the
case of this example, since (as seen later) we utilize the TensorVariable as
convenient way to represent multiple variables using one single Python object.
Note
`TensorVariable` becomes very useful when defining problems with, e.g., a lot of binary variables.
Additionally, we see that the the attributes lowerbounds, upperbounds, and
initial_values are now in plural. As shown, we may either provide values for
each element of the tensor using a list (as done with the lowerbounds), or we
may provide a single value, in which case the bound is assumed to be the same
for all elements (as done with the upperbounds). This applies for
initial_values as well. If some elements should have a lower or upperbounds,
or both, and some elements are unbound, then the value None may be provided
instead of a numerical value.
Constants¶
Apart from variables, constants can be defined as well. We have the constants
$IC$, This is done using the Constant class:
from desdeo.problem import Constant
ideal_n_cylinders = Constant(
name="Ideal number of cylinders",
symbol="IC",
value=8,
)
fuel_efficiency_th = Constant(
name="Fuel efficiency threshold",
symbol="FE",
value=20,
)
safety_th = Constant(
name="Safety rating threshold",
symbol="S",
value=35,
)
As we can see, constants are straightforward to define. Notice how they also
take as an attribute a symbol. Similar to TensorVariables, DESDEO provides
the class TensorConstant in the module desdeo.problem. This can be used to
define multi-dimensional constants as well, either as a convenience, or to be
used as part of vector and matrix calculations. However, we will not cover the
latter in this example.
Objective functions¶
We are now ready to define the objective functions of the vehicle design problem. This is done as follows using the Objective class:
from desdeo.problem import Objective, ObjectiveTypeEnum
cost = Objective(
name="Cost",
symbol="C",
unit="euros",
func="5000*x_1 + 2000*x_2 + 100*y[1] + 50*y[2]",
objective_type=ObjectiveTypeEnum.analytical,
maximize=False,
is_convex=True,
is_linear=True,
is_twice_differentiable=True,
)
emissions = Objective(
name="Emissions",
symbol="E",
unit="kg",
func="0.5*x_1**2 + 0.3*x_2**2 + 0.1*y[1] + 0.05*y[2] + Abs(x_1 - IC)",
objective_type=ObjectiveTypeEnum.analytical,
maximize=False,
is_convex=False,
is_linear=False,
is_twice_differentiable=False,
)
performance = Objective(
name="Performance index",
symbol="P",
func="10*x_1 + 5*x_2 - 0.2*y[2]",
objective_type=ObjectiveTypeEnum.analytical,
is_convex=True,
is_linear=True,
is_twice_differentiable=True,
)
The name and symbol attributes play the same role as in the case of
variables and constants. The attribute unit on the other hand is used to
indicate the units of the value represented by the objective function, e.g.,
"euros" in the case of the cost.
More importantly, we notice the new attribute func, which is used to provide
the functional representation of the objective function. The may be readily
written out using a string representation. We can write the functions as we
would write them in Python, and we can refer to variables and constants using
their respective symbol values (we may refer in practice to any element of the
problem with a defined symbol attribute!). We may also access the elements of
tensor variables by using brackets ([]), as is done in the case of the
variable y. Notice that indexing starts at 1. Also worth noting is that, apart
from basic operations, such as multiplication (*) and addition (+), other
operations are also available, such as the absolute value function (Abs())
used in the function expression for emission.
Note
When accessing multidimensional variables or constants, such as vectors or other tensors, indexing starts at 1.
The objective_type attribute is also important. It is used to indicate the
type of objective function. In the case of this example, each objective is
analytical (or analytic), which in DESDEO, meant that the objective function can
be represented by writing down its mathematical definition. Notice that in
DESDEO this does not mean that the function is infinitely differentiable! There
are also other types of objective functions, which are covered it other
examples.
Next, we have the attribute maximize, which is used to indicate whether the
objective function is to be maximized (True) or minimized (False). If not
explicitly defined, objective functions are assumed to be minimized in DESDEO by
default. Finally, we have the attributes is_convex, is_linear, and
is_twice_differentiable, which indicate whether the objective function is
convex, linear, and/or twice differentiable, respectively. This information is
important when choosing (either manually or automatically, e.g., when solving
the multiobjective optimization problem) an adequate solver.
Constraints¶
Before our problem definition can be completed, we still need to define its
constraints. This is done very similarly to how objective functions were
defined, using the Constraints class:
from desdeo.problem import Constraint, ConstraintTypeEnum
fuel_efficiency_constraint = Constraint(
name="Fuel efficiency related constraint threshold",
symbol="FE_con",
func="0.2*x_1 - 0.1*x_2 + 0.05*y[1] + 0.03*y[2] - FE",
cons_type=ConstraintTypeEnum.LTE,
is_convex=True,
is_linear=True,
is_twice_differentiable=True,
)
safety_rating_constraint = Constraint(
name="Safety rating related constraint",
symbol="S_con",
func="0.8*y[1] + 0.6*y[2] - S",
cons_type=ConstraintTypeEnum.LTE,
is_convex=True,
is_linear=True,
is_twice_differentiable=True,
)
material_composition_constraint = Constraint(
name="Material composition must sum to 100%",
symbol="y_con",
func="y[1] + y[2]",
cons_type=ConstraintTypeEnum.EQ,
is_convex=True,
is_linear=True,
is_twice_differentiable=True,
)
We quickly notice that the constraints functions for the fuel efficiency and the
safety rating are not exactly as in the definition. This is because in DESDEO,
constraints are always assumed to be in a standard form. This means that any
inequality constraint should follow the form $g(...) \leq 0$, and equality
constraint the form $h(...) = 0$. In other words, all the terms of the
constraint should be moved to its left hand side so that the right hand belongs
zero. This is what has been done in the above code for the two inequality
constraints of the problem. Notice also the attribute cons_type, which is used
to indicate the type of the constraint: ConstraintTypeEnum.LTE or "LTE" for
an inequality constraint (less than or equal), and ConstraintTypeEnum.EQ or
"EQ" for an equality constraint.
Note
Then defining constraint, it is assumed that the provided func attribute will evaluate to a negative number when the constraint holds, and to a positive one when it is breached.
Problem¶
We have now defined all the components that make up the vehicle design problem.
What remains is to collect all these components and define the multiobjective
optimization problem in DESDEO. To achieve this, we use the Problem class:
from desdeo.problem import Problem
vehicle_design_problem = Problem(
name="Vehicle design problem",
description="Vehicle design problem, minimizes cost and emissions while maximizing performance.",
variables=[x_1, x_2, y],
constants=[ideal_n_cylinders, fuel_efficiency_th, safety_th],
objectives=[cost, emissions, performance],
constraints=[fuel_efficiency_constraint, safety_rating_constraint, material_composition_constraint],
)
After providing the name and the description of the problem, we provide the
variables, constants, objectives, and constraints of the problem as
lists. And that is it, we are done. We can now utilize the problem
vehicle_design_problem elsewhere in DESDEO with functionalities and tools that
require an instance of the Problem class. For example, we may solve it using
any of the interactive methods available in DESDEO.
Examples on how the defined problem may be utilized and solved in DESDEO, are
given in other examples.