Sanjeeb Dash

Overview

Sanjeeb Dash

Title

Manager, Foundations of Optimization & Probability

Location

IBM Research - Yorktown Heights Yorktown Heights, NY USA

Bio

Research Interests

  • Integer Programming
    - Cutting planes; Routing and scheduling problems
  • Discrete Optimization for ML - Interpretable machine learning; Causal structure learning; Symbolic regression
  • Linear Programming & Semidefinite programming
    - Exact/Floating point LP solvers; semidefinite relaxations of IPs and Polynomial Optimization problems
  • Software for Mathematical Programming

Research Software

  • QSopt, a floating point LP solver.
  • QSopt_ex, an exact LP solver (returns rational solutions). A 'light/simplified' version can be found here.
  • AI-Descartes, a collection of codes to create symbolic expressions that fit data and are consistent with and axiom list.

Editorial Boards (current)

Editorial Boards (past)

  • Associate Editor, Operations Research (2016-2018)
  • Associate Editor, Naval Research Logistics (2015-2018)
  • Associate Editor, Mathematical Programming Computation (2008-2016)
  • Associate Editor, Operations Research Letters (2009-2019)

Conference Organization & Committees

Prizes

Work experience

Education

Summer Interns Mentored

  • Karan Srivastava (2024)
  • Yatharth Dubey (2021)
  • Rui Chen (2019, 2020)
  • Dabeen Lee (2017)
  • Sercan Yildiz (2015)
  • Merve Bodur (2013,2014)
  • Diego Moran (2012)
  • Marco Molinaro (2011)
  • Andrea Tramontani (2010)
  • Anureet Saxena (2007)
  • Ricardo Fukasawa (2006)
  • Marcos Goycoolea (2005)

Collaborators
David Applegate, Merve Bodur, Pierre Bonami, William Cook, Gerard Cornuejols, Daniel Espinoza, Matteo Fischetti, Ricardo Fukasawa, Tian Gao, Marcos Goycoolea, Oktay Gunluk, Jayant R. Kalagnanam , Dabeen Lee, Andrea Lodi, Jim Luedtke, Marco Molinaro, Diego Moran, Ramesh Neelamani, Christian Raack, Deepak Rajan, Chandra Reddy, Andre Rohe, Gregory Sorkin, Juan Pablo Vielma, Dennis Wei, Laurence Wolsey, Sercan Yildiz

Comments + Unpublished Preprints/Tech. Reports

  1. Symbolic Regression using Mixed-Integer Nonlinear Optimization, 2020. With V. Austel, C. Cornelio, J. Goncalves, L. Horesh, T. Josephson, N. Megiddo. arXiv:2006.06813
  2. Comments on: Perspectives on integer programming for time-dependent models, TOP 27, 2019, 174–177. (journal link)
  3. On nearly orthogonal lattice bases and Minkowski reduction. 2008. IBM Research Report RC24696; With Ramesh Neelamani, Gregory Sorkin.
  4. On the Matrix Cuts of Lovasz and Schrijver and their use in Integer Programming. Technical Report TR01-08, Rice University, 2001 (my Ph.D. thesis).

