Medición de la eficiencia productiva: Aspectos computacionales (Tesis con mención de «Doctorado Internacional»)

  • Autor: Martín González Espinosa
  • Director/es: Juan Aparicio Baeza, José Juan López Espín
  • Defensa: 25/3/2022 - Universidad Miguel Hernández de Elche
  • Tribunal: José María Cecilia, Magdalena Kapelko, Javier Alcaraz Soria
  • Calificación: Sobresaliente cum laude
  • Ver publicaciones relacionadas

Resumen

La finalidad de los problemas de eficiencia y productividad se basan en evaluar si el uso de los recursos (entradas o inputs, en inglés) disponibles por parte de una empresa o institución pública (en general, cualquier unidad tomadora de decisiones) se corresponde o no con la forma óptima de operar de dicha entidad, generando la mayor cantidad de salidas posible (outputs en inglés). Para llevar a cabo este tipo de cálculos, varios modelos matemáticos han sido ya planteados en la literatura especializada que pueden ser utilizados, teniendo en común todos ellos que están basados en problemas de Programación Matemática, y, en particular, algunos de ellos se corresponden con problemas de Programación Matemática Lineal Mixta (Mixed Integer Linear Programming en inglés – MILP). Este tipo de problemas combinan en un mismo modelo matemático varios tipos de variables, continuas y discretas, así como numerosas restricciones, dependiendo de la naturaleza del problema, siendo estas restricciones características que pueden hacer que el proceso de resolución resulte ser algo difícil. Además, cabe destacar la característica de que estos problemas suelen ser en la práctica de tipo combinatorio (NP-duros).

A lo largo de este trabajo, el análisis y el estudio se va a centrar en un campo dentro del área de Investigación Operativa denominado Análisis Envolvente de Datos (Data Envelopment Analysis en inglés – DEA), cuyo principal objetivo es el de la estimación de fronteras de producción y la medición de la eficiencia productiva. Diferentes modelos de optimización pertenecientes a este ámbito serán puestos a prueba en esta tesis desde una perspectiva puramente computacional, siendo resueltos a través de diferentes técnicas, tanto exactas como de aproximación, analizando el rendimiento y la dificultad del mismo.

El objetivo principal de este trabajo no reside en el desarrollo y modelado de nuevos problemas en el ámbito del DEA, sino en cómo conseguir soluciones óptimas y eficientes en un tiempo razonable para ciertos problemas de naturaleza combinatoria, dado que al ser problemas de tipo NP-duro, a medida que el tamaño del problema crece, también lo hace la dificultad de obtener soluciones óptimas, sobre todo en un tiempo reducido. En este punto, centraremos la atención en el estudio y diseño de técnicas de aproximación, conocidas en la literatura como Metaheurísticas, estando muy ligadas a metodologías de Machine Learning o Artificial Inteligence. Además de estas metodologías, basadas en el aprendizaje y la mejora de las soluciones obtenidas, también se han incorporado técnicas de paralelismo, capaces de reducir de forma eficiente el tiempo necesario para obtener soluciones óptimas en problemas complejos.

