Revista de Matemáticas 10(1 y 2)https://hdl.handle.net/10669/128622024-03-29T05:22:37Z2024-03-29T05:22:37ZAn enumerative procedure for identifying maximal covershttps://hdl.handle.net/10669/128762021-05-02T23:20:38Z2009-02-20T00:00:00ZAn enumerative procedure for identifying maximal covers; An enumerative procedure for identifying maximal covers
In this paper we present an enumerative procedure for identifying all maximalcovers from the set of covers implied by a 0-1 knapsack constraint. The inequalitiesinduced by these maximal covers are not dominated by the inequality induced by anyother cover implied by the knapsack constraint. Thus, their identification can help totighten 0-1 models. On the other hand, we present an improvement on a proceduretaken from the literature for identifying certain maximal covers. Some comparativecomputational experiments where both procedures have been applied to randomlygenerated knapsack constraints are also reported.Keywords: Maximal covers, tighter formulations, knapsack constraints, dominated inequalities; En este trabajo se presenta un procedimiento enumerativo que identifica todos loscubrimientos maximales respecto del conjunto de cubrimientos implicados por unarestricci´on de tipo mochila con variables 0-1. Las desigualdades inducidas por estoscubrimientos maximales no est´an dominadas por la desigualdad inducida por ning´unotro cubrimiento implicado por la restricci´on de tipo mochila. As´? pues, su identificaci´on puede contribuir al reforzamiento de formulaciones de problemas de programaci´on 0-1. Por otra parte, se presenta una mejora de un procedimiento de la literaturaexistente que ´unicamente identifica ciertos cubrimientos maximales. Adem´as,se muestran algunos resultados computacionales comparativos en los que ambos procedimientosse han aplicado a restricciones de tipo mochila generadas aleatoriamente.Palabras clave: Cubrimientos maximales, formulaciones m´as fuertes, restricciones detipo mochila, desigualdades dominadas
2009-02-20T00:00:00ZProblemas matemáticos sugeridos por la genética y la ecología de poblacioneshttps://hdl.handle.net/10669/128752021-05-02T23:20:37Z2009-02-20T00:00:00ZProblemas matemáticos sugeridos por la genética y la ecología de poblaciones; Problemas matemáticos sugeridos por la genética y la ecología de poblaciones
The main goal of the present work is to show a paralellism between the equationsin Physics and Mathematics, and some problems generated in another branch whichcould be called Mathematical Biology. The article is divided in two parts; in the firstone we discuss a behavior problem of a population disseminated in a certain area,and in the second part we try to develop numerical methods in continuous integrals,solution of problems of that type.Keywords: Biomathemaics, population genetics, numerical methods.; La finalidad del presente trabajo consiste en esbozar un paralelo entre las ecuacionesde la F´?sica Matem´atica y problemas generados en otra rama del conocimientoque bien podr´?a llamarse de la Biolog´?a Matem´atica. El trabajo se divide en 2 partes;en la primera se discute un problema del comportamiento de una poblaci´on diseminadaen una cierta ´area, y en la segunda se intenta desarrollar m´etodos num´ericos enlas integrales continuales, soluci´on de problemas de dicho tipo.Palabras clave: Biomatem´aticas, gen´etica de poblaciones, m´etodos num´ericos.
2009-02-20T00:00:00ZEl problema del conjunto independiente en la selección de horarios de cursoshttps://hdl.handle.net/10669/128742021-05-02T23:20:38Z2009-02-20T00:00:00ZEl problema del conjunto independiente en la selección de horarios de cursos; El problema del conjunto independiente en la selección de horarios de cursos
Registration process at the Universidad Aut´onoma Metropolitana is such thatevery student is free to choose his/her own subjects and schedule. Success of thissystem, based in the percentage of students that obtain a place in the lectures chosen, depends principally on the characteristics of the supply of scheduled lectures, relativesto quantity and variety of timetables, as well as the oportunity of the students todo an adequate selection of lectures. An adequate selection of lectures is a subset ofthe lectures set with pairwise different subjects and timetables. The Choose LecturesProblem is to find the maximal adequate selection of lectures. A Graph Theory modelof the problem and an algorithm to solve it will be shown.Keywords: Graph Theory, Independent Set, Operations Research, Educational Timetabling.; El proceso de inscripci´on para alumnos de la Universidad Aut´onoma Metropolitanatiene como fundamento la libertad de cada alumno de seleccionar las asignaturas quecursar´a, as´? como los grupos en los que quedar´a inscrito. El ´exito de este sistema,medido en t´erminos del porcentaje de alumnos que obtienen inscripci´on en los cursosque seleccionaron, depende en gran medida tanto de las caracter´?sticas de la oferta degrupos, relativas principalmente a la cantidad y a la variedad de horarios, como dela posibilidad por parte de los alumnos de hacer una selecci´on adecuada de horariospara los cursos por los que optaron. Una selecci´on adecuada de horarios de cursos esaquella en la que las asignaturas seleccionadas tienen horarios dos a dos compatibles.El problema de selecci´on de horarios consiste en la obtenci´on de una selecci´on dehorarios adecuada de cardinalidad m´axima. En este trabajo se presentar´a un modelode Teor´?a de Gr´aficas para este problema as´? como un algoritmo de soluci´on para elmismo.Palabras clave: Calendarizaci´on, Conjunto Independiente, Investigaci´on de Operaciones,Teor´?a de Gr´aficas.
2009-02-20T00:00:00ZEl problema del multicubrimiento: una aplicación para la selección de paradas en la red de transporte de la Ciudad de Méxicohttps://hdl.handle.net/10669/128732021-05-02T23:20:38Z2009-02-20T00:00:00ZEl problema del multicubrimiento: una aplicación para la selección de paradas en la red de transporte de la Ciudad de México; El problema del multicubrimiento: una aplicación para la selección de paradas en la red de transporte de la Ciudad de México
In this paper an heuristic algorithm is developed. Its implementation is developedas well, in order to solve a sampling problem in the urban transportation network in Mexico City. The problem consist of the selection of at least 2 points (stops) on each ofthe 236 routes in the study comprising a total of 8390 stops. This problem is presentedas a multicover problem subject to 236 restrictions and 8390 binary variables. Giventhat this an NP-hard problem, it was implemented an heuristic algorithm to determinethe sampling points.Keywords: Multicover problem, heuristic methods, greedy algorithms, combinatorial optimization.; En este art´?culo se desarrolla un algoritmo heur´?stico y su correspondiente implementaci´on para resolver un problema de muestreo en la red de rutas de transporteurbano de la Ciudad de M´exico. El problema consiste en la selecci´on de al menos 2puntos (paradas de la ruta) en cada una de las 236 rutas en el estudio con un total de8390 paradas. El problema anterior, se plantea como un problema de multicubrimiento(multicover problem) con 236 restricciones y 8390 variables binarias. Este problema esun problema NP-duro, por lo que se implement´o un algoritmo heur´?stico para obtenerlos puntos de muestreo.Palabras clave: Problema de multicubrimiento, m´etodos heur´?sticos, algoritmos glotones,optimizaci´on combinatoria
2009-02-20T00:00:00Z