Conference + Workshop papers (not published in journals)

  1. Heavy Sets with Applications to Interpretable Machine Learning Diagnostics, To appear, AISTATS 2023. With D. M. Malioutov, D. Wei.
  2. Rule induction in knowledge graphs using linear programming. To appear, AAAI 2023 (oral presentation). With J. Goncalves. arXiv:2110.08245, slides, poster.
  3. Integer programming for causal structure learning in the presence of latent variables. ICML 2021 (Long presentation). PMLR 139:1550-1560. With R. Chen, T. Gao (presentation and slides)
  4. Multilabel classification by hierarchical partitioning and data-dependent grouping, Neurips 2020. With S. Ubaru, O. Gunluk, A. Mazumdar. (paper link)
  5. Cardinality constrained multilinear sets, In: Baïou M., Gendron B., Günlük O., Mahjoub A.R. (eds.) Combinatorial Optimization. ISCO 2020. Lecture Notes in Computer Science, vol 12176. Springer, Cham, 54-65. (paper link)
  6. Generalized linear rule models, ICML 2019, PMLR 97:6687-6696, With D. Wei, O. Gunluk, T. Gao. (pdf, suppementary material).
  7. Boolean decision rules via column generation, NIPS 2018 (Spotlight presentation). With O. Gunluk, D. Wei. (paper link) - Submission based on this paper won 1st Place in Inaugural FICO Explainable Machine Learning Challenge, 2019.
  8. Globally Optimal Symbolic Regression, NIPS Symposium on Interpretable Machine Learning, 2017. With V. Austel, O. Gunluk, L. Horesh, L. Liberti, G. Nannicini, B. Schieber. (pdf)
  9. A Model for Fusion and Code Motion in an Integrated Auto-Parallelizing Compiler. International Conference on Parallel Architectures and Compilation Techniques (PACT), 2010, Vienna. With U. Bondhugula, O. Gunluk, L. Renganarayana. (paper link)

