Open access peer-reviewed chapter

Robust Optimization: Concepts and Applications

By José García and Alvaro Peña

Submitted: October 16th 2017Reviewed: February 13th 2018Published: July 18th 2018

DOI: 10.5772/intechopen.75381

Downloaded: 516

Abstract

Robust optimization is an emerging area in research that allows addressing different optimization problems and specifically industrial optimization problems where there is a degree of uncertainty in some of the variables involved. There are several ways to apply robust optimization and the choice of form is typical of the problem that is being solved. In this paper, the basic concepts of robust optimization are developed, the different types of robustness are defined in detail, the main areas in which it has been applied are described and finally, the future lines of research that appear in this area are included.

Keywords

  • optimization
  • robustness
  • uncertainly
  • uncertainty modeling

1. Introduction

Nowadays, using the technologies and techniques associated with the Internet of things, Big Data and artificial intelligence, we are able to capture and process enormous and varied volumes of data. Examples of the above can be observed in different disciplines such as transport [1, 2], mining [3] and agriculture [4] among others. However, in the area of optimization, many problems still work at the level of reference instances [5, 6, 7, 8]. To solve real optimization problems, we must consider that these are generally multi-variable problems with restrictions and trade-off between them. In many instances, when a problem is modeled, a point that is not taken into consideration is the uncertainty to which the system is subject. In this sense, our solution can be submitted to questions of the type: How feasible is this solution according to the different scenarios? What is the optimality of this solution? How strict should the treatment of uncertainty be? One way to approach uncertainty is to consider the robustness of the solution. However, the definition of robustness is not trivial and there are several definitions. Ideally, you want to get the best solution and also the most robust one but usually there is a trade-off between these two concepts [9]. Due to the importance and particularity for each problem of this trade-off between the quality and robustness of the solution, a series of definitions have been generated and a series of methods developed to adequately address or estimate the trade-off [10, 11].

Because each problem has its own level of demand regarding the quality of the solution and its treatment with respect to its robustness, it is difficult to provide a single definition of robustness. In some cases, our solution could be considered robust if under certain conditions of the search space or under certain operational conditions, the solution behaves reasonably with respect to its quality, feasibility or optimality. Under other conditions where the management of uncertainty is very strict, the most appropriate result is associated with scenarios that consider the worst case [12].

On the other hand, it has been methodologically argued [13] that instead of transforming and solving the optimization problem with uncertainty in a robust problem, this can be solved in two stages considering the robustness as a separate objective [13]. The argument is based on the fact that a separate analysis allows obtaining more information and understanding about the solution and its robustness, facilitating the decision-making process. On the other hand, considering robustness as part of the problem has advantages over implementation, computational cost and alternatives to solve the problem. In the latter case, modeling the choice of scenarios and the measure of robustness is essential [14].

The aforementioned discussion indicates that the concepts of robustness are still in the process of maturation and there is no clear methodology on how to address robust problems. There are conceptual, computational and application challenges in the area of robust optimization. Usually, the few state of the art reviews found about robust optimization, focus on identifying what areas and types of problems have been addressed. In this article, as a starting point, we present a collection of the different definitions and models with which robust optimization problems have been addressed. Knowledge of the different models used in robust optimization is essential for a proper understanding of the field. Once the main concepts are defined, we proceed to provide an update on the main robust optimization works that have been carried out over the last few years. In Section 2, we will describe the basic concepts associated with uncertainty. We will describe the main robustness models in Section 3. Finally, in Section 4, we will describe the main areas of application.

2. Fundamental concepts

Suppose an engineer who must make constant decisions and face the difficulty of multidimensional problems with some degree of ambiguity or errors in the parameters to analyze and some kind of stochastic uncertainty of the process and its environment. Then this engineer must also determine if the proposed solution is robust. This means that the solution is feasible to apply for any parameter scenario and stochastic uncertainty and that this feasibility remains close to the optimality condition. Then two fundamental concepts appear: the uncertainty of the feasibility of the solution and the uncertainty of the objective value of the function.

2.1. Uncertainty in the feasibility of the solution