WP_Query Object ( [query] => Array ( [post_type] => publicaciones [meta_key] => _wpcf_belongs_tesis_id [meta_value] => 3369 ) [query_vars] => Array ( [post_type] => publicaciones [meta_key] => _wpcf_belongs_tesis_id [meta_value] => 3369 [error] => [m] => [p] => 0 [post_parent] => [subpost] => [subpost_id] => [attachment] => [attachment_id] => 0 [name] => [pagename] => [page_id] => 0 [second] => [minute] => [hour] => [day] => 0 [monthnum] => 0 [year] => 0 [w] => 0 [category_name] => [tag] => [cat] => [tag_id] => [author] => [author_name] => [feed] => [tb] => [paged] => 0 [comments_popup] => [preview] => [s] => [sentence] => [fields] => [menu_order] => [category__in] => Array ( ) [category__not_in] => Array ( ) [category__and] => Array ( ) [post__in] => Array ( ) [post__not_in] => Array ( ) [tag__in] => Array ( ) [tag__not_in] => Array ( ) [tag__and] => Array ( ) [tag_slug__in] => Array ( ) [tag_slug__and] => Array ( ) [post_parent__in] => Array ( ) [post_parent__not_in] => Array ( ) [author__in] => Array ( ) [author__not_in] => Array ( ) [ignore_sticky_posts] => [suppress_filters] => [cache_results] => 1 [update_post_term_cache] => 1 [update_post_meta_cache] => 1 [posts_per_page] => 10 [nopaging] => [comments_per_page] => 50 [no_found_rows] => [order] => DESC ) [tax_query] => WP_Tax_Query Object ( [queries] => Array ( ) [relation] => AND [table_aliases:protected] => Array ( ) [queried_terms] => Array ( ) [primary_table] => wp_posts [primary_id_column] => ID ) [meta_query] => WP_Meta_Query Object ( [queries] => Array ( [0] => Array ( [key] => _wpcf_belongs_tesis_id [value] => 3369 ) [relation] => OR ) [relation] => AND [meta_table] => wp_postmeta [meta_id_column] => post_id [primary_table] => wp_posts [primary_id_column] => ID [table_aliases:protected] => Array ( [0] => wp_postmeta ) ) [date_query] => [request] => SELECT SQL_CALC_FOUND_ROWS wp_posts.ID FROM wp_posts INNER JOIN wp_postmeta ON ( wp_posts.ID = wp_postmeta.post_id ) WHERE 1=1 AND wp_posts.post_type = 'publicaciones' AND (wp_posts.post_status = 'publish') AND ( ( wp_postmeta.meta_key = '_wpcf_belongs_tesis_id' AND CAST(wp_postmeta.meta_value AS CHAR) = '3369' ) ) GROUP BY wp_posts.ID ORDER BY wp_posts.post_date DESC LIMIT 0, 10 [posts] => Array ( [0] => WP_Post Object ( [ID] => 3374 [post_author] => 19 [post_date] => 2022-05-23 11:55:44 [post_date_gmt] => 2022-05-23 09:55:44 [post_content] => Abstract Metaheuristic and exact methods are one of the most common tools to solve Mixed-Integer Optimization Problems (MIPs). Most of these problems are NP-hard problems, being intractable to obtain optimal solutions in a reasonable time when the size of the problem is huge. In this paper, a hybrid parallel optimization algorithm for matheuristics is studied. In this algorithm, exact and metaheuristic methods work together to solve a Mixed Integer Linear Programming (MILP) problem which is divided into two different subproblems, one of which is linear (and easier to solve by exact methods) and the other discrete (and is solved using metaheuristic methods). Even so, solving this problem has a high computational cost. The algorithm proposed follows an efficient decomposition which is based on the nature of the decision variables (continuous versus discrete). Because of the high cost of the algorithm, as this kind of problem belongs to NP-hard problems, parallelism techniques have been incorporated at different levels to reduce the computing cost. The matheuristic has been optimized both at the level of the problem division and internally. This configuration offers the opportunity to improve the computational time and the fitness function. The paper also focuses on the performance of different optimization software packages working in parallel. In particular, a comparison of two well-known optimization software packages (CPLEX and GUROBI) is performed when they work executing several simultaneous instances, solving various problems at the same time. Thus, this paper proposes and studies a two-level parallel algorithm based on message-passing (MPI) and shared memory (Open MP) schemes where the two subproblems are considered and where the linear problem is solved by using and studying optimization software packages (CPLEX and GUROBI). Experiments have also been carried out to ascertain the performance of the application using different programming paradigms (shared memory and distributed memory). [post_title] => A Parallel Algorithm for Matheuristics: A Comparison of Optimization Solvers [post_excerpt] => [post_status] => publish [comment_status] => open [ping_status] => open [post_password] => [post_name] => a-parallel-algorithm-for-matheuristics-a-comparison-of-optimization-solvers [to_ping] => [pinged] => [post_modified] => 2022-05-24 18:04:46 [post_modified_gmt] => 2022-05-24 16:04:46 [post_content_filtered] => [post_parent] => 0 [guid] => http://doctoradodecide.com/?post_type=publicaciones&p=3374 [menu_order] => 0 [post_type] => publicaciones [post_mime_type] => [comment_count] => 0 [filter] => raw ) [1] => WP_Post Object ( [ID] => 3372 [post_author] => 19 [post_date] => 2022-05-23 11:51:13 [post_date_gmt] => 2022-05-23 09:51:13 [post_content] => Abstract In this paper we use data from OECD countries participating in PISA 2012 to assess the efficiency of schools in a cross-country framework. In the analysis, and in contrast to previous applications, we consider that schools might concentrate their efforts on improving the results in one dimension of the educational output to a greater extent than in the other. To do this, we rely on non-radial efficiency measures of performance and the estimation of an educational production function based upon Data Envelopment Analysis (DEA) techniques. Specifically, DEA non-radial measures allow for identifying different levels of inefficiency for each output considered (reading and maths). In particular, we apply a non-radial measure based on Ando et al. [5] and Aparicio et al. [12]. Our results show that the majority of schools in OECD countries tend to be less efficient in reading than in mathematics. [post_title] => Using non-radial DEA to assess school efficiency in a cross-country perspective: An empirical analysis of OECD countries [post_excerpt] => [post_status] => publish [comment_status] => open [ping_status] => open [post_password] => [post_name] => using-non-radial-dea-to-assess-school-efficiency-in-a-cross-country-perspective-an-empirical-analysis-of-oecd-countries [to_ping] => [pinged] => [post_modified] => 2022-05-24 18:04:47 [post_modified_gmt] => 2022-05-24 16:04:47 [post_content_filtered] => [post_parent] => 0 [guid] => http://doctoradodecide.com/?post_type=publicaciones&p=3372 [menu_order] => 0 [post_type] => publicaciones [post_mime_type] => [comment_count] => 0 [filter] => raw ) [2] => WP_Post Object ( [ID] => 3370 [post_author] => 19 [post_date] => 2022-05-23 11:47:27 [post_date_gmt] => 2022-05-23 09:47:27 [post_content] => Abstract Mixed Integer Linear Programs (MILPs) are usually NP-hard mathematical programming problems, which present difficulties to obtain optimal solutions in a reasonable time for large-scale models. Nowadays, metaheuristics are one of the potential tools for solving this type of problems in any context. In this paper, we focus our attention on MILPs in the specific framework of Data Envelopment Analysis (DEA), where the determination of a score of technical efficiency of a set of Decision Making Units (DMUs) is one of the main objectives. In particular, we propose a new hyper-matheuristic grounded on a MILP-based decomposition in which the optimization problem is divided into two hierarchical subproblems. The new approach decomposes the model into discrete and continuous variables, treating each subproblem through different optimization methods. In particular, metaheuristics are used for dealing with the discrete variables, whereas exact methods are used for the set of continuous variables. The metaheuristics use an indirect representation that encodes an incomplete solution for the problem, whereas the exact method is applied to decode the solution and generate a complete solution. The experimental results, based on simulated data in the context of Data Envelopment Analysis, show that the solutions obtained through the new approach outperform those found by solving the problem globally using a metaheuristic method. Finally, regarding the new hyper-matheuristic scheme, the best algorithm selection is found for a set of cooperative metaheuristics and exact optimization algorithms. [post_title] => A Hyper-Matheuristic Approach for Solving Mixed Integer Linear Optimization Models in the context of Data Envelopment Analysis [post_excerpt] => [post_status] => publish [comment_status] => open [ping_status] => open [post_password] => [post_name] => a-hyper-matheuristic-approach-for-solving-mixed-integer-linear-optimization-models-in-the-context-of-data-envelopment-analysis [to_ping] => [pinged] => [post_modified] => 2022-05-24 18:04:47 [post_modified_gmt] => 2022-05-24 16:04:47 [post_content_filtered] => [post_parent] => 0 [guid] => http://doctoradodecide.com/?post_type=publicaciones&p=3370 [menu_order] => 0 [post_type] => publicaciones [post_mime_type] => [comment_count] => 0 [filter] => raw ) ) [post_count] => 3 [current_post] => -1 [in_the_loop] => [post] => WP_Post Object ( [ID] => 3374 [post_author] => 19 [post_date] => 2022-05-23 11:55:44 [post_date_gmt] => 2022-05-23 09:55:44 [post_content] => Abstract Metaheuristic and exact methods are one of the most common tools to solve Mixed-Integer Optimization Problems (MIPs). Most of these problems are NP-hard problems, being intractable to obtain optimal solutions in a reasonable time when the size of the problem is huge. In this paper, a hybrid parallel optimization algorithm for matheuristics is studied. In this algorithm, exact and metaheuristic methods work together to solve a Mixed Integer Linear Programming (MILP) problem which is divided into two different subproblems, one of which is linear (and easier to solve by exact methods) and the other discrete (and is solved using metaheuristic methods). Even so, solving this problem has a high computational cost. The algorithm proposed follows an efficient decomposition which is based on the nature of the decision variables (continuous versus discrete). Because of the high cost of the algorithm, as this kind of problem belongs to NP-hard problems, parallelism techniques have been incorporated at different levels to reduce the computing cost. The matheuristic has been optimized both at the level of the problem division and internally. This configuration offers the opportunity to improve the computational time and the fitness function. The paper also focuses on the performance of different optimization software packages working in parallel. In particular, a comparison of two well-known optimization software packages (CPLEX and GUROBI) is performed when they work executing several simultaneous instances, solving various problems at the same time. Thus, this paper proposes and studies a two-level parallel algorithm based on message-passing (MPI) and shared memory (Open MP) schemes where the two subproblems are considered and where the linear problem is solved by using and studying optimization software packages (CPLEX and GUROBI). Experiments have also been carried out to ascertain the performance of the application using different programming paradigms (shared memory and distributed memory). [post_title] => A Parallel Algorithm for Matheuristics: A Comparison of Optimization Solvers [post_excerpt] => [post_status] => publish [comment_status] => open [ping_status] => open [post_password] => [post_name] => a-parallel-algorithm-for-matheuristics-a-comparison-of-optimization-solvers [to_ping] => [pinged] => [post_modified] => 2022-05-24 18:04:46 [post_modified_gmt] => 2022-05-24 16:04:46 [post_content_filtered] => [post_parent] => 0 [guid] => http://doctoradodecide.com/?post_type=publicaciones&p=3374 [menu_order] => 0 [post_type] => publicaciones [post_mime_type] => [comment_count] => 0 [filter] => raw ) [comment_count] => 0 [current_comment] => -1 [found_posts] => 3 [max_num_pages] => 1 [max_num_comment_pages] => 0 [is_single] => [is_preview] => [is_page] => [is_archive] => 1 [is_date] => [is_year] => [is_month] => [is_day] => [is_time] => [is_author] => [is_category] => [is_tag] => [is_tax] => [is_search] => [is_feed] => [is_comment_feed] => [is_trackback] => [is_home] => [is_404] => [is_comments_popup] => [is_paged] => [is_admin] => [is_attachment] => [is_singular] => [is_robots] => [is_posts_page] => [is_post_type_archive] => 1 [query_vars_hash:WP_Query:private] => fed3e36c36bae7febb740e892d67221f [query_vars_changed:WP_Query:private] => [thumbnails_cached] => [stopwords:WP_Query:private] => )

Publicaciones relacionadas

Array ( [_edit_lock] => Array ( [0] => 1653408287:19 ) [_edit_last] => Array ( [0] => 19 ) [_wpcf-autor-sort-order] => Array ( [0] => a:1:{i:0;i:24712;} ) [wpcf-autor] => Array ( [0] => Martín González Espinosa ) [wpcf-director] => Array ( [0] => Juan Aparicio Baeza, José Juan López Espín ) [wpcf-fecha-defensa] => Array ( [0] => 1648166400 ) [wpcf-lugar] => Array ( [0] => Universidad Miguel Hernández de Elche ) [wpcf-tribunal] => Array ( [0] => José María Cecilia Magdalena Kapelko Javier Alcaraz Soria ) [wpcf-calificacion] => Array ( [0] => 10 ) )