An enumerative algorithm for computing all possibly optimal solutions to an interval LP

• Carla Oliveira ^[3] ; Carlos Henggeler Antunes ^[1] ; Carlos Barrico ^[2]
  1. [1] Universidade de Coimbra

     Universidade de Coimbra

     Coimbra (Sé Nova), Portugal

     
  2. [2] Universidade da Beira Interior

     Universidade da Beira Interior

     Covilhã (Conceição), Portugal

     
  3. [3] ISCAC Coimbra, Portugal

  Mostrar afiliaciones +
• Localización: Top, ISSN-e 1863-8279, ISSN 1134-5764, Vol. 22, Nº. 2, 2014, págs. 530-542
• Idioma: inglés
• Enlaces
  • Texto completo (pdf)
• Resumen

  • Interval programming techniques are a valuable approach for tackling uncertainty in mathematical programming models, because they only require the knowledge of the feasible range of variation of the model coefficients. Nevertheless, the use of these techniques has some limitations, namely when the number of decision variables with interval coefficients is high since the number of objective functions at stake in the sub-problem for testing the (weak) efficiency of each non-basic variable may be easily out of an acceptable computational effort. A similar problem may arise with the number of sub-problems for testing the multi-parametric optimality of each solution obtained (that is, to check whether the solution is possibly optimal or not) and the multi-parametric optimality of each edge by using the all emanating edges algorithm. An alternative algorithm is suggested that allows obtaining all possibly optimal solutions, which fulfill the formal criteria of optimality in a feasible bounded region.