Ideally, the engineer would like his or her solution to be feasible for any value of the parameters analyzed; however, this feasibility has consequences. The first consequence corresponds to having a significant computational cost when considering all the possible parameter values. The second consequence is related to the deterioration in the quality of the solution. The more demanding it is with regard to the feasibility of the parameters, the greater the probability of moving away from optimality. Therefore, there is a trade-off, which is related to the problem that is being solved. Then solutions in the area of control theory related to equipment failures should be much stricter regarding the feasibility of the solution than solutions obtained in marketing areas where the effect on a set of clients is not so critical. Therefore, the choice of the uncertainty set plays a fundamental role in the feasibility of solving the problem and in the quality of the solution obtained.

2.2. Uncertainty in the optimality of the solution

It may happen that depending on the set of uncertainty chosen, the optimality of the solution is altered. In this case, robust optimization tries to obtain a solution that performs adequately in the different scenarios; however, all scenarios do not require the same treatment with respect to optimality. Due to the above, in the literature, we can find different concepts of robustness; among the most mentioned are: strict robustness [15], cardinality constrained robustness [16], adjustable robustness [17], lightweight robustness [18], soft robustness [19], lexicographic robustness and regret robustness.

2.3. Uncertainty in the optimization problem

Each real optimization problem suffers from some type of uncertainty that are mainly caused by uncertainty at the level of the measurements or by uncertainties due to changes in the environment of the system. The first case we will refer to microscopic uncertainties and the second will be macroscopic. The optimization problem can be approached in a standard way through a nominal scenario which would describe, for example, the most typical case or an average case. However, in general, the most probable scenario is not trivial to obtain and for some problems, having a more frequent scenario is not the natural way to approach the problem [20]. An optimization problem with constraints can be formally written as shown in Eq. (1).

minfxs.t.Fx0xS,E1

where F:RnRmdescribes a problem of n dimensions with m constraints. f:RnRis the objective function and SRnis the search space. Our next step is to formalize the uncertainty in the optimization problem. Suppose ξRkcorresponds to a scenario that could occur in our real problem. Hence, our optimization problem considering the uncertainty scenario ξ, is written in Eq. (2):

minfxξs.t.Fxξ0xS,E2

In most problems, it is not known exactly what the value of ξis, but if it is clear that the problem falls on an uncertainty set URk, which represents the scenarios that are enough to consider. Then we have a family of optimization problems given by the pair PξξU. A fundamental objective of robust optimization corresponds to turn this family of problems into a single problem of optimization, where the choice of the set of uncertainty is fundamental for the result and complexity of the problem. For an adequate treatment of the problem of uncertainty, it is fundamental to give structure to the set U. In literature, it is common to find the following types:

  1. Finite uncertainty U=ξ1ξl.

  2. Interval-based uncertainty U=ξ1,ξ̂1××ξk,ξ̂k.

  3. Norm-based uncertainty U=ξRk:ξξ̂r.

  4. Polytopic uncertainty U=convξ1ξl.

  5. Constraint-wise uncertainly U=U1××Um, where Uiaffects only the constraint i.

3. Robustness models

This section aims to formally define the main concepts of robustness used to solve optimization problems with uncertainty. In each of the ways to approach robustness, the intuition that exists behind the definition is described; later, the sets that model the uncertainty are characterized and then the problem is written in its robust version. Finally, articles where the definition has been used are referenced.

3.1. Strict robustness

Let xinSbe a solution to the optimization problem with uncertainty PξξU. The solution is strict if xis feasible for all possible scenarios of U, that is, if Fxξ0for all ξU. This approach is the most intuitive when trying to solve the optimization problem in a robust way. Formally, consider the set of all possible strictly robust solutions with respect to the uncertainty set Ugiven by:

Fξ=xS:Fxξ0RU=ξUFξE3

Then the strict robust problem corresponds to the problem formulated in Eq. (4),

minsupξUfxξs.t.xRUxSE4

To the best of our knowledge, the first to use strict robustness was Soster in [21], where he applied uncertainty to convex sets, solving the problem using linear programming. Later, this work was extended and placed in a theoretical framework in the articles [22, 23]. The essence of strict robustness is that all scenarios can occur and all of them have an important criticality. In real problems, this type of robustness is necessary in critical systems where a failure is not tolerable. For example, the case of air planes and nuclear plants. However, in other types of problems, such as revenue management, public or scheduling, this type of robustness can be relaxed.

