首页> 外文会议>Experimental Algorithms >Optimal University Course Timetables and the Partial Transversal Polytope
【24h】

Optimal University Course Timetables and the Partial Transversal Polytope

机译:最佳大学课程表和部分横向多面体

获取原文
获取原文并翻译 | 示例

摘要

University course timetabling is the conflict-free assignment of courses to weekly time slots and rooms subject to various hard and soft constraints. One goal is to meet as closely as possible professors' preferences. Building on an intuitive integer program (IP), we develop an exact decomposition approach which schedules courses first, and matches courses/times to rooms in a second stage. The subset of constraints which ensures a feasible room assignment defines the well-known partial transversal polytope. We describe it as a polymatroid, and thereby obtain a complete characterization of its facets. This enables us to add only strong valid inequalities to the first stage IP. In fact, for all practical purposes the number of facets is small. We present encouraging computational results on real-world and simulated timetabling data. The sizes of our optimally solvable instances (respecting all hard constraints) are the largest reported in the literature by far.
机译:大学课程时间表是将课程无冲突地分配给每周的时间段和房间,并受到各种硬性和软性约束。一个目标是尽可能接近教授的喜好。在直观的整数程序(IP)的基础上,我们开发了一种精确的分解方法,该方法首先安排课程,然后在第二阶段将课程/时间与房间进行匹配。确保可行的房间分配的约束子集定义了众所周知的部分横向多面体。我们将其描述为多类动物,从而获得其各个方面的完整特征。这使我们能够在第一阶段IP中仅添加强烈的有效不等式。实际上,出于所有实际目的,刻面的数量很少。我们在现实世界和模拟时间表数据上给出了令人鼓舞的计算结果。迄今为止,我们最优可解实例的大小(考虑到所有硬约束)是文献中报道的最大大小。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱:kefu@zhangqiaokeyan.com

京公网安备:11010802029741号 ICP备案号:京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有
  • 客服微信

  • 服务号