Second-Order Cone Relaxation Algorithms for Maritime Packing and Scheduling Problems

Second-Order Cone Relaxation Algorithms for Maritime Packing and Scheduling Problems | 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 Research Article Second-Order Cone Relaxation Algorithms for Maritime Packing and Scheduling Problems Nam Anh Quach This is a preprint; it has not been peer reviewed by a journal. https://doi.org/ 10.21203/rs.3.rs-9084063/v1 This work is licensed under a CC BY 4.0 License Status: Posted Version 1 posted You are reading this latest preprint version Abstract Integrated packing and scheduling problems arising in maritime container terminal operations lead naturally to Mixed-Integer Nonlinear Programs (MINLPs) in which discrete spatial assignments interact with continuous temporal variables and nonlinear physical constraints. These interactions often produce bilinear queueing relationships and quadratic vessel stability constraints, making the resulting optimization problems computationally challenging. In particular, standard polyhedral relaxations frequently yield weak lower bounds, limiting the effectiveness of classical spatial branch-and-bound methods. This paper proposes a lifted second-order cone (SOC) relaxation for a class of maritime packing and scheduling models. The formulation isolates the nonlinear queueing and stability structures and embeds them within a convex conic representation that preserves the geometry of the underlying quadratic constraints. We show that the resulting SOC relaxation strictly dominates the corresponding linear relaxation and provides significantly tighter lower bounds. Building on this relaxation, we develop a Conic Spatial Branch-and-Bound (Conic-sBB) algorithm that integrates the strengthened conic bounds with a hierarchical branching strategy and a deterministic primal heuristic. Computational experiments on a comprehensive benchmark set demonstrate that the proposed framework substantially improves root-node bounds and reduces search tree sizes compared with linear-relaxation-based approaches. In particular, the algorithm consistently solves medium- and large-scale instances more efficiently and proves optimality for problem sizes that remain challenging for baseline methods. The results highlight the potential of conic relaxation techniques for strengthening global optimization algorithms in integrated packing–scheduling problems. Second-order cone relaxation mixed-integer nonlinear programming branch-and-bound algorithms maritime logistics optimization packing and scheduling conic programming Full Text Additional Declarations No competing interests reported. Cite Share Download PDF Status: Posted Version 1 posted 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-9084063","acceptedTermsAndConditions":true,"allowDirectSubmit":true,"archivedVersions":[],"articleType":"Research Article","associatedPublications":[],"authors":[{"id":603803804,"identity":"c4647bd3-6a98-4688-bc67-ba43fde8c6f0","order_by":0,"name":"Nam Anh Quach","email":"data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAZAAAAAyAQMAAABI0h/eAAAABlBMVEX///8AAABVwtN+AAAACXBIWXMAAA7EAAAOxAGVKw4bAAAA9UlEQVRIiWNgGAWjYLACxgYQycP4+E8FkGZmbiBaC7MBzxmQFkbitbBJ8LYhuDiBOfvpxM+FO6wT+9vPHpCQnFcbzd8O1PKjYhtOLZY9uZulZ55JT5xxJi/BwHDb8dwZhxkbGHvO3MapxeBA7gZp3rbDiQ03eAwSErcdy20AamFmbMOj5fzbzb9BWuYDtRw4OOdY7nyCWm7kbgPbsuEGj2FjY0NN7gbCWt5us+ZtSzfeeCbHmJnh2IHcjUAtB/H65Xzu5tu8bday846fMf/NUFOXO+/84YMPflTg1gIFzDDGYTB5gJB6ZC11RCgeBaNgFIyCkQYAJ8Fh8iX1/zgAAAAASUVORK5CYII=","orcid":"","institution":"Hong Bang International University","correspondingAuthor":true,"prefix":"","firstName":"Nam","middleName":"Anh","lastName":"Quach","suffix":""}],"badges":[],"createdAt":"2026-03-10 12:38:25","currentVersionCode":1,"declarations":"","doi":"10.21203/rs.3.rs-9084063/v1","doiUrl":"https://doi.org/10.21203/rs.3.rs-9084063/v1","draftVersion":[],"editorialEvents":[],"editorialNote":"","failedWorkflow":false,"files":[{"id":105728638,"identity":"7168e32f-25ac-47e7-bc81-2c3c3fc054ac","added_by":"auto","created_at":"2026-03-30 11:12:21","extension":"pdf","order_by":1,"title":"","display":"","copyAsset":false,"role":"manuscript-pdf","size":573074,"visible":true,"origin":"","legend":"","description":"","filename":"ConicRelaxationAlgorithmsforMaritimePackingandSchedulingProblems2ndrevised.pdf","url":"https://assets-eu.researchsquare.com/files/rs-9084063/v1_covered_52318f8d-3632-4065-a21e-1dded386d688.pdf"}],"financialInterests":"No competing interests reported.","formattedTitle":"Second-Order Cone Relaxation Algorithms for Maritime Packing and Scheduling Problems","fulltext":[],"fulltextSource":"","fullText":"","funders":[],"hasAdminPriorityOnWorkflow":false,"hasManuscriptDocX":false,"hasOptedInToPreprint":true,"hasPassedJournalQc":"","hasAnyPriority":true,"hideJournal":true,"highlight":"","institution":"","isAcceptedByJournal":false,"isAuthorSuppliedPdf":true,"isDeskRejected":"","isHiddenFromSearch":false,"isInQc":false,"isInWorkflow":false,"isPdf":true,"isPdfUpToDate":true,"isWithdrawnOrRetracted":false,"journal":{"display":true,"email":"[email protected]","identity":"researchsquare","isNatureJournal":false,"hasQc":true,"allowDirectSubmit":true,"externalIdentity":"","sideBox":"","snPcode":"","submissionUrl":"/submission","title":"Research Square","twitterHandle":"researchsquare","acdcEnabled":true,"dfaEnabled":false,"editorialSystem":"","reportingPortfolio":"","inReviewEnabled":false,"inReviewRevisionsEnabled":true},"keywords":"Second-order cone relaxation, mixed-integer nonlinear programming, branch-and-bound algorithms, maritime logistics optimization, packing and scheduling, conic programming","lastPublishedDoi":"10.21203/rs.3.rs-9084063/v1","lastPublishedDoiUrl":"https://doi.org/10.21203/rs.3.rs-9084063/v1","license":{"name":"CC BY 4.0","url":"https://creativecommons.org/licenses/by/4.0/"},"manuscriptAbstract":"Integrated packing and scheduling problems arising in maritime container terminal operations lead naturally to Mixed-Integer Nonlinear Programs (MINLPs) in which discrete spatial assignments interact with continuous temporal variables and nonlinear physical constraints. These interactions often produce bilinear queueing relationships and quadratic vessel stability constraints, making the resulting optimization problems computationally challenging. In particular, standard polyhedral relaxations frequently yield weak lower bounds, limiting the effectiveness of classical spatial branch-and-bound methods.\nThis paper proposes a lifted second-order cone (SOC) relaxation for a class of maritime packing and scheduling models. The formulation isolates the nonlinear queueing and stability structures and embeds them within a convex conic representation that preserves the geometry of the underlying quadratic constraints. We show that the resulting SOC relaxation strictly dominates the corresponding linear relaxation and provides significantly tighter lower bounds.\nBuilding on this relaxation, we develop a Conic Spatial Branch-and-Bound (Conic-sBB) algorithm that integrates the strengthened conic bounds with a hierarchical branching strategy and a deterministic primal heuristic. Computational experiments on a comprehensive benchmark set demonstrate that the proposed framework substantially improves root-node bounds and reduces search tree sizes compared with linear-relaxation-based approaches. In particular, the algorithm consistently solves medium- and large-scale instances more efficiently and proves optimality for problem sizes that remain challenging for baseline methods.\nThe results highlight the potential of conic relaxation techniques for strengthening global optimization algorithms in integrated packing–scheduling problems.","manuscriptTitle":"Second-Order Cone Relaxation Algorithms for Maritime Packing and Scheduling Problems","msid":"","msnumber":"","nonDraftVersions":[{"code":1,"date":"2026-03-11 07:20:37","doi":"10.21203/rs.3.rs-9084063/v1","editorialEvents":[{"type":"communityComments","content":0}],"status":"published","journal":{"display":true,"email":"[email protected]","identity":"researchsquare","isNatureJournal":false,"hasQc":true,"allowDirectSubmit":true,"externalIdentity":"","sideBox":"","snPcode":"","submissionUrl":"/submission","title":"Research Square","twitterHandle":"researchsquare","acdcEnabled":true,"dfaEnabled":false,"editorialSystem":"","reportingPortfolio":"","inReviewEnabled":false,"inReviewRevisionsEnabled":true}}],"origin":"","ownerIdentity":"bd2cceed-7ea5-4675-a506-75c0281f3ee9","owner":[],"postedDate":"March 11th, 2026","published":true,"recentEditorialEvents":[],"rejectedJournal":[],"revision":"","amendment":"","status":"posted","subjectAreas":[],"tags":[],"updatedAt":"2026-03-28T16:24:40+00:00","versionOfRecord":[],"versionCreatedAt":"2026-03-11 07:20:37","video":"","vorDoi":"","vorDoiUrl":"","workflowStages":[]},"version":"v1","identity":"rs-9084063","journalConfig":"researchsquare"},"__N_SSP":true},"page":"/article/[identity]/[[...version]]","query":{"redirect":"/article/rs-9084063","identity":"rs-9084063","version":["v1"]},"buildId":"XKTyCvWXoU3ODBz1xrDgd","isFallback":false,"isExperimentalCompile":false,"dynamicIds":[84888],"gssp":true,"scriptLoader":[]}