3.2. Cardinality constrained robustness

One way to relax the strict robustness is to restrict the space of uncertainty. There are several ways to achieve this restriction. In cardinality constrained robustness, the property is used that it is unlikely that all the uncertainty parameters change at the same time when analyzing the worst case. Then, we can restrict the cardinality of the uncertainty space by varying only some parameters; the others are modeled with their representative values.

Let X=x1xnand b1x1,,bnxncbe a solution and restriction respectively of the optimization problem. Let U=bRn:bib̂idib̂i+dii=1n; then, the cardinality constrained robustness is described in Eq. (5).

i=1nb̂ixi+maxR1n,R=γiRdixicE5

This approach was conceptualized by Bertsimas and Sim [16] for continuous problems. Later, this approach was extended to combinatorial problems in the articles [24, 25].

3.3. Adjustable robustness

Another way to relax the space of uncertainty of strict robustness, corresponds to divide the space into groups of variables. A first group will be called here and now variables. These variables correspond to variables that must be evaluated before the scenario ξUis determined and the wait and see variables, which can be determined once the scenario ξis known.

Let Xbe one point of our search space; then, X=uvcan be divided into uS1Rn1and vS2Rn2where n1+n2=n. Then the variables u correspond to the group here and now variables and the variables v to the group wait and see variables. Formally, this is written in Eq. (6).

minfuvξFuvξ0uvS1×S2E6

Then once we have fixed the variables here and now, we must make sure that for any of the selected ξUscenarios, there is vS2such that uvis feasible for ξ. Let PS1Fξ, defined in Eq. (7) be the projection of Fξover S1.

PS1FξuS1:vS2s.t.uvFξE7

where Fξcorresponds to the solution space that complies with the constraints defined in Eq. (3). Then, the set of solutions for the split robustness is given by:

R=uS1:ξUvS2s.t.uvFξ=ξUPS1FξE8

Given a u, the worst case wfor some specific u with respect to the set of solutions R, is given by Eq. (9).

wRu=supξUinfv:uvFξfuvξE9

And therefore, the split robustness is given by Eq. (10).

minwRu:uRE10

The first one to introduce the concept of adjustable robustness was Ben Tal et al. [17] applied to uncertainly problems in linear programming. However, the concept has continued to develop and adapt and nowadays, applications are being seen in portfolio selection [26], in power systems [27], capacity extension planning [28], aperiodic timetabling [29], among others.

3.4. Light robustness

A completely different way of relaxing the concept of strict robustness corresponds to instead of reducing the space of uncertainty, we can relax the constraints in favor of the quality of the solution. This new concept that is called light robustness, this concept considers as a fundamental hypothesis that if we are able to adequately solve the optimization problem considering the nominal (or average) case, the solution should not be bad and basically, we can concentrate on finding relatively close solutions of the fitness that also fulfill in the best possible way the restrictions of the problem considering all ξU. Formally, light robustness is detailed in Eq. (11).

mini=1kwiλis.t.fxξ̂fξ̂+ρFxξλ,ξUxS,λRkE11

The concept of light robustness was introduced by Fischetti and Monaci [30], the main objective of its new definition was to allow a trade-off between robustness and quality of the solution. A constraint is added by entering the parameter ρ. This parameter forces the solution to have a certain closeness to the solution for the nominal case represented by ξ̂. Because there is a trade-off between quality and robustness, to allow this closeness of the nominal case, it is necessary to relax the original constraints. This is done with the λfactor, where we finally want to find the best set of coefficients that relax our solution.

Originally, the concept of light robustness was conceived to be applied to problems of linear programming [30] and specifically, in time optimizations in Italian single-line instances. Later, in [31] light robustness was applied to determine the best route to traveling in a public transport network in Germany. Later in [18] the concept was generalized taking into account any optimization problem and any set of uncertainty.

3.5. Regret robustness

