Finding near optimal solutions to the Thesis Defense Timetabling problem by exploiting symmetries

Finding near optimal solutions to the Thesis Defense Timetabling problem by exploiting symmetries | Research Square window.SnipcartSettings = { analytics: { enabled: false } }; (function() { var accessVector = localStorage.getItem('access_vector') || ''; window.dataLayer = window.dataLayer || []; if (accessVector) { window.dataLayer.push({ user: { profile: { profileInfo: { snid: accessVector } } } }); } })(); (function(w,d,s,l,i){w[l]=w[l]||[];w[l].push({'gtm.start':new Date().getTime(),event:'gtm.js'});var f=d.getElementsByTagName(s)[0],j=d.createElement(s),dl=l!='dataLayer'?'&l='+l:'';j.async=true;j.src='https://www.googletagmanager.com/gtm.js?id='+i+dl;f.parentNode.insertBefore(j,f);})(window,document,'script','dataLayer','GTM-K279D39R'); Browse Preprints In Review Journals COVID-19 Preprints AJE Video Bytes Research Tools Research Promotion AJE Professional Editing AJE Rubriq About Preprint Platform In Review Editorial Policies Our Team Advisory Board Help Center Sign In Submit a Preprint Cite Share Download PDF Short Report Finding near optimal solutions to the Thesis Defense Timetabling problem by exploiting symmetries Angelos Dimitsas, Christos Gogos This is a preprint; it has not been peer reviewed by a journal. https://doi.org/ 10.21203/rs.3.rs-3982715/v1 This work is licensed under a CC BY 4.0 License Status: Published Journal Publication published 20 Jul, 2024 Read the published version in Operations Research Forum → Version 1 posted 8 You are reading this latest preprint version Abstract Thesis Defense Timetabling is the problem of arranging meetings of graduation candidates and faculty members for evaluating the theses of the first ones. Several rules apply that guarantee that the evaluation process will be assigned to appropriate opponents based on their expertise, while work will be balanced among all faculty members. The problem is combinatorial in nature, and optimal solutions are hard to find and even harder to verify that they are indeed optimal. In this work we present an exact model of the problem that is solved using Constraint Programming. We augment this model by adding constraints that capture three types of symmetries that we identified. These additions make the models capable of finding near optimal solutions, in reasonable time, and this is demonstrated by running experiments on public datasets of Thesis Defense Timetabling problem instances. Several new best solutions and lower bounds are obtained. Our approach shows that exploiting intricate details of a problem can drive contemporary constraint programming solvers to optimal or near optimal solutions faster. Scheduling Thesis Defense Timetabling Constraint Programming Symmetries Full Text Additional Declarations No competing interests reported. Cite Share Download PDF Status: Published Journal Publication published 20 Jul, 2024 Read the published version in Operations Research Forum → Version 1 posted Editorial decision: Revision requested 21 May, 2024 Reviewers agreed at journal 10 Apr, 2024 Reviews received at journal 07 Apr, 2024 Reviewers agreed at journal 02 Apr, 2024 Reviewers invited by journal 12 Mar, 2024 Submission checks completed at journal 26 Feb, 2024 Editor assigned by journal 26 Feb, 2024 First submitted to journal 23 Feb, 2024 You are reading this latest preprint version Research Square lets you share your work early, gain feedback from the community, and start making changes to your manuscript prior to peer review in a journal. As a division of Research Square Company, we’re committed to making research communication faster, fairer, and more useful. We do this by developing innovative software and high quality services for the global research community. Our growing team is made up of researchers and industry professionals working together to solve the most critical problems facing scientific publishing. Also discoverable on Platform About Our Team In Review Editorial Policies Advisory Board Help Center Resources Author Services Accessibility API Access RSS feed Manage Cookie Preferences © Research Square 2026 | ISSN 2693-5015 (online) Privacy Policy Terms of Service Do Not Sell My Personal Information {"props":{"pageProps":{"initialData":{"identity":"rs-3982715","acceptedTermsAndConditions":true,"allowDirectSubmit":false,"archivedVersions":[],"articleType":"Short Report","associatedPublications":[],"authors":[{"id":274970069,"identity":"e7894458-c964-4003-9c3f-c815736de261","order_by":0,"name":"Angelos Dimitsas","email":"data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAZAAAAAyAQMAAABI0h/eAAAABlBMVEX///8AAABVwtN+AAAACXBIWXMAAA7EAAAOxAGVKw4bAAAAv0lEQVRIiWNgGAWjYHACgwMMBiCa+QADhEGcFpBStgTitUAxD5Hq+RuYNx66UfDHnr//zDeJDwUMdtsbCGiROMBWcDjHwCBxxo3cbZIzDBiS5xwgZM0BHgOQlgSGG7zbpIFuS5YgpEMeqsVe/vyZZ8RpMYBqYdxwIIcNpMWOoBbDw2C/GCduvJFmbDnDQCKBoBa5482bP+f8kbOXO3/44Y0Pf2zsCWphYEblSiQ2ENSCDuxJ1jEKRsEoGAXDHgAADIQ64NfP04gAAAAASUVORK5CYII=","orcid":"","institution":"University of Ioannina","correspondingAuthor":true,"prefix":"","firstName":"Angelos","middleName":"","lastName":"Dimitsas","suffix":""},{"id":274970070,"identity":"c2b1045c-78af-426c-b0f0-0a38691f5270","order_by":1,"name":"Christos Gogos","email":"","orcid":"","institution":"University of Ioannina","correspondingAuthor":false,"prefix":"","firstName":"Christos","middleName":"","lastName":"Gogos","suffix":""}],"badges":[],"createdAt":"2024-02-23 17:59:13","currentVersionCode":1,"declarations":"","doi":"10.21203/rs.3.rs-3982715/v1","doiUrl":"https://doi.org/10.21203/rs.3.rs-3982715/v1","draftVersion":[],"editorialEvents":[{"content":"https://doi.org/10.1007/s43069-024-00346-4","type":"published","date":"2024-07-20T16:13:36+00:00"}],"editorialNote":"","failedWorkflow":false,"files":[{"id":61595333,"identity":"3f87b5e9-aa4c-4fb5-aa36-aa5666103598","added_by":"auto","created_at":"2024-08-01 17:22:17","extension":"pdf","order_by":1,"title":"","display":"","copyAsset":false,"role":"manuscript-pdf","size":259743,"visible":true,"origin":"","legend":"","description":"","filename":"tdttnearoptimal.pdf","url":"https://assets-eu.researchsquare.com/files/rs-3982715/v1_covered_aaa938cf-c355-4994-a56c-c382a5489a8b.pdf"}],"financialInterests":"No competing interests reported.","formattedTitle":"Finding near optimal solutions to the Thesis Defense Timetabling problem by exploiting symmetries","fulltext":[],"fulltextSource":"","fullText":"","funders":[],"hasAdminPriorityOnWorkflow":false,"hasManuscriptDocX":false,"hasOptedInToPreprint":true,"hasPassedJournalQc":"","hasAnyPriority":false,"hideJournal":false,"highlight":"","institution":"","isAcceptedByJournal":true,"isAuthorSuppliedPdf":true,"isDeskRejected":"","isHiddenFromSearch":false,"isInQc":false,"isInWorkflow":false,"isPdf":true,"isPdfUpToDate":true,"isWithdrawnOrRetracted":false,"journal":{"display":true,"email":"[email protected]","identity":"operations-research-forum","isNatureJournal":false,"hasQc":true,"allowDirectSubmit":false,"externalIdentity":"","sideBox":"Learn more about [Operations Research Forum](https://link.springer.com/journal/43069)","snPcode":"43069","submissionUrl":"https://submission.nature.com/new-submission/43069/3","title":"Operations Research Forum","twitterHandle":"","acdcEnabled":true,"dfaEnabled":true,"editorialSystem":"stoa","reportingPortfolio":"Springer Hybrid","inReviewEnabled":true,"inReviewRevisionsEnabled":false},"keywords":"Scheduling, Thesis Defense Timetabling, Constraint Programming, Symmetries","lastPublishedDoi":"10.21203/rs.3.rs-3982715/v1","lastPublishedDoiUrl":"https://doi.org/10.21203/rs.3.rs-3982715/v1","license":{"name":"CC BY 4.0","url":"https://creativecommons.org/licenses/by/4.0/"},"manuscriptAbstract":"Thesis Defense Timetabling is the problem of arranging meetings of graduation candidates and faculty members for evaluating the theses of the first ones. Several rules apply that guarantee that the evaluation process will be assigned to appropriate opponents based on their expertise, while work will be balanced among all faculty members. The problem is combinatorial in nature, and optimal solutions are hard to find and even harder to verify that they are indeed optimal. In this work we present an exact model of the problem that is solved using Constraint Programming. We augment this model by adding constraints that capture three types of symmetries that we identified. These additions make the models capable of finding near optimal solutions, in reasonable time, and this is demonstrated by running experiments on public datasets of Thesis Defense Timetabling problem instances. Several new best solutions and lower bounds are obtained. Our approach shows that exploiting intricate details of a problem can drive contemporary constraint programming solvers to optimal or near optimal solutions faster.","manuscriptTitle":"Finding near optimal solutions to the Thesis Defense Timetabling problem by exploiting symmetries","msid":"","msnumber":"","nonDraftVersions":[{"code":1,"date":"2024-02-28 02:49:16","doi":"10.21203/rs.3.rs-3982715/v1","editorialEvents":[{"type":"communityComments","content":0},{"type":"decision","content":"Revision requested","date":"2024-05-21T09:02:52+00:00","index":"","fulltext":""},{"type":"reviewerAgreed","content":"60bec2a5-ae78-4def-9504-2fe2f58380d0","date":"2024-04-10T05:56:00+00:00","index":"hide","fulltext":""},{"type":"editorInvitedReview","content":"","date":"2024-04-07T15:49:50+00:00","index":"hide","fulltext":""},{"type":"reviewerAgreed","content":"b5607568-74b1-4466-aa1e-278b53015f7c_SNPRID","date":"2024-04-02T09:00:29+00:00","index":"hide","fulltext":""},{"type":"reviewersInvited","content":"","date":"2024-03-12T05:18:35+00:00","index":"","fulltext":""},{"type":"checksComplete","content":"","date":"2024-02-26T06:57:39+00:00","index":"","fulltext":""},{"type":"editorAssigned","content":"","date":"2024-02-26T06:57:39+00:00","index":"","fulltext":""},{"type":"submitted","content":"Operations Research Forum","date":"2024-02-23T17:54:11+00:00","index":"","fulltext":""}],"status":"published","journal":{"display":true,"email":"[email protected]","identity":"operations-research-forum","isNatureJournal":false,"hasQc":true,"allowDirectSubmit":false,"externalIdentity":"","sideBox":"Learn more about [Operations Research Forum](https://link.springer.com/journal/43069)","snPcode":"43069","submissionUrl":"https://submission.nature.com/new-submission/43069/3","title":"Operations Research Forum","twitterHandle":"","acdcEnabled":true,"dfaEnabled":true,"editorialSystem":"stoa","reportingPortfolio":"Springer Hybrid","inReviewEnabled":true,"inReviewRevisionsEnabled":false}}],"origin":"","ownerIdentity":"f9f79b17-56b6-4371-bdf0-03fe2d531bc2","owner":[],"postedDate":"February 28th, 2024","published":true,"recentEditorialEvents":[],"rejectedJournal":[],"revision":"","amendment":"","status":"published-in-journal","subjectAreas":[],"tags":[],"updatedAt":"2024-08-01T16:21:46+00:00","versionOfRecord":{"articleIdentity":"rs-3982715","link":"https://doi.org/10.1007/s43069-024-00346-4","journal":{"identity":"operations-research-forum","isVorOnly":false,"title":"Operations Research Forum"},"publishedOn":"2024-07-20 16:13:36","publishedOnDateReadable":"July 20th, 2024"},"versionCreatedAt":"2024-02-28 02:49:16","video":"","vorDoi":"10.1007/s43069-024-00346-4","vorDoiUrl":"https://doi.org/10.1007/s43069-024-00346-4","workflowStages":[]},"version":"v1","identity":"rs-3982715","journalConfig":"researchsquare"},"__N_SSP":true},"page":"/article/[identity]/[[...version]]","query":{"redirect":"/article/rs-3982715","identity":"rs-3982715","version":["v1"]},"buildId":"qtupq5eGEP_6zYnWcrvyt","isFallback":false,"isExperimentalCompile":false,"dynamicIds":[84888],"gssp":true,"scriptLoader":[]}