ROBUST OPTIMIZATION

CLICK TO FIND YOUR INSTANCE!

Robust optimization is a partly young and active research field and has been mainly developed in the last 25 years. There have been many publications that show the value of robust optimization in applications in many fields including finance, management science, supply chain, healthcare, engineering, etc.

Like all other areas of optimization, in robust optimization the theoretical parts of each research project should be completed by the experimental ones. More importantly, researchers should have the ability to compare the similar algorithms to better understand their value. To this end, it is necessary to collect different types of instances in a library so that all researchers working in the field of robust optimization can easily have access to them.

In this website, we have been working to collect the instances which are used in different publication and if the instances are not accessible, we regenerate them exactly based on their original description. Furthermore, in order to ease of usability we categorize the problems on the instance page based on four factors called problem, uncertainty, criterion and type.

  • Problem: This filter can be used to choose the desired problem. So far, we include instances for Knapsack, Selection, Shortest Path and Traveling Salesman problems and we aim to expand the library with the more well-known problems like Assignment, Spanning Tree, Set Cover, etc.
  • Uncertainty: In robust optimization problems all or some part of the coefficients could are unknown, but given through possible scenarios. The set which contains the scenarios is called the uncertainty set. Here the following uncertainty sets are considered: The discrete uncertainty set which contains N explicitly listed scenarios, interval uncertainty set where for each element i ∈ [n] a nominal value ci and a deviation di is given and the element can take any value within [ci , ci+di], the budgeted uncertainty which is similar to the interval scenario set with an additional parameter Г called the budget which controls how many elements can take value more than their nominal value. Furthermore, we are working to add instances with convex uncertainty set, ellipsoidal uncertainty set, etc.
  • Criterion: This refers to the methods can be used to solve a robust optimization problems. In decision theory under uncertainty and in particular robust optimization, different criteria are used in order to choose a solution. Two of the most important and repeatedly used criteria are the Min-Max and Min-Max Regret, which assume that the decision maker is risk averse and seeks a solution minimizing the cost or opportunity loss under the worst scenario which may occur. In the min-max setting, we need to find a single solution that performs optimally under the worst-case decision criterion; while in the min-max regret criterion, we compare against the best possible outcome under each scenario.
  • Type: Robust optimization problems can be solved in one or more stages. Here we consider one-stage, two-stage and recoverable problems. In the one-stage problem we are given the uncertainty set and should choose a solution, then the adversary choose a scenario. However, for both two-stage and recoverable problems we first choose a partial solution and wait for the adversary to choose a scenario, then we complete our solution in two-stage or choose a completely new solution in recoverable problems.

 

Note: This page is still under construction and will be updated regularly.