The regret robustness described by [32] uses a way to relax the problem through the objective function. Let fξbe the best target value in the scenario ξU. Instead of minimizing the worst-case performance of a solution, it minimizes the difference to the objective function of the best solution that would have been possible in a scenario. The regret robustness formulation is shown Eq. (12).

minsupξUfxξfξs.t.Fx0xSE12

Today, we see used in the concept of regret robustness in different areas. In [33], it was used in portfolio optimization problems. In safety investment problems, it was used in [34]. In [35] it was used to solve evacuation planning models.

3.6. Recoverable robustness

Recoverable robustness uses the concept of recovery algorithm and, like adjustable robustness, it obtains the solution in two stages. Give a family of algorithms A. A solution x is recovery robust with respect to Aif it exists for every scenario ξU, an algorithm AAsuch that Aapplied to the solution x and a scenario ξallows you to build a solution AxξFξ. Then the optimization problem in its robust form is written by Eq. (13):

minxAFξ×Afxs.t.AxξFξ,ξUE13

The concept of recoverable robustness was developed in the article [36] applied to shunting problems and later refined in [37] applying recoverable robustness to railway problems with linear programming. Today, we find the concept of recoverable robustness applied to location planning [38], scheduling and delivering routing [39], allocation and network design problems [40], robust traveling salesman problem [41] and transit network design [42], among others.

4. Application areas of robust optimization

In this section, we will describe some examples where robust optimization has been applied. Mainly identified areas have been logistics, finance, water management, energy management and machine learning.

4.1. Energy management

Energy management has received significant attention with respect to robust optimization. In [43] a strategic planning model applied to the integrated oil chain was designed. For the design, it was considered as sources of uncertainty: crude oil production, demand for refined products and market prices. The robust version of the demands for a power plant problem was studied in [44]. In this article the phases of unit commitment and economic dispatch were considered to minimize the local cost. A robust model of energy distribution under uncertainties with respect to wind energy was studied in [45]. In this article, it was shown that the proposed method can be solved in suitable times in addition to being able to effectively capture the ambiguous distribution of wind power generation. In [46], the configuration of the energy consumption of household appliances under the uncertainty of manually operated devices (MOAs) was modeled as a problem of robust optimization. When evaluating all the possible cases of the energy of MOAs, the traditional approach was chosen, that is, using the worst case with the intention of reducing the payment of electricity for all the household appliances. To determine the reduction in the payment, the price of electricity in real time was considered as information in addition to the inclining block rate.

4.2. Water management

In [47] robust optimization was used to handle the uncertainties of water planning resources. In [48] the authors developed a new methodology for the optimizing daily operations of pumping stations. This methodology takes into consideration the fact that a water distribution system is actually unavoidably affected by uncertainties. A multi-objective robust decision-making approach was developed in [49]. This approach supports seasonal water management. In [51], a comparison of Robust Optimization and Info-Gap Methods for Water Resource Management under Deep Uncertainty was made. A multi-objective design of water distribution systems under uncertainty was developed in [50]. The main objectives are (1) minimize the total water distribution system (WDS) design cost and (2) maximize WDS robustness. In the article, the WDS robustness is defined as the probability of simultaneously satisfying minimum pressure head constraints at all nodes in the network.

4.3. Machine learning

In [52] regularized support vector machines (SVMs) were considered, and they were shown to be equivalent to a robust formulation of the problem. The authors show that this equivalence between robust optimization and regularization has implications for both algorithms and analysis. The equivalence of robustness and regularization provides a robust optimization interpretation for the success of regularized SVMs. On the other hand, Fertis in his doctoral thesis [53], studied the connection between regularizations like Lazo and robustness. Specifically, he showed that in classical regression, regularized estimators like lasso can be obtained by applying robust optimization to the classical least squares problem. He discovers an explicit connection between the size and the structure of the uncertainty used in the robust estimator, with the coefficient and the kind of norm used in regularization. Xu et al. [54], investigated a probabilistic interpretation of robust optimization. They established a connection between robust optimization and distributionally robust stochastic programming (DRSP). In the article, they showed that the solution to any robust optimization problem is also a solution to a DRSP problem. In [55] the problem of constructing robust classifiers when the training is subject to uncertainty was studied. The problem is posed by a chance-constrained programming, which ensures that the uncertainty of the data is correctly defined with high probability.

