Dif\u00edcil de resolver<\/strong><\/p>\nLos problemas MILP tienen un n\u00famero exponencial de soluciones potenciales. Por ejemplo, digamos que un vendedor ambulante quiere encontrar el camino m\u00e1s corto para visitar varias ciudades y luego regresar a su ciudad de origen. Si hay muchas ciudades que se pueden visitar en cualquier orden, el n\u00famero de soluciones potenciales podr\u00eda ser mayor que el n\u00famero de \u00e1tomos en el universo. <\/p>\n
\u201cEstos problemas se denominan NP-dif\u00edciles, lo que significa que es muy poco probable que exista un algoritmo eficiente para resolverlos. Cuando el problema es lo suficientemente grande, s\u00f3lo podemos esperar lograr un rendimiento sub\u00f3ptimo\u201d, explica Wu.<\/p>\n
Un solucionador MILP emplea una variedad de t\u00e9cnicas y trucos pr\u00e1cticos que pueden lograr soluciones razonables en un per\u00edodo de tiempo manejable.<\/p>\n
Un solucionador t\u00edpico utiliza un enfoque de divide y vencer\u00e1s, dividiendo primero el espacio de soluciones potenciales en partes m\u00e1s peque\u00f1as con una t\u00e9cnica llamada ramificaci\u00f3n. Luego, el solucionador emplea una t\u00e9cnica llamada corte para apretar estas piezas m\u00e1s peque\u00f1as y poder buscarlas m\u00e1s r\u00e1pido.<\/p>\n
Cutting utiliza un conjunto de reglas que reducen el espacio de b\u00fasqueda sin eliminar ninguna soluci\u00f3n factible. Estas reglas se generan mediante unas pocas docenas de algoritmos, conocidos como separadores, que se han creado para diferentes tipos de problemas MILP. <\/p>\n
Wu y su equipo descubrieron que el proceso de identificar la combinaci\u00f3n ideal de algoritmos separadores a utilizar es, en s\u00ed mismo, un problema con un n\u00famero exponencial de soluciones.<\/p>\n
\u201cLa gesti\u00f3n de separadores es una parte fundamental de todo solucionador, pero es un aspecto subestimado del espacio de problemas. Una de las contribuciones de este trabajo es identificar el problema de la gesti\u00f3n de separadores como una tarea de aprendizaje autom\u00e1tico para empezar\u201d, afirma.<\/p>\n
Reducir el espacio de la soluci\u00f3n<\/strong><\/p>\nElla y sus colaboradores idearon un mecanismo de filtrado que reduce este espacio de b\u00fasqueda del separador de m\u00e1s de 130.000 combinaciones potenciales a alrededor de 20 opciones. Este mecanismo de filtrado se basa en el principio de rendimientos marginales decrecientes, que dice que el mayor beneficio provendr\u00eda de un peque\u00f1o conjunto de algoritmos, y agregar algoritmos adicionales no traer\u00e1 muchas mejoras adicionales.<\/p>\n
Luego utilizan un modelo de aprendizaje autom\u00e1tico para elegir la mejor combinaci\u00f3n de algoritmos entre las 20 opciones restantes.<\/p>\n
Este modelo se entrena con un conjunto de datos espec\u00edfico para el problema de optimizaci\u00f3n del usuario, por lo que aprende a elegir los algoritmos que mejor se adaptan a la tarea particular del usuario. Dado que una empresa como FedEx ha resuelto problemas de enrutamiento muchas veces antes, el uso de datos reales obtenidos de experiencias pasadas deber\u00eda conducir a mejores soluciones que empezar desde cero cada vez.<\/p>\n
El proceso de aprendizaje iterativo del modelo, conocido como bandidos contextuales, una forma de aprendizaje por refuerzo, implica elegir una soluci\u00f3n potencial, obtener retroalimentaci\u00f3n sobre qu\u00e9 tan buena fue y luego intentar nuevamente encontrar una soluci\u00f3n mejor.<\/p>\n
Este enfoque basado en datos aceler\u00f3 los solucionadores MILP entre un 30 y un 70 por ciento sin perder precisi\u00f3n. Adem\u00e1s, la aceleraci\u00f3n fue similar cuando la aplicaron a un solucionador de c\u00f3digo abierto m\u00e1s simple y a un solucionador comercial m\u00e1s potente.<\/p>\n
En el futuro, Wu y sus colaboradores quieren aplicar este enfoque a problemas MILP a\u00fan m\u00e1s complejos, donde la recopilaci\u00f3n de datos etiquetados para entrenar el modelo podr\u00eda resultar especialmente desafiante. Tal vez puedan entrenar el modelo en un conjunto de datos m\u00e1s peque\u00f1o y luego modificarlo para abordar un problema de optimizaci\u00f3n mucho mayor, afirma. Los investigadores tambi\u00e9n est\u00e1n interesados \u200b\u200ben interpretar el modelo aprendido para comprender mejor la eficacia de los diferentes algoritmos separadores.<\/p>\n
Esta investigaci\u00f3n cuenta con el apoyo, en parte, de Mathworks, la Fundaci\u00f3n Nacional de Ciencias (NSF), el MIT Amazon Science Hub y el Comit\u00e9 de Apoyo a la Investigaci\u00f3n del MIT.<\/p>\n<\/p><\/div>\n
[ad_2]
\n
Source link <\/a><\/p>\n","protected":false},"excerpt":{"rendered":"[ad_1] Si bien Pap\u00e1 Noel puede tener un trineo m\u00e1gico y nueve valientes renos para ayudarlo a entregar regalos, para empresas como FedEx, el problema de optimizaci\u00f3n de enrutar eficientemente los paquetes de vacaciones es tan complicado que a menudo emplean software especializado para encontrar una soluci\u00f3n. Este software, llamado solucionador de programaci\u00f3n lineal entera […]<\/p>\n","protected":false},"author":1,"featured_media":161369,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_et_pb_use_builder":"","_et_pb_old_content":"","_et_gb_content_width":"","footnotes":""},"categories":[52],"tags":[9167,3740,9169,9168],"class_list":["post-161368","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-ciencia","tag-cathy-wu","tag-logistica","tag-optimizacion-guiada-por-aprendizaje","tag-programacion-lineal-entera-mixta","et-has-post-format-content","et_post_format-et-post-format-standard"],"_links":{"self":[{"href":"https:\/\/rbnews247.com\/v1\/wp-json\/wp\/v2\/posts\/161368","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/rbnews247.com\/v1\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/rbnews247.com\/v1\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/rbnews247.com\/v1\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/rbnews247.com\/v1\/wp-json\/wp\/v2\/comments?post=161368"}],"version-history":[{"count":0,"href":"https:\/\/rbnews247.com\/v1\/wp-json\/wp\/v2\/posts\/161368\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/rbnews247.com\/v1\/wp-json\/wp\/v2\/media\/161369"}],"wp:attachment":[{"href":"https:\/\/rbnews247.com\/v1\/wp-json\/wp\/v2\/media?parent=161368"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/rbnews247.com\/v1\/wp-json\/wp\/v2\/categories?post=161368"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/rbnews247.com\/v1\/wp-json\/wp\/v2\/tags?post=161368"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}
![](\"https:\/\/news.mit.edu\/sites\/default\/files\/styles\/news_article__cover_image__original\/public\/images\/202312\/MIT-MILP-Solvers-01.jpg?itok=yEZqV-Eh\")
<\/p>\n