Journal papers (and links to preprints/conference versions)

  1. Evolving scientific discovery by unifying data and background knowledge with AI Hilbert. Nature Communications 15, 5922 (2024). With R. Cory-Wright, C. Cornelio, B. El Khadir, L. Horesh. (journal link, ibm blog post, blog post on springer, webpage)
  2. On polytopes with linear rank with respect to generalizations of the split closure, Discrete Optimization 51, 2024, With Y. Dubey. (journal link,pdf)
  3. Convexifying multilinear sets with cardinality constraints: structural properties, nested case and extensions, Discrete Optimization 51, 2024.(journal link, pdf) With R. Chen, O. Gunluk.
  4. Interpretable and fair boolean rule sets via column generation, Journal of Machine Learning Research 24, 2023, 1–50. (journal link) With C. Lawless, O. Gunluk, D. Wei.
  5. Combining data and theory for derivable scientific discovery with AI-Descartes. Nature Communications, 14, 2023, Article 1777. With C. Cornelio, T. Josephson, J. Goncalves, V. Austel, K. Clarkson, N. Megiddo, L. Horesh. (journal link, ibm blog post, blog post on springer, webpage)
  6. Multilinear Sets with Two Monomials and Cardinality Constraints. Discrete Applied Mathematics, 324, 2023, 67-79. With R. Chen, O. Gunluk. (journal link, pdf)
  7. On a Generalization of the Chvátal-Gomory Closure. Mathematical Programming, 192, 2022, 149–175. Earlier in: IPCO 2020, Lecture Notes in Computer Science, vol 12125, Springer. With O. Gunluk, D. Lee. (journal link, Full paper pdf)
  8. Generalized Chvatal-Gomory closures for integer programs with bounds on variables, Mathematical Programming, 190, 2021, 393–425. With O. Gunluk, D. Lee (journal link, pdf)
  9. Lattice closures of polyhedra, Mathematical Programming, 181, 2020, 119–147. With O. Gunluk, D. A. Moran R. (journal link, pdf)
  10. Binary extended formulations for polyhedral mixed-integer sets, Mathematical Programming (Series B), 170, 2018, 207-236. With O. Gunluk, R. Hildebrand. (journal link, pdf)
  11. On the polyhedrality of closures of multi-branch split sets and other polyhedra with bounded max-facet-width. SIAM Journal on Optimization, 27, 2017, 1340-1361. With O. Gunluk, D. A. Moran R. (journal link, pdf)
  12. Optimization over structured subsets of positive semidefinite matrices via column generation. Discrete Optimization, 24, 2017, 129-151. With A. A. Ahmadi, G. Hall. (journal link, pdf)
  13. Cutting planes derived from extended LP formulations. Mathematical Programming, 161, 2017, 159-192. With M. Bodur, O. Gunluk. (journal link, pdf)
  14. Strengthened Benders cuts for stochastic integer programs with continuous recourse. Informs Journal on Computing, 29, 2017, 77-91. With M. Bodur, O. Gunluk, J. R. Luedtke. (journal link,pdf), supplementary material (journal link, pdf). Data/instances used in the paper: Data Explanation, CAP1, CAP2, SNIP.
  15. Learning interpretable classification rules with boolean compressed sensing. Chapter in Transparent data mining for big and small data (T. Cerquitelli, D. Quercia, F. Pascale, Eds.), pp. 95-121, Springer, 2017. With D. Malioutov, K. Varshney, A. Emad. (book link) Earlier in: Learning interpretable classification rules using sequential row sampling, ICASSP 2015, Screening for learning classification rules via boolean compressed sensing, ICASSP 2014.
  16. A new lift-and-project operator. European Journal on Operational Research, 257, 2016, 420-428. With M. Bodur, O. Gunluk. (journal link, pdf)
  17. On the polyhedrality of cross and quadrilateral closures. Mathematical Programming, 160, 2016, 245-270. With O. Gunluk, D. A. Moran R. (journal link, pdf) Earlier in: On some generalizations of the split closure. IPCO 2013, Lecture Notes in Computer Science 7801, 2013, 145-156. (pdf)
  18. The continuous knapsack set. Mathematical Programming, 155, 2016, 471-496. With O. Gunluk, L. Wolsey, (journal link, pdf)
  19. On quadratic unconstrained binary optimization problems defined on Chimera graphs, Optima 98, 2015, 2-6. With J. F. Puget. (pdf) Earlier in: A note on QUBO instances defined on Chimera graphs, 2013, arXiv:1306.1202 (version 2). (test data)
  20. On the relative strength of different generalizations of split cuts. Discrete Optimization 16, 2015, 36-50. With O. Gunluk, M. Molinaro. (journal link, pdf)
  21. Computational Experiments with Cross and Crooked Cross Cuts. INFORMS Journal on Computing, 26, 2014, 780-797. With O. Gunluk, J. P. Vielma. (journal link, pdf)
  22. Lattice-free sets, branching disjunctions, and mixed-integer programming. Mathematical Programming 145, 2014, 483-508. With N. B. Dobbs, O. Gunluk. T. J. Nowicki, G. M. Swirszcz. (journal link, pdf )
  23. On t-branch split cuts for mixed-integer programs. Mathematical Programming 141, 2013, 191-199. With O. Gunluk. (journal link,pdf)
  24. A time bucket formulation for the TSP with time windows. INFORMS Journal on Computing 24, 2012, 132-147. With A. Lodi, A. Tramontani, O. Gunluk. (journal link, pdf)
  25. The master equality polyhedron with multiple rows. Mathematical Programming 132, 2012, 125-152. With R. Fukasawa, O. Gunluk. (journal link, pdf)
  26. Two dimensional lattice-free cuts and asymmetric disjunctions for mixed-integer polyhedra. Mathematical Programming, 2012, 135, 221-254. With Santanu S. Dey, Oktay Gunluk. (journal link,pdf)
  27. Mixed integer rounding cuts and master group polyhedra. Combinatorial Optimization: Methods and Applications (NATO Science for Peace and Security Series - D: Information and Communication Security, Vol. 31; Ed., V. Chvatal), pp. 1-32, 2011, IOS Press, the Netherlands. Available as IBM Research Report RC24521, 2008.
  28. A note on the MIR closure and basic relaxations of polyhedra. Operations Research Letters 39 , 2011, 198-199. With O. Gunluk, C. Raack. (journal link, pdf)
  29. On mixed-integer sets with two integer variables. 2010. Operations Research Letters 39 , 2011, 305-309. With Santanu S. Dey, Oktay Gunluk.(journal link, pdf)
  30. A heuristic to separate rank-1 GMI cuts. Mathematical Programming Computation 2 , 2010, 231-257. With Marcos Goycoolea. (journal link, pdf)
  31. On a generalization of the master cyclic group polyhedron, Mathematical Programming 125, 2010, 1-30. With R. Fukasawa, O. Gunluk. (journal link, pdf). Earlier in: IPCO 2007, Lecture Notes in Computer Science 4513, 2007, 197-209.
  32. On the complexity of cutting plane proofs using split cuts. Operations Research Letters 38, 2010, 109-114.(journal link, pdf)
  33. MIR closures of polyhedral sets. Mathematical Programming 121, 2010, 33-60. With Oktay Gunluk, Andrea Lodi. (journal link, pdf). Erratum: Mathematical Programming 123, 2010, 485-486. Earlier in: On the MIR closure of polyhedra, IPCO 2007, Lecture Notes in Computer Science 4513, 2007, 337-351.
  34. Two-step MIR inequalities for mixed-integer programs. INFORMS Journal on Computing 22 , 2010, 236-249. With Marcos Goycoolea, Oktay Gunluk. (journal link, pdf)
  35. Numerically accurate Gomory mixed-integer cuts. Informs Journal On Computing 21, 2009, 641-649. With William Cook, Ricardo Fukasawa, Marcos Goycoolea. (journal link, pdf)
  36. On mixing inequalities: rank, closure and cutting plane proofs. SIAM Journal on Optimization 20, 2009, 1090-1109. With Oktay Gunluk. (pdf)
  37. On the strength of Gomory cuts as group cuts. Mathematical Programming 115, 2008, 387-407. With Oktay Gunluk. (pdf).
  38. Projected Chvatal-Gomory inequalities for mixed-integer programs. Mathematical Programming 113, 2008, 241-258. With Pierre Bonami, Gerard Cornuejols, Matteo Fischetti, Andrea Lodi. (pdf)
  39. Production design for plate products in the steel industry. IBM Journal of Research and Development 51, No. 3/4, 2007, 345-362. With Jayant Kalagnanam, Chandra Reddy, Sanghwa Song. (html, pdf)
  40. Exact solutions to linear programming problems. Operations Research Letters 35(6), 2007, 693-699. With David Applegate, William Cook, Daniel Espinoza. (pdf)
  41. On nearly orthogonal lattice bases, SIAM Journal on Discrete Mathematics 21, issue 1, 2007, 199-219. With Ramesh Neelamani, Richard Baraniuk. (pdf)
  42. Valid inequalities based on simple mixed-integer sets. Mathematical Programming 105, 2006, 29-53. With Oktay Gunluk. (journal link, pdf) Earlier in: IPCO 2004, Lecture Notes in Computer Science 3064, 2004, 33-45. (link)
  43. Valid inequalities based on the interpolation procedure. Mathematical Programming 106, 2006, 111-136. With Oktay Gunluk. (journal link,pdf).
  44. JPEG compression history estimation for color images. IEEE Transactions on Image Processing 15(6), 2006, 1365-1378. With R.Neelamani, R. de Queiroz, Z. Fan, and R. G. Baraniuk. (pdf)
  45. An exponential lower bound on the length of some classes of branch-and-cut proofs. Mathematics of Operations Research 30(3), 2005, 678-700; Earlier in IPCO 2002, Lecture Notes in Computer Science 2337, 2002, 145-160 (link). Preliminary version in: IBM Research Report RC22575, Sept 2002.
  46. Solution of a min-max vehicle routing problem. INFORMS Journal on Computing 14, 2002, 132-143. With David Applegate, William Cook, and Andre Rohe. (pdf)
  47. On the matrix-cut rank of polyhedra. Mathematics of Operations Research 26, February 2001, 19-30. With William Cook. (pdf)

Publications

Patents

Top collaborators

KC
Kenneth L Clarkson

Kenneth L Clarkson

Manager, Theory of Computation & Information; Distinguished Research Scientist
LH
Lior Horesh

Lior Horesh

Senior Manager, Mathematics & Theoretical Computer Science