Algoritmo de Generación de Columnas : Una revisión desde su aplicación al problema de asignación de cupos escolares
RESUMEN: El algoritmo de generación de columnas (GC) se cita usualmente como alternativa para la solución de problemas de optimización de gran escala; este artículo aborda la presentación de dicho algoritmo en el contexto de la asignación de cupos escolares en el sistema de educación pública del dis...
- Autores:
-
Maya Duque, Pablo Andrés
- Tipo de recurso:
- Article of investigation
- Fecha de publicación:
- 2008
- Institución:
- Universidad de Antioquia
- Repositorio:
- Repositorio UdeA
- Idioma:
- spa
- OAI Identifier:
- oai:bibliotecadigital.udea.edu.co:10495/4950
- Acceso en línea:
- http://hdl.handle.net/10495/4950
- Palabra clave:
- Algoritmo de generación de columnas
Algoritmos
Algoritmo Branch and Price
- Rights
- openAccess
- License
- https://creativecommons.org/licenses/by-nc-sa/2.5/co/
| id |
UDEA2_7e190f57a6ac9e495e9fafbb7ce667fd |
|---|---|
| oai_identifier_str |
oai:bibliotecadigital.udea.edu.co:10495/4950 |
| network_acronym_str |
UDEA2 |
| network_name_str |
Repositorio UdeA |
| repository_id_str |
|
| dc.title.spa.fl_str_mv |
Algoritmo de Generación de Columnas : Una revisión desde su aplicación al problema de asignación de cupos escolares |
| dc.title.translated.spa.fl_str_mv |
Column Generation Algorithm : A revision from its application to the Student Assignation Problem |
| title |
Algoritmo de Generación de Columnas : Una revisión desde su aplicación al problema de asignación de cupos escolares |
| spellingShingle |
Algoritmo de Generación de Columnas : Una revisión desde su aplicación al problema de asignación de cupos escolares Algoritmo de generación de columnas Algoritmos Algoritmo Branch and Price |
| title_short |
Algoritmo de Generación de Columnas : Una revisión desde su aplicación al problema de asignación de cupos escolares |
| title_full |
Algoritmo de Generación de Columnas : Una revisión desde su aplicación al problema de asignación de cupos escolares |
| title_fullStr |
Algoritmo de Generación de Columnas : Una revisión desde su aplicación al problema de asignación de cupos escolares |
| title_full_unstemmed |
Algoritmo de Generación de Columnas : Una revisión desde su aplicación al problema de asignación de cupos escolares |
| title_sort |
Algoritmo de Generación de Columnas : Una revisión desde su aplicación al problema de asignación de cupos escolares |
| dc.creator.fl_str_mv |
Maya Duque, Pablo Andrés |
| dc.contributor.author.none.fl_str_mv |
Maya Duque, Pablo Andrés |
| dc.subject.none.fl_str_mv |
Algoritmo de generación de columnas Algoritmos Algoritmo Branch and Price |
| topic |
Algoritmo de generación de columnas Algoritmos Algoritmo Branch and Price |
| description |
RESUMEN: El algoritmo de generación de columnas (GC) se cita usualmente como alternativa para la solución de problemas de optimización de gran escala; este artículo aborda la presentación de dicho algoritmo en el contexto de la asignación de cupos escolares en el sistema de educación pública del distrito de Bogotá. Se discuten algunas de las falencias evidenciadas en la puesta en práctica del algoritmo, presentando estrategias para enfrentarlas. Se ilustra además, la forma como la generación de columnas se acopla dentro del algoritmo Branch and Price para dar solución a problemas de mayor complejidad. |
| publishDate |
2008 |
| dc.date.issued.none.fl_str_mv |
2008 |
| dc.date.accessioned.none.fl_str_mv |
2016-10-08T22:37:56Z |
| dc.date.available.none.fl_str_mv |
2016-10-08T22:37:56Z |
| dc.type.spa.fl_str_mv |
Artículo de investigación |
| dc.type.coar.spa.fl_str_mv |
http://purl.org/coar/resource_type/c_2df8fbb1 |
| dc.type.redcol.spa.fl_str_mv |
https://purl.org/redcol/resource_type/ART |
| dc.type.coarversion.spa.fl_str_mv |
http://purl.org/coar/version/c_970fb48d4fbd8a85 |
| dc.type.driver.spa.fl_str_mv |
info:eu-repo/semantics/article |
| dc.type.version.spa.fl_str_mv |
info:eu-repo/semantics/publishedVersion |
| format |
http://purl.org/coar/resource_type/c_2df8fbb1 |
| status_str |
publishedVersion |
| dc.identifier.citation.spa.fl_str_mv |
P. A. Maya, "Algoritmo de Generación de Columnas: Una revisión desde su aplicación al problema de asignación de cupos escolares", Rev. Fac. Ing. Univ. Antioquia, no. 46, pp. 145-157, 2008. |
| dc.identifier.issn.none.fl_str_mv |
0120-6230 |
| dc.identifier.uri.none.fl_str_mv |
http://hdl.handle.net/10495/4950 |
| dc.identifier.eissn.none.fl_str_mv |
2422-2844 |
| identifier_str_mv |
P. A. Maya, "Algoritmo de Generación de Columnas: Una revisión desde su aplicación al problema de asignación de cupos escolares", Rev. Fac. Ing. Univ. Antioquia, no. 46, pp. 145-157, 2008. 0120-6230 2422-2844 |
| url |
http://hdl.handle.net/10495/4950 |
| dc.language.iso.spa.fl_str_mv |
spa |
| language |
spa |
| dc.relation.ispartofjournalabbrev.spa.fl_str_mv |
Rev. Fac. Ing. Univ. Antioquia |
| dc.relation.citationendpage.spa.fl_str_mv |
157 |
| dc.relation.citationissue.spa.fl_str_mv |
46 |
| dc.relation.citationstartpage.spa.fl_str_mv |
145 |
| dc.relation.ispartofjournal.spa.fl_str_mv |
Revista Facultad de Ingeniería Universidad de Antioquia |
| dc.rights.uri.*.fl_str_mv |
https://creativecommons.org/licenses/by-nc-sa/2.5/co/ |
| dc.rights.uri.spa.fl_str_mv |
https://creativecommons.org/licenses/by-nc-sa/4.0/ |
| dc.rights.accessrights.*.fl_str_mv |
Atribución-NoComercial-CompartirIgual 2.5 Colombia (CC BY-NC-SA 2.5 CO) |
| dc.rights.accessrights.spa.fl_str_mv |
info:eu-repo/semantics/openAccess |
| dc.rights.coar.spa.fl_str_mv |
http://purl.org/coar/access_right/c_abf2 |
| rights_invalid_str_mv |
https://creativecommons.org/licenses/by-nc-sa/2.5/co/ https://creativecommons.org/licenses/by-nc-sa/4.0/ Atribución-NoComercial-CompartirIgual 2.5 Colombia (CC BY-NC-SA 2.5 CO) http://purl.org/coar/access_right/c_abf2 |
| eu_rights_str_mv |
openAccess |
| dc.format.extent.spa.fl_str_mv |
12 |
| dc.format.mimetype.spa.fl_str_mv |
application/pdf |
| dc.publisher.spa.fl_str_mv |
Universidad de Antioquia, Facultad de Ingeniería |
| dc.publisher.place.spa.fl_str_mv |
Medellín, Colombia |
| institution |
Universidad de Antioquia |
| bitstream.url.fl_str_mv |
https://bibliotecadigital.udea.edu.co/bitstreams/0b17d012-f387-439c-bccf-d59edeee385d/download https://bibliotecadigital.udea.edu.co/bitstreams/b11ff55e-9dd7-4ccd-9325-456c2299392a/download https://bibliotecadigital.udea.edu.co/bitstreams/8be24af2-0385-4f25-bcf3-c7d063a0fe04/download https://bibliotecadigital.udea.edu.co/bitstreams/beace693-e795-41a0-872a-15b91e40d9eb/download https://bibliotecadigital.udea.edu.co/bitstreams/ec909b59-0dd8-4326-b1ed-118c5e47fec3/download https://bibliotecadigital.udea.edu.co/bitstreams/fbff8113-81ab-49eb-baf7-7135b4e2f101/download https://bibliotecadigital.udea.edu.co/bitstreams/8e46efa9-9c3c-47a6-8b42-3943577a2114/download |
| bitstream.checksum.fl_str_mv |
9d85e0967cdafb25b57aa0cda698c143 4afdbb8c545fd630ea7db775da747b2f d41d8cd98f00b204e9800998ecf8427e d41d8cd98f00b204e9800998ecf8427e 8a4605be74aa9ea9d79846c1fba20a33 38ec2fa685154fdcf1b985edc17ddf22 6d4c46f603dd3415e9fd6e449c95c170 |
| bitstream.checksumAlgorithm.fl_str_mv |
MD5 MD5 MD5 MD5 MD5 MD5 MD5 |
| repository.name.fl_str_mv |
Repositorio Institucional de la Universidad de Antioquia |
| repository.mail.fl_str_mv |
aplicacionbibliotecadigitalbiblioteca@udea.edu.co |
| _version_ |
1851052468254801920 |
| spelling |
Maya Duque, Pablo Andrés2016-10-08T22:37:56Z2016-10-08T22:37:56Z2008P. A. Maya, "Algoritmo de Generación de Columnas: Una revisión desde su aplicación al problema de asignación de cupos escolares", Rev. Fac. Ing. Univ. Antioquia, no. 46, pp. 145-157, 2008.0120-6230http://hdl.handle.net/10495/49502422-2844RESUMEN: El algoritmo de generación de columnas (GC) se cita usualmente como alternativa para la solución de problemas de optimización de gran escala; este artículo aborda la presentación de dicho algoritmo en el contexto de la asignación de cupos escolares en el sistema de educación pública del distrito de Bogotá. Se discuten algunas de las falencias evidenciadas en la puesta en práctica del algoritmo, presentando estrategias para enfrentarlas. Se ilustra además, la forma como la generación de columnas se acopla dentro del algoritmo Branch and Price para dar solución a problemas de mayor complejidad.ABSTRACT: The Column Generation Algorithm (CGA) is commonly cited in the bibliography as alternative to solve large scale optimization problems. This article deals with the description of the GC algorithm in the context of the student assignation to the public schools. Some of the weaknesses and shortcomings encountered in the implementation and application to a real problem are discussed and some strategies to sort it out are presented. This work pointed out how the CGA could be used within a general Branch and Price procedure to solve problems with additional constrains.12application/pdfspaUniversidad de Antioquia, Facultad de IngenieríaMedellín, Colombiahttps://creativecommons.org/licenses/by-nc-sa/2.5/co/https://creativecommons.org/licenses/by-nc-sa/4.0/Atribución-NoComercial-CompartirIgual 2.5 Colombia (CC BY-NC-SA 2.5 CO)info:eu-repo/semantics/openAccesshttp://purl.org/coar/access_right/c_abf2Algoritmo de generación de columnasAlgoritmosAlgoritmo Branch and PriceAlgoritmo de Generación de Columnas : Una revisión desde su aplicación al problema de asignación de cupos escolaresColumn Generation Algorithm : A revision from its application to the Student Assignation ProblemArtículo de investigaciónhttp://purl.org/coar/resource_type/c_2df8fbb1https://purl.org/redcol/resource_type/ARThttp://purl.org/coar/version/c_970fb48d4fbd8a85info:eu-repo/semantics/articleinfo:eu-repo/semantics/publishedVersionRev. Fac. Ing. Univ. Antioquia15746145Revista Facultad de Ingeniería Universidad de AntioquiaPublicationORIGINALMayaPablo_2008_algoritmogeneracioncolumnas.pdfMayaPablo_2008_algoritmogeneracioncolumnas.pdfArtículo de investigaciónapplication/pdf1011712https://bibliotecadigital.udea.edu.co/bitstreams/0b17d012-f387-439c-bccf-d59edeee385d/download9d85e0967cdafb25b57aa0cda698c143MD51trueAnonymousREADCC-LICENSElicense_urllicense_urltext/plain; charset=utf-849https://bibliotecadigital.udea.edu.co/bitstreams/b11ff55e-9dd7-4ccd-9325-456c2299392a/download4afdbb8c545fd630ea7db775da747b2fMD52falseAnonymousREADlicense_textlicense_texttext/html; charset=utf-80https://bibliotecadigital.udea.edu.co/bitstreams/8be24af2-0385-4f25-bcf3-c7d063a0fe04/downloadd41d8cd98f00b204e9800998ecf8427eMD53falseAnonymousREADlicense_rdflicense_rdfapplication/rdf+xml; charset=utf-80https://bibliotecadigital.udea.edu.co/bitstreams/beace693-e795-41a0-872a-15b91e40d9eb/downloadd41d8cd98f00b204e9800998ecf8427eMD54falseAnonymousREADLICENSElicense.txtlicense.txttext/plain; charset=utf-81748https://bibliotecadigital.udea.edu.co/bitstreams/ec909b59-0dd8-4326-b1ed-118c5e47fec3/download8a4605be74aa9ea9d79846c1fba20a33MD55falseAnonymousREADTEXTMayaPablo_2008_algoritmogeneracioncolumnas.pdf.txtMayaPablo_2008_algoritmogeneracioncolumnas.pdf.txtExtracted texttext/plain47126https://bibliotecadigital.udea.edu.co/bitstreams/fbff8113-81ab-49eb-baf7-7135b4e2f101/download38ec2fa685154fdcf1b985edc17ddf22MD56falseAnonymousREADTHUMBNAILMayaPablo_2008_algoritmogeneracioncolumnas.pdf.jpgMayaPablo_2008_algoritmogeneracioncolumnas.pdf.jpgGenerated Thumbnailimage/jpeg11624https://bibliotecadigital.udea.edu.co/bitstreams/8e46efa9-9c3c-47a6-8b42-3943577a2114/download6d4c46f603dd3415e9fd6e449c95c170MD57falseAnonymousREAD10495/4950oai:bibliotecadigital.udea.edu.co:10495/49502025-03-26 22:49:16.686https://creativecommons.org/licenses/by-nc-sa/2.5/co/open.accesshttps://bibliotecadigital.udea.edu.coRepositorio Institucional de la Universidad de Antioquiaaplicacionbibliotecadigitalbiblioteca@udea.edu.coTk9URTogUExBQ0UgWU9VUiBPV04gTElDRU5TRSBIRVJFClRoaXMgc2FtcGxlIGxpY2Vuc2UgaXMgcHJvdmlkZWQgZm9yIGluZm9ybWF0aW9uYWwgcHVycG9zZXMgb25seS4KCk5PTi1FWENMVVNJVkUgRElTVFJJQlVUSU9OIExJQ0VOU0UKCkJ5IHNpZ25pbmcgYW5kIHN1Ym1pdHRpbmcgdGhpcyBsaWNlbnNlLCB5b3UgKHRoZSBhdXRob3Iocykgb3IgY29weXJpZ2h0Cm93bmVyKSBncmFudHMgdG8gRFNwYWNlIFVuaXZlcnNpdHkgKERTVSkgdGhlIG5vbi1leGNsdXNpdmUgcmlnaHQgdG8gcmVwcm9kdWNlLAp0cmFuc2xhdGUgKGFzIGRlZmluZWQgYmVsb3cpLCBhbmQvb3IgZGlzdHJpYnV0ZSB5b3VyIHN1Ym1pc3Npb24gKGluY2x1ZGluZwp0aGUgYWJzdHJhY3QpIHdvcmxkd2lkZSBpbiBwcmludCBhbmQgZWxlY3Ryb25pYyBmb3JtYXQgYW5kIGluIGFueSBtZWRpdW0sCmluY2x1ZGluZyBidXQgbm90IGxpbWl0ZWQgdG8gYXVkaW8gb3IgdmlkZW8uCgpZb3UgYWdyZWUgdGhhdCBEU1UgbWF5LCB3aXRob3V0IGNoYW5naW5nIHRoZSBjb250ZW50LCB0cmFuc2xhdGUgdGhlCnN1Ym1pc3Npb24gdG8gYW55IG1lZGl1bSBvciBmb3JtYXQgZm9yIHRoZSBwdXJwb3NlIG9mIHByZXNlcnZhdGlvbi4KCllvdSBhbHNvIGFncmVlIHRoYXQgRFNVIG1heSBrZWVwIG1vcmUgdGhhbiBvbmUgY29weSBvZiB0aGlzIHN1Ym1pc3Npb24gZm9yCnB1cnBvc2VzIG9mIHNlY3VyaXR5LCBiYWNrLXVwIGFuZCBwcmVzZXJ2YXRpb24uCgpZb3UgcmVwcmVzZW50IHRoYXQgdGhlIHN1Ym1pc3Npb24gaXMgeW91ciBvcmlnaW5hbCB3b3JrLCBhbmQgdGhhdCB5b3UgaGF2ZQp0aGUgcmlnaHQgdG8gZ3JhbnQgdGhlIHJpZ2h0cyBjb250YWluZWQgaW4gdGhpcyBsaWNlbnNlLiBZb3UgYWxzbyByZXByZXNlbnQKdGhhdCB5b3VyIHN1Ym1pc3Npb24gZG9lcyBub3QsIHRvIHRoZSBiZXN0IG9mIHlvdXIga25vd2xlZGdlLCBpbmZyaW5nZSB1cG9uCmFueW9uZSdzIGNvcHlyaWdodC4KCklmIHRoZSBzdWJtaXNzaW9uIGNvbnRhaW5zIG1hdGVyaWFsIGZvciB3aGljaCB5b3UgZG8gbm90IGhvbGQgY29weXJpZ2h0LAp5b3UgcmVwcmVzZW50IHRoYXQgeW91IGhhdmUgb2J0YWluZWQgdGhlIHVucmVzdHJpY3RlZCBwZXJtaXNzaW9uIG9mIHRoZQpjb3B5cmlnaHQgb3duZXIgdG8gZ3JhbnQgRFNVIHRoZSByaWdodHMgcmVxdWlyZWQgYnkgdGhpcyBsaWNlbnNlLCBhbmQgdGhhdApzdWNoIHRoaXJkLXBhcnR5IG93bmVkIG1hdGVyaWFsIGlzIGNsZWFybHkgaWRlbnRpZmllZCBhbmQgYWNrbm93bGVkZ2VkCndpdGhpbiB0aGUgdGV4dCBvciBjb250ZW50IG9mIHRoZSBzdWJtaXNzaW9uLgoKSUYgVEhFIFNVQk1JU1NJT04gSVMgQkFTRUQgVVBPTiBXT1JLIFRIQVQgSEFTIEJFRU4gU1BPTlNPUkVEIE9SIFNVUFBPUlRFRApCWSBBTiBBR0VOQ1kgT1IgT1JHQU5JWkFUSU9OIE9USEVSIFRIQU4gRFNVLCBZT1UgUkVQUkVTRU5UIFRIQVQgWU9VIEhBVkUKRlVMRklMTEVEIEFOWSBSSUdIVCBPRiBSRVZJRVcgT1IgT1RIRVIgT0JMSUdBVElPTlMgUkVRVUlSRUQgQlkgU1VDSApDT05UUkFDVCBPUiBBR1JFRU1FTlQuCgpEU1Ugd2lsbCBjbGVhcmx5IGlkZW50aWZ5IHlvdXIgbmFtZShzKSBhcyB0aGUgYXV0aG9yKHMpIG9yIG93bmVyKHMpIG9mIHRoZQpzdWJtaXNzaW9uLCBhbmQgd2lsbCBub3QgbWFrZSBhbnkgYWx0ZXJhdGlvbiwgb3RoZXIgdGhhbiBhcyBhbGxvd2VkIGJ5IHRoaXMKbGljZW5zZSwgdG8geW91ciBzdWJtaXNzaW9uLgo= |