{"data":{"id":"10.48550/arxiv.2107.10201","type":"dois","attributes":{"doi":"10.48550/arxiv.2107.10201","prefix":"10.48550","suffix":"arxiv.2107.10201","identifiers":[{"identifier":"2107.10201","identifierType":"arXiv"}],"alternateIdentifiers":[{"alternateIdentifierType":"arXiv","alternateIdentifier":"2107.10201"}],"creators":[{"name":"Sonnerat, Nicolas","nameType":"Personal","givenName":"Nicolas","familyName":"Sonnerat","affiliation":[],"nameIdentifiers":[]},{"name":"Wang, Pengming","nameType":"Personal","givenName":"Pengming","familyName":"Wang","affiliation":[],"nameIdentifiers":[]},{"name":"Ktena, Ira","nameType":"Personal","givenName":"Ira","familyName":"Ktena","affiliation":[],"nameIdentifiers":[]},{"name":"Bartunov, Sergey","nameType":"Personal","givenName":"Sergey","familyName":"Bartunov","affiliation":[],"nameIdentifiers":[]},{"name":"Nair, Vinod","nameType":"Personal","givenName":"Vinod","familyName":"Nair","affiliation":[],"nameIdentifiers":[]}],"titles":[{"title":"Learning a Large Neighborhood Search Algorithm for Mixed Integer Programs"}],"publisher":"arXiv","container":{},"publicationYear":2021,"subjects":[{"lang":"en","subject":"Optimization and Control (math.OC)","subjectScheme":"arXiv"},{"lang":"en","subject":"Machine Learning (cs.LG)","subjectScheme":"arXiv"},{"subject":"FOS: Mathematics","subjectScheme":"Fields of Science and Technology (FOS)"},{"subject":"FOS: Mathematics","schemeUri":"http://www.oecd.org/science/inno/38235147.pdf","subjectScheme":"Fields of Science and Technology (FOS)"},{"subject":"FOS: Computer and information sciences","subjectScheme":"Fields of Science and Technology (FOS)"},{"subject":"FOS: Computer and information sciences","schemeUri":"http://www.oecd.org/science/inno/38235147.pdf","subjectScheme":"Fields of Science and Technology (FOS)"}],"contributors":[],"dates":[{"date":"2021-07-21T16:43:46Z","dateType":"Submitted","dateInformation":"v1"},{"date":"2021-07-22T00:24:45Z","dateType":"Updated","dateInformation":"v1"},{"date":"2021-07-22T20:37:42Z","dateType":"Submitted","dateInformation":"v2"},{"date":"2021-07-26T00:02:56Z","dateType":"Updated","dateInformation":"v2"},{"date":"2022-05-20T16:31:03Z","dateType":"Submitted","dateInformation":"v3"},{"date":"2022-05-23T00:23:38Z","dateType":"Updated","dateInformation":"v3"},{"date":"2021-07","dateType":"Available","dateInformation":"v1"},{"date":"2021","dateType":"Issued"}],"language":null,"types":{"ris":"GEN","bibtex":"misc","citeproc":"article","schemaOrg":"CreativeWork","resourceType":"Article","resourceTypeGeneral":"Preprint"},"relatedIdentifiers":[],"relatedItems":[],"sizes":[],"formats":[],"version":"3","rightsList":[{"rights":"Creative Commons Attribution 4.0 International","rightsUri":"https://creativecommons.org/licenses/by/4.0/legalcode","schemeUri":"https://spdx.org/licenses/","rightsIdentifier":"cc-by-4.0","rightsIdentifierScheme":"SPDX"}],"descriptions":[{"description":"Large Neighborhood Search (LNS) is a combinatorial optimization heuristic that starts with an assignment of values for the variables to be optimized, and iteratively improves it by searching a large neighborhood around the current assignment. In this paper we consider a learning-based LNS approach for mixed integer programs (MIPs). We train a Neural Diving model to represent a probability distribution over assignments, which, together with an off-the-shelf MIP solver, generates an initial assignment. Formulating the subsequent search steps as a Markov Decision Process, we train a Neural Neighborhood Selection policy to select a search neighborhood at each step, which is searched using a MIP solver to find the next assignment. The policy network is trained using imitation learning. We propose a target policy for imitation that, given enough compute resources, is guaranteed to select the neighborhood containing the optimal next assignment amongst all possible choices for the neighborhood of a specified size. Our approach matches or outperforms all the baselines on five real-world MIP datasets with large-scale instances from diverse applications, including two production applications at Google. It achieves $2\\times$ to $37.8\\times$ better average primal gap than the best baseline on three of the datasets at large running times.","descriptionType":"Abstract"}],"geoLocations":[],"fundingReferences":[],"xml":"PD94bWwgdmVyc2lvbj0iMS4wIiBlbmNvZGluZz0idXRmLTgiPz4KPHJlc291cmNlIHhtbG5zPSJodHRwOi8vZGF0YWNpdGUub3JnL3NjaGVtYS9rZXJuZWwtNCIgeG1sbnM6eHNpPSJodHRwOi8vd3d3LnczLm9yZy8yMDAxL1hNTFNjaGVtYS1pbnN0YW5jZSIgeHNpOnNjaGVtYUxvY2F0aW9uPSJodHRwOi8vZGF0YWNpdGUub3JnL3NjaGVtYS9rZXJuZWwtNCBodHRwOi8vc2NoZW1hLmRhdGFjaXRlLm9yZy9tZXRhL2tlcm5lbC00LjMvbWV0YWRhdGEueHNkIj4KICA8aWRlbnRpZmllciBpZGVudGlmaWVyVHlwZT0iRE9JIj4xMC40ODU1MC9BUlhJVi4yMTA3LjEwMjAxPC9pZGVudGlmaWVyPgogIDxhbHRlcm5hdGVJZGVudGlmaWVycz4KICAgIDxhbHRlcm5hdGVJZGVudGlmaWVyIGFsdGVybmF0ZUlkZW50aWZpZXJUeXBlPSJhclhpdiI+MjEwNy4xMDIwMTwvYWx0ZXJuYXRlSWRlbnRpZmllcj4KICA8L2FsdGVybmF0ZUlkZW50aWZpZXJzPgogIDxjcmVhdG9ycz4KICAgIDxjcmVhdG9yPgogICAgICA8Y3JlYXRvck5hbWUgbmFtZVR5cGU9IlBlcnNvbmFsIj5Tb25uZXJhdCwgTmljb2xhczwvY3JlYXRvck5hbWU+CiAgICAgIDxnaXZlbk5hbWU+Tmljb2xhczwvZ2l2ZW5OYW1lPgogICAgICA8ZmFtaWx5TmFtZT5Tb25uZXJhdDwvZmFtaWx5TmFtZT4KICAgIDwvY3JlYXRvcj4KICAgIDxjcmVhdG9yPgogICAgICA8Y3JlYXRvck5hbWUgbmFtZVR5cGU9IlBlcnNvbmFsIj5XYW5nLCBQZW5nbWluZzwvY3JlYXRvck5hbWU+CiAgICAgIDxnaXZlbk5hbWU+UGVuZ21pbmc8L2dpdmVuTmFtZT4KICAgICAgPGZhbWlseU5hbWU+V2FuZzwvZmFtaWx5TmFtZT4KICAgIDwvY3JlYXRvcj4KICAgIDxjcmVhdG9yPgogICAgICA8Y3JlYXRvck5hbWUgbmFtZVR5cGU9IlBlcnNvbmFsIj5LdGVuYSwgSXJhPC9jcmVhdG9yTmFtZT4KICAgICAgPGdpdmVuTmFtZT5JcmE8L2dpdmVuTmFtZT4KICAgICAgPGZhbWlseU5hbWU+S3RlbmE8L2ZhbWlseU5hbWU+CiAgICA8L2NyZWF0b3I+CiAgICA8Y3JlYXRvcj4KICAgICAgPGNyZWF0b3JOYW1lIG5hbWVUeXBlPSJQZXJzb25hbCI+QmFydHVub3YsIFNlcmdleTwvY3JlYXRvck5hbWU+CiAgICAgIDxnaXZlbk5hbWU+U2VyZ2V5PC9naXZlbk5hbWU+CiAgICAgIDxmYW1pbHlOYW1lPkJhcnR1bm92PC9mYW1pbHlOYW1lPgogICAgPC9jcmVhdG9yPgogICAgPGNyZWF0b3I+CiAgICAgIDxjcmVhdG9yTmFtZSBuYW1lVHlwZT0iUGVyc29uYWwiPk5haXIsIFZpbm9kPC9jcmVhdG9yTmFtZT4KICAgICAgPGdpdmVuTmFtZT5WaW5vZDwvZ2l2ZW5OYW1lPgogICAgICA8ZmFtaWx5TmFtZT5OYWlyPC9mYW1pbHlOYW1lPgogICAgPC9jcmVhdG9yPgogIDwvY3JlYXRvcnM+CiAgPHRpdGxlcz4KICAgIDx0aXRsZT5MZWFybmluZyBhIExhcmdlIE5laWdoYm9yaG9vZCBTZWFyY2ggQWxnb3JpdGhtIGZvciBNaXhlZCBJbnRlZ2VyIFByb2dyYW1zPC90aXRsZT4KICA8L3RpdGxlcz4KICA8cHVibGlzaGVyPmFyWGl2PC9wdWJsaXNoZXI+CiAgPHB1YmxpY2F0aW9uWWVhcj4yMDIxPC9wdWJsaWNhdGlvblllYXI+CiAgPHN1YmplY3RzPgogICAgPHN1YmplY3QgeG1sOmxhbmc9ImVuIiBzdWJqZWN0U2NoZW1lPSJhclhpdiI+T3B0aW1pemF0aW9uIGFuZCBDb250cm9sIChtYXRoLk9DKTwvc3ViamVjdD4KICAgIDxzdWJqZWN0IHhtbDpsYW5nPSJlbiIgc3ViamVjdFNjaGVtZT0iYXJYaXYiPk1hY2hpbmUgTGVhcm5pbmcgKGNzLkxHKTwvc3ViamVjdD4KICAgIDxzdWJqZWN0IHN1YmplY3RTY2hlbWU9IkZpZWxkcyBvZiBTY2llbmNlIGFuZCBUZWNobm9sb2d5IChGT1MpIj5GT1M6IE1hdGhlbWF0aWNzPC9zdWJqZWN0PgogICAgPHN1YmplY3Qgc3ViamVjdFNjaGVtZT0iRmllbGRzIG9mIFNjaWVuY2UgYW5kIFRlY2hub2xvZ3kgKEZPUykiPkZPUzogQ29tcHV0ZXIgYW5kIGluZm9ybWF0aW9uIHNjaWVuY2VzPC9zdWJqZWN0PgogIDwvc3ViamVjdHM+CiAgPGRhdGVzPgogICAgPGRhdGUgZGF0ZVR5cGU9IlN1Ym1pdHRlZCIgZGF0ZUluZm9ybWF0aW9uPSJ2MSI+MjAyMS0wNy0yMVQxNjo0Mzo0Nlo8L2RhdGU+CiAgICA8ZGF0ZSBkYXRlVHlwZT0iVXBkYXRlZCIgZGF0ZUluZm9ybWF0aW9uPSJ2MSI+MjAyMS0wNy0yMlQwMDoyNDo0NVo8L2RhdGU+CiAgICA8ZGF0ZSBkYXRlVHlwZT0iU3VibWl0dGVkIiBkYXRlSW5mb3JtYXRpb249InYyIj4yMDIxLTA3LTIyVDIwOjM3OjQyWjwvZGF0ZT4KICAgIDxkYXRlIGRhdGVUeXBlPSJVcGRhdGVkIiBkYXRlSW5mb3JtYXRpb249InYyIj4yMDIxLTA3LTI2VDAwOjAyOjU2WjwvZGF0ZT4KICAgIDxkYXRlIGRhdGVUeXBlPSJTdWJtaXR0ZWQiIGRhdGVJbmZvcm1hdGlvbj0idjMiPjIwMjItMDUtMjBUMTY6MzE6MDNaPC9kYXRlPgogICAgPGRhdGUgZGF0ZVR5cGU9IlVwZGF0ZWQiIGRhdGVJbmZvcm1hdGlvbj0idjMiPjIwMjItMDUtMjNUMDA6MjM6MzhaPC9kYXRlPgogICAgPGRhdGUgZGF0ZVR5cGU9IkF2YWlsYWJsZSIgZGF0ZUluZm9ybWF0aW9uPSJ2MSI+MjAyMS0wNzwvZGF0ZT4KICA8L2RhdGVzPgogIDxyZXNvdXJjZVR5cGUgcmVzb3VyY2VUeXBlR2VuZXJhbD0iUHJlcHJpbnQiPkFydGljbGU8L3Jlc291cmNlVHlwZT4KICA8dmVyc2lvbj4zPC92ZXJzaW9uPgogIDxyaWdodHNMaXN0PgogICAgPHJpZ2h0cyByaWdodHNVUkk9Imh0dHA6Ly9jcmVhdGl2ZWNvbW1vbnMub3JnL2xpY2Vuc2VzL2J5LzQuMC8iIHJpZ2h0c0lkZW50aWZpZXJTY2hlbWU9IlNQRFgiIHJpZ2h0c0lkZW50aWZpZXI9IkNDLUJZLTQuMCI+Q3JlYXRpdmUgQ29tbW9ucyBBdHRyaWJ1dGlvbiA0LjAgSW50ZXJuYXRpb25hbDwvcmlnaHRzPgogIDwvcmlnaHRzTGlzdD4KICA8ZGVzY3JpcHRpb25zPgogICAgPGRlc2NyaXB0aW9uIGRlc2NyaXB0aW9uVHlwZT0iQWJzdHJhY3QiPkxhcmdlIE5laWdoYm9yaG9vZCBTZWFyY2ggKExOUykgaXMgYSBjb21iaW5hdG9yaWFsIG9wdGltaXphdGlvbiBoZXVyaXN0aWMgdGhhdCBzdGFydHMgd2l0aCBhbiBhc3NpZ25tZW50IG9mIHZhbHVlcyBmb3IgdGhlIHZhcmlhYmxlcyB0byBiZSBvcHRpbWl6ZWQsIGFuZCBpdGVyYXRpdmVseSBpbXByb3ZlcyBpdCBieSBzZWFyY2hpbmcgYSBsYXJnZSBuZWlnaGJvcmhvb2QgYXJvdW5kIHRoZSBjdXJyZW50IGFzc2lnbm1lbnQuIEluIHRoaXMgcGFwZXIgd2UgY29uc2lkZXIgYSBsZWFybmluZy1iYXNlZCBMTlMgYXBwcm9hY2ggZm9yIG1peGVkIGludGVnZXIgcHJvZ3JhbXMgKE1JUHMpLiBXZSB0cmFpbiBhIE5ldXJhbCBEaXZpbmcgbW9kZWwgdG8gcmVwcmVzZW50IGEgcHJvYmFiaWxpdHkgZGlzdHJpYnV0aW9uIG92ZXIgYXNzaWdubWVudHMsIHdoaWNoLCB0b2dldGhlciB3aXRoIGFuIG9mZi10aGUtc2hlbGYgTUlQIHNvbHZlciwgZ2VuZXJhdGVzIGFuIGluaXRpYWwgYXNzaWdubWVudC4gRm9ybXVsYXRpbmcgdGhlIHN1YnNlcXVlbnQgc2VhcmNoIHN0ZXBzIGFzIGEgTWFya292IERlY2lzaW9uIFByb2Nlc3MsIHdlIHRyYWluIGEgTmV1cmFsIE5laWdoYm9yaG9vZCBTZWxlY3Rpb24gcG9saWN5IHRvIHNlbGVjdCBhIHNlYXJjaCBuZWlnaGJvcmhvb2QgYXQgZWFjaCBzdGVwLCB3aGljaCBpcyBzZWFyY2hlZCB1c2luZyBhIE1JUCBzb2x2ZXIgdG8gZmluZCB0aGUgbmV4dCBhc3NpZ25tZW50LiBUaGUgcG9saWN5IG5ldHdvcmsgaXMgdHJhaW5lZCB1c2luZyBpbWl0YXRpb24gbGVhcm5pbmcuIFdlIHByb3Bvc2UgYSB0YXJnZXQgcG9saWN5IGZvciBpbWl0YXRpb24gdGhhdCwgZ2l2ZW4gZW5vdWdoIGNvbXB1dGUgcmVzb3VyY2VzLCBpcyBndWFyYW50ZWVkIHRvIHNlbGVjdCB0aGUgbmVpZ2hib3Job29kIGNvbnRhaW5pbmcgdGhlIG9wdGltYWwgbmV4dCBhc3NpZ25tZW50IGFtb25nc3QgYWxsIHBvc3NpYmxlIGNob2ljZXMgZm9yIHRoZSBuZWlnaGJvcmhvb2Qgb2YgYSBzcGVjaWZpZWQgc2l6ZS4gT3VyIGFwcHJvYWNoIG1hdGNoZXMgb3Igb3V0cGVyZm9ybXMgYWxsIHRoZSBiYXNlbGluZXMgb24gZml2ZSByZWFsLXdvcmxkIE1JUCBkYXRhc2V0cyB3aXRoIGxhcmdlLXNjYWxlIGluc3RhbmNlcyBmcm9tIGRpdmVyc2UgYXBwbGljYXRpb25zLCBpbmNsdWRpbmcgdHdvIHByb2R1Y3Rpb24gYXBwbGljYXRpb25zIGF0IEdvb2dsZS4gSXQgYWNoaWV2ZXMgJDJcdGltZXMkIHRvICQzNy44XHRpbWVzJCBiZXR0ZXIgYXZlcmFnZSBwcmltYWwgZ2FwIHRoYW4gdGhlIGJlc3QgYmFzZWxpbmUgb24gdGhyZWUgb2YgdGhlIGRhdGFzZXRzIGF0IGxhcmdlIHJ1bm5pbmcgdGltZXMuPC9kZXNjcmlwdGlvbj4KICA8L2Rlc2NyaXB0aW9ucz4KPC9yZXNvdXJjZT4=","url":"https://arxiv.org/abs/2107.10201","contentUrl":null,"metadataVersion":1,"schemaVersion":"http://datacite.org/schema/kernel-4","source":"mds","isActive":true,"state":"findable","reason":null,"viewCount":0,"viewsOverTime":[],"downloadCount":0,"downloadsOverTime":[],"referenceCount":0,"citationCount":1,"citationsOverTime":[{"year":"2026","total":1}],"partCount":0,"partOfCount":0,"versionCount":0,"versionOfCount":0,"created":"2022-02-21T14:35:46.000Z","registered":"2022-02-21T14:35:47.000Z","published":"2021","updated":"2022-05-23T01:18:02.000Z"},"relationships":{"client":{"data":{"id":"arxiv.content","type":"clients"}},"provider":{"data":{"id":"arxiv","type":"providers"}},"media":{"data":{"id":"10.48550/arxiv.2107.10201","type":"media"}},"references":{"data":[]},"citations":{"data":[{"id":"10.4230/lipics.cp.2026.18","type":"dois"}]},"parts":{"data":[]},"partOf":{"data":[]},"versions":{"data":[]},"versionOf":{"data":[]}}}}