4.4. Logistics

In the area of logistics problems such as the traveling salesman and routing problem have been explored in their robust versions. A Swarm intelligence system was designed in [56] to solve the vehicle routing problem with time windows and uncertain travel times. The uncertainty here models the perturbation in the data. This perturbation, is caused by the effects of unpredictable events, such as traffic jams, road building, etc. In the article, the authors proposed a heuristic approach using ant colony optimization as a metaheuristic. In [57], the open vehicle routing problem with uncertain demands was studied. In this problem, the vehicles have as an additional function that they do not necessarily return to their original locations after delivering the products to the customers. First, the authors modeled the demand of the clients as specific sets of limited uncertainty with expected values of demand and nominal values. Having the sets modeled, they later proposed a robust optimization model that aims to minimize transport costs and unsatisfied demands on the specific uncertainty sets defined. The robust vehicle routing problem with time windows was solved in [58]. They proposed two new formulations for the robust problem, each based on a different robust approach. They proposed two new formulations for the robust problem, each based on a different robust approach. The first formulation uses adjustable robustness with the aim of extending the well-known formulation of resource inequalities. The second formulation generalizes a path inequalities formulation to the uncertain context. In this case, uncertainty is modeled in the formulation of the problem. In [41], an uncertain traveling salesman problem was developed. In this problem, the distances between the nodes are not exactly known, but they can be obtained from a set of uncertainties of possible scenarios. This set of uncertainties is modeled as intervals, including an additional limit associated with the number of distances that can deviate from their expected nominal values. In the study, a recoverable robust model was proposed. This model allows a tour to change only a limited number of borders once a scenario is known; all these with the goal of minimizing the complexity in calculations. The robust traveling salesman problem with interval data was studied in [59]. In the article, travel times are specified as a range of possible values. They applied the robust deviation criterion to drive the optimization over the interval data problem thus obtained.

Another interesting group of problems in the logistics area corresponds to facility location problems. The robust formulation of these problems aims to obtain an optimal design of a system considering uncertainty. The authors introduce a robust optimization-based approach to obtain some capacity expansion solutions that are not sensitive to this uncertainty. In this area, we highlight the work carried out by [60], where they considered the question of how to make a decision about capacity expansions for a network flow problem that is subject to demand and travel time uncertainty. The authors introduce a robust optimization-based approach to obtain some capacity expansion solutions that are not sensitive to this uncertainty. They show that the robust modeled solution is a computationally tractable problem when considering general uncertainty sets together with reasonable conditions for network flow applications. Another interesting problem in this area is the robust transmission expansion planning. In [61] the authors address the problem of transmission expansion planning, considering uncertainties in the electric power system. They consider varied sources of uncertainty such as: the growth of future demand, the availability of generation facilities, geographical characterization within the electric power system. A robust adaptive optimization model is used to obtain investment decisions with the objective of minimizing the total costs of the system and anticipating the worst-case materialization of the uncertain parameters within a uncertainty set.

4.5. Public goods

Public goods can be understood as a merchandise or service that is provided non-profit to all members of a society. This merchandise or service, can be provided by the government, an individual or an organization. When we consider public goods and robust optimization, interesting applications appear. An interesting first application corresponds to radiation therapy. When a radiation therapy examination is performed, there are uncertainties that are fundamental to consider in defining the correct treatment in patients with cancer. In this context, addressing problems through robust optimization makes a lot of sense. In [62] the authors constructed an uncertainty model of the movement of respiration based on probability density functions. These functions allowed them to robustly model the optimization of intensity-modulated radiation therapy.

Another interesting implementation associated with the application of robust optimization to public goods corresponds to intrahospital transport. Intrahospital transport is often required for reasons associated with a diagnosis or some therapy that the patient must perform. Depending on the design of the hospital, transportation between the nursing rooms and the service units is provided by ambulances or by trained personnel accompanying patients on foot. When the hospital is large, the patient transport service is often poorly managed and there is no associated flow coordination; on the other hand, there is no clarity of all the necessary transports since they are dependent on the diagnoses. In [63] the authors address the problem of defining robustness to patient flow management in the context of optimized patient transport in hospitals. In [64] a methodology was proposed to obtain a robust logistics plan to mitigate the uncertainty of the demand for humanitarian relief supply chains. More specifically, the authors formulated the problem as a robust optimization problem with the objective of dynamically assigning emergency response and generate evacuation traffic flow, all this in the context of time-dependent demand uncertainty.

5. Discussion and conclusions

In this article, we have carefully reviewed the different definitions that have appeared in the literature to address the concept of robust optimization. We have taken special care to formalize each of the definitions and cite specific examples where they have been used. Subsequently, a review was made in areas where robust optimization has been applied. In particular, the areas of water management, energy management, machine learning, logistics and public goods stood out. With the advent of the concepts and technologies associated with the Internet of Things and Big Data, it is expected that the problems described above have a greater amount of data to build more robust models; however, this brings challenges regarding the complexity of the algorithms, in addition to the learning and operation of these in real time.

When we analyze the research works developed in the area of robust optimization, we found that there is a lack of a formal argument that clearly defines the uncertainty set to be used to solve the problem in a robust way. Usually, the choice is guided by business intuition together with the need to adapt the uncertainty set to solve the problem in a reasonable time.

Therefore, there is an important space to develop quantitative studies to determine what kind of robustness and uncertainty set should be used to solve a problem. Identifying how different uncertainty sets behave for a defined problem is fundamental. To be able to answer questions such as: How is the quality of the solutions perturbed with the choice of the uncertainty set?, Is this perturbation important for the problem that is being solved?, How is the convergence of the algorithm altered against different sets of uncertainty?, Can we classify problems according to some degree of robustness? Can this classification be related to the type of uncertainty to be used? The answer to these questions allows developing a methodology that allows identifying which is the robustness required by the problem, what type of uncertainty set should be chosen and how is the behavior of the algorithm in terms of quality of its results and convergence.

As future lines of research in the area of robust optimization, we see that considering these group of definitions together with the different applications mentioned earlier, we can work on developing a methodology that gives a specific problem, allows in a simple way to identify which definition is the most appropriate and which methods they are the most appropriate to solve the problem at reasonable times.

Regarding the tractability of robust problems, we have not found solutions where the hybridization of metaheuristics with other techniques is exploited such as integration with mathematical programming, with simulations or integration with machine learning, all these with the goal of improving convergence times of algorithms.

Particularly, according to our experience in the integration of machine learning and metaheuristics, a line that must be explored corresponds to the use of a general scheme of integration of these two areas through the use of metalearning techniques. Considering that we have a set of algorithms or settings of some algorithm, we use a mechanism that selects the best algorithm or settings for given an instance to obtain the best convergence and results. Furthermore, the use of reinforced learning can be explored to enrich the meta-model with the new results generated.

How to cite and reference

Link to this chapter Copy to clipboard

Cite this chapter Copy to clipboard

José García and Alvaro Peña (July 18th 2018). Robust Optimization: Concepts and Applications, Nature-inspired Methods for Stochastic, Robust and Dynamic Optimization, Javier Del Ser and Eneko Osaba, IntechOpen, DOI: 10.5772/intechopen.75381. Available from:

chapter statistics

516total chapter downloads

2Crossref citations

More statistics for editors and authors

Login to your personal dashboard for more detailed statistics on your publications.

Access personal reporting

Related Content

This Book

Next chapter

Evaluation of Non-Parametric Selection Mechanisms in Evolutionary Computation: A Case Study for the Machine Scheduling Problem

By Maxim A. Dulebenets

Related Book

First chapter

A Tutorial on H.264/SVC Scalable Video Coding and its Tradeoff between Quality, Coding Efficiency and Performance

By Iraide Unanue, Inigo Urteaga, Ronaldo Husemann, Javier Del Ser, Valter Roesler, Aitor Rodriguez and Pedro Sanchez

We are IntechOpen, the world's leading publisher of Open Access books. Built by scientists, for scientists. Our readership spans scientists, professors, researchers, librarians, and students, as well as business professionals. We share our knowledge and peer-reveiwed research papers with libraries, scientific and engineering societies, and also work with corporate R&D departments and government entities.

More about us