Palabras clave
mixed-integer programming
simulated annealing
combinatorial optimization
Dados chinos
programación entera mixta
sobrecalentamiento simulado
recocido simulado
optimización combinatoria
Cómo citar
Resumen
En este artículo estudiamos los dados chinos, objetos matemáticos similares a los dados ordinarios pero con la diferencia que pueden repetir algunos de sus lados. Decimos que el dado A es preferido sobre el dado B si A gana con mayor frecuencia que B. Estudiamos primero la existencia de cadenas circulares de tres dados A, B, C (aquellos para los cuales A > B > C > A) utilizando un algoritmo de programación lineal entera. Luego generalizamos el problema al caso de dados n- dimensionales, esto es, dados de n caras (con n ≥ 4) y cadenas circulares de m dados (con m ≥ 3), utilizando un algoritmo de recocido simulado. Comparamos diversas funciones objetivas y obtenemos buenas soluciones al problema con algoritmos eficientes. Finalmente obtenemos un resultado teórico acerca de la existencia de cadenas circulares para el caso general.
Citas
Aarts, E.; Korst, J. (1990) Simulated Annealing and Boltzmann Machines. A Stochastic Approach to Combinatorial Optimization and Neural Computing. John Wiley & Sons, Chichester.
Bixby, R.E. (1992) “Implementing the simplex method: The initial basis”, ORSA Journal on Computing 4: 267–284.
Bixby, R.E. et al. (2002) ILOG AMPL CPLEX System, Version 8.0. User’s Guide.
Fourer, R.; Gay, D.M.; Kernighan, B.W. (2002) AMPL: A Modeling Language for Mathematical Programming. Duxbury Press-Brooks-Cole Publishing Co.
Knuth, D.E. (1981) Seminumerical Algorithms. Second edition, volume 2 of the book The Art of Computer Programming. Addison-Wesley, Reading, Mass.
Laarhoven, P.J.M. van (1988) “Theoretical and computational aspects of simulated annealing”, Centrum voor Wiskunde in Informatic, Tract 57.
Williams, H.P. (1999) Model Building in Mathematical Programming. John Wiley & Sons, Chinchester.