<?xml version="1.0" encoding="utf-8"?>
<export-example>
  <doc>
    <id>9280</id>
    <completedYear/>
    <publishedYear>2023</publishedYear>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume>49</volume>
    <type>article</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>--</completedDate>
    <publishedDate>--</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Principled Deep Neural Network Training Through Linear Programming</title>
    <abstract language="eng">Deep learning has received much attention lately due to the impressive empirical performance achieved by training algorithms. Consequently, a need for a better theoretical understanding of these problems has become more evident and multiple works in recent years have focused on this task. In this work, using a unified framework, we show that there exists a polyhedron that simultaneously encodes, in its facial structure, all possible deep neural network training problems that can arise from a given architecture, activation functions, loss function, and sample size. Notably, the size of the polyhedral representation depends only linearly on the sample size, and a better dependency on several other network parameters is unlikely. Using this general result, we compute the size of the polyhedral encoding for commonly used neural network architectures. Our results provide a new perspective on training problems through the lens of polyhedral theory and reveal strong structure arising from these problems.</abstract>
    <parentTitle language="eng">Discrete Optimization</parentTitle>
    <identifier type="doi">10.1016/j.disopt.2023.100795</identifier>
    <enrichment key="PeerReviewed">yes</enrichment>
    <enrichment key="opus.source">publish</enrichment>
    <author>Daniel Bienstock</author>
    <submitter> Spiegel</submitter>
    <author>Gonzalo Muñoz</author>
    <author>Sebastian Pokutta</author>
    <collection role="persons" number="pokutta">Pokutta, Sebastian</collection>
    <collection role="institutes" number="ais2t">AI in Society, Science, and Technology</collection>
  </doc>
  <doc>
    <id>9692</id>
    <completedYear/>
    <publishedYear>2024</publishedYear>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst>255</pageFirst>
    <pageLast>266</pageLast>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume>16</volume>
    <type>article</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>--</completedDate>
    <publishedDate>--</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">The MIP workshop 2023 computational competition on reoptimization</title>
    <abstract language="eng">This paper describes the computational challenge developed for a computational competition held in 2023 for the 20th anniversary of the Mixed Integer Programming Workshop. The topic of this competition was reoptimization, also known as warm starting, of mixed integer linear optimization problems after slight changes to the input data for a common formulation. The challenge was to accelerate the proof of optimality of the modified instances by leveraging the information from the solving processes of previously solved instances, all while creating high-quality primal solutions. Specifically, we discuss the competition’s format, the creation of public and hidden datasets, and the evaluation criteria. Our goal is to establish a methodology for the generation of benchmark instances and an evaluation framework, along with benchmark datasets, to foster future research on reoptimization of mixed integer linear optimization problems.</abstract>
    <parentTitle language="eng">Mathematical Programming Computation</parentTitle>
    <identifier type="doi">10.1007/s12532-024-00256-w</identifier>
    <enrichment key="PeerReviewed">yes</enrichment>
    <enrichment key="opus.source">publish</enrichment>
    <author>Suresh Bolusani</author>
    <submitter>Christoph Spiegel</submitter>
    <author>Mathieu Besançon</author>
    <author>Ambros Gleixner</author>
    <author>Timo Berthold</author>
    <author>Claudia D'Ambrosio</author>
    <author>Gonzalo Muñoz</author>
    <author>Joseph Paat</author>
    <author>Dimitri Thomopulos</author>
    <collection role="persons" number="berthold">Berthold, Timo</collection>
    <collection role="projects" number="MODAL-SynLab">MODAL-SynLab</collection>
    <collection role="projects" number="MODAL-Gesamt">MODAL-Gesamt</collection>
    <collection role="institutes" number="ais2t">AI in Society, Science, and Technology</collection>
  </doc>
  <doc>
    <id>8391</id>
    <completedYear/>
    <publishedYear>2018</publishedYear>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>article</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>--</completedDate>
    <publishedDate>--</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Principled Deep Neural Network Training through Linear Programming</title>
    <abstract language="eng">Deep Learning has received significant attention due to its impressive performance in many state-of-the-art learning tasks. Unfortunately, while very powerful, Deep Learning is not well understood theoretically and in particular only recently results for the complexity of training deep neural networks have been obtained. In this work we show that large classes of deep neural networks with various architectures (e.g., DNNs, CNNs, Binary Neural Networks, and ResNets), activation functions (e.g., ReLUs and leaky ReLUs), and loss functions (e.g., Hinge loss, Euclidean loss, etc) can be trained to near optimality with desired target accuracy using linear programming in time that is exponential in the input data and parameter space dimension and polynomial in the size of the data set; improvements of the dependence in the input dimension are known to be unlikely assuming P≠NP, and improving the dependence on the parameter space dimension remains open. In particular, we obtain polynomial time algorithms for training for a given fixed network architecture. Our work applies more broadly to empirical risk minimization problems which allows us to generalize various previous results and obtain new complexity results for previously unstudied architectures in the proper learning setting.</abstract>
    <enrichment key="opus.source">publish</enrichment>
    <enrichment key="opus.doi.autoCreate">false</enrichment>
    <enrichment key="opus.urn.autoCreate">true</enrichment>
    <author>Daniel Bienenstock</author>
    <author>Gonzalo Muñoz</author>
    <author>Sebastian Pokutta</author>
    <collection role="persons" number="pokutta">Pokutta, Sebastian</collection>
    <collection role="institutes" number="Mathematical Algorithmic Intelligence">Mathematical Algorithmic Intelligence</collection>
    <collection role="institutes" number="ais2t">AI in Society, Science, and Technology</collection>
  </doc>
  <doc>
    <id>8625</id>
    <completedYear/>
    <publishedYear>2022</publishedYear>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst>89</pageFirst>
    <pageLast>118</pageLast>
    <pageNumber/>
    <edition/>
    <issue>1</issue>
    <volume>192</volume>
    <type>article</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>--</completedDate>
    <publishedDate>--</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">On generalized surrogate duality in mixed-integer nonlinear programming</title>
    <abstract language="eng">The most important ingredient for solving mixed-integer nonlinear programs (MINLPs) to global ϵ-optimality with spatial branch and bound is a tight, computationally tractable relaxation. Due to both theoretical and practical considerations, relaxations of MINLPs are usually required to be convex. Nonetheless, current optimization solvers can often successfully handle a moderate presence of nonconvexities, which opens the door for the use of potentially tighter nonconvex relaxations. In this work, we exploit this fact and make use of a nonconvex relaxation obtained via aggregation of constraints: a surrogate relaxation. These relaxations were actively studied for linear integer programs in the 70s and 80s, but they have been scarcely considered since. We revisit these relaxations in an MINLP setting and show the computational benefits and challenges they can have. Additionally, we study a generalization of such relaxation that allows for multiple aggregations simultaneously and present the first algorithm that is capable of computing the best set of aggregations. We propose a multitude of computational enhancements for improving its practical performance and evaluate the algorithm’s ability to generate strong dual bounds through extensive computational experiments.</abstract>
    <parentTitle language="eng">Mathematical Programming</parentTitle>
    <identifier type="doi">10.1007/s10107-021-01691-6</identifier>
    <enrichment key="PeerReviewed">yes</enrichment>
    <enrichment key="AcceptedDate">2021-06-28</enrichment>
    <enrichment key="opus.source">publish</enrichment>
    <author>Benjamin Müller</author>
    <submitter>Ambros Gleixner</submitter>
    <author>Gonzalo Muñoz</author>
    <author>Maxime Gasse</author>
    <author>Ambros Gleixner</author>
    <author>Andrea Lodi</author>
    <author>Felipe Serrano</author>
    <collection role="projects" number="MODAL-SynLab">MODAL-SynLab</collection>
    <collection role="projects" number="MODAL-Gesamt">MODAL-Gesamt</collection>
    <collection role="institutes" number="ais2t">AI in Society, Science, and Technology</collection>
  </doc>
  <doc>
    <id>9892</id>
    <completedYear/>
    <publishedYear>2025</publishedYear>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst>189</pageFirst>
    <pageLast>222</pageLast>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume>210</volume>
    <type>article</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>2024-07-08</completedDate>
    <publishedDate>--</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Monoidal strengthening and unique lifting in MIQCPs</title>
    <parentTitle language="eng">Mathematical Programming B</parentTitle>
    <identifier type="doi">10.1007/s10107-024-02112-0</identifier>
    <enrichment key="PeerReviewed">yes</enrichment>
    <enrichment key="opus.source">publish</enrichment>
    <author>Antonia Chmiela</author>
    <submitter>Christoph Spiegel</submitter>
    <author>Gonzalo Muñoz</author>
    <author>Felipe Serrano</author>
    <collection role="projects" number="MODAL-SynLab">MODAL-SynLab</collection>
    <collection role="projects" number="MODAL-Gesamt">MODAL-Gesamt</collection>
    <collection role="institutes" number="ais2t">AI in Society, Science, and Technology</collection>
  </doc>
  <doc>
    <id>9432</id>
    <completedYear/>
    <publishedYear>2023</publishedYear>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst>549</pageFirst>
    <pageLast>586</pageLast>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume>197</volume>
    <type>article</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>--</completedDate>
    <publishedDate>--</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">On the implementation and strengthening of intersection cuts for QCQPs</title>
    <parentTitle language="eng">Mathematical Programming B</parentTitle>
    <identifier type="doi">10.1007/s10107-022-01808-5</identifier>
    <enrichment key="PeerReviewed">yes</enrichment>
    <enrichment key="opus.source">publish</enrichment>
    <author>Antonia Chmiela</author>
    <submitter>Christoph Spiegel</submitter>
    <author>Gonzalo Muñoz</author>
    <author>Felipe Serrano</author>
    <collection role="projects" number="MODAL-SynLab">MODAL-SynLab</collection>
    <collection role="projects" number="MODAL-Gesamt">MODAL-Gesamt</collection>
    <collection role="institutes" number="ais2t">AI in Society, Science, and Technology</collection>
  </doc>
  <doc>
    <id>8959</id>
    <completedYear/>
    <publishedYear>2023</publishedYear>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst>87</pageFirst>
    <pageLast>99</pageLast>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume>13904</volume>
    <type>conferenceobject</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>--</completedDate>
    <publishedDate>--</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Monoidal strengthening and unique lifting in MIQCPs</title>
    <abstract language="eng">Using the recently proposed maximal quadratic-free sets and the well-known monoidal strengthening procedure, we show how to improve inter- section cuts for quadratically-constrained optimization problems by exploiting integrality requirements. We provide an explicit construction that allows an efficient implementation of the strengthened cuts along with computational results showing their improvements over the standard intersection cuts. We also show that, in our setting, there is unique lifting which implies that our strengthening procedure is generating the best possible cut coefficients for the integer variables.</abstract>
    <parentTitle language="eng">Integer Programming and Combinatorial Optimization. IPCO 2023.</parentTitle>
    <identifier type="doi">10.1007/978-3-031-32726-1_7</identifier>
    <enrichment key="PeerReviewed">yes</enrichment>
    <enrichment key="AcceptedDate">20.01.2023</enrichment>
    <enrichment key="opus.source">publish</enrichment>
    <enrichment key="PreprintUrn">urn:nbn:de:0297-zib-89130</enrichment>
    <enrichment key="Series">Lecture Notes in Computer Science</enrichment>
    <author>Antonia Chmiela</author>
    <submitter>Antonia Chmiela</submitter>
    <author>Gonzalo Muñoz</author>
    <author>Felipe Serrano</author>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="projects" number="MODAL-SynLab">MODAL-SynLab</collection>
    <collection role="projects" number="MODAL-Gesamt">MODAL-Gesamt</collection>
    <collection role="institutes" number="ais2t">AI in Society, Science, and Technology</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
  </doc>
  <doc>
    <id>8601</id>
    <completedYear/>
    <publishedYear>2021</publishedYear>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst>134</pageFirst>
    <pageLast>147</pageLast>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume>22</volume>
    <type>conferenceobject</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>--</completedDate>
    <publishedDate>--</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">On the implementation and strengthening of intersection cuts for QCQPs</title>
    <abstract language="eng">The generation of strong linear inequalities for QCQPs has been recently tackled by a number of authors using the intersection cut paradigm - a highly studied tool in integer programming whose flexibility has triggered these renewed efforts in non-linear settings. In this work, we consider intersection cuts using the recently proposed construction of maximal quadratic-free sets. Using these sets, we derive closed-form formulas to compute intersection cuts which allow for quick cut-computations by simply plugging-in parameters associated to an arbitrary quadratic inequality being violated by a vertex of an LP relaxation. Additionally, we implement a cut-strengthening procedure that dates back to Glover and evaluate these techniques with extensive computational experiments.</abstract>
    <parentTitle language="eng">Integer Programming and Combinatorial Optimization: 22nd International Conference, IPCO 2021</parentTitle>
    <identifier type="doi">10.1007/978-3-030-73879-2_10</identifier>
    <enrichment key="PeerReviewed">yes</enrichment>
    <enrichment key="AcceptedDate">2021-01-26</enrichment>
    <enrichment key="opus.source">publish</enrichment>
    <enrichment key="PreprintUrn">urn:nbn:de:0297-zib-79994</enrichment>
    <author>Antonia Chmiela</author>
    <submitter>Antonia Chmiela</submitter>
    <author>Gonzalo Muñoz</author>
    <author>Felipe Serrano</author>
    <collection role="projects" number="MODAL-SynLab">MODAL-SynLab</collection>
    <collection role="projects" number="MODAL-Gesamt">MODAL-Gesamt</collection>
    <collection role="institutes" number="ais2t">AI in Society, Science, and Technology</collection>
  </doc>
  <doc>
    <id>7999</id>
    <completedYear/>
    <publishedYear>2021</publishedYear>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>--</completedDate>
    <publishedDate>--</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">On the implementation and strengthening of intersection cuts for QCQPs</title>
    <abstract language="eng">The generation of strong linear inequalities for QCQPs has been recently tackled by a number of authors using the intersection cut paradigm - a highly studied tool in integer programming whose flexibility has triggered these renewed efforts in non-linear settings. In this work, we consider intersection cuts using the recently proposed construction of maximal quadratic-free sets. Using these sets, we derive closed-form formulas to compute intersection cuts which allow for quick cut-computations by simply plugging-in parameters associated to an arbitrary quadratic inequality being violated by a vertex of an LP relaxation. Additionally, we implement a cut-strengthening procedure that dates back to Glover and evaluate these techniques with extensive computational experiments.</abstract>
    <identifier type="urn">urn:nbn:de:0297-zib-79994</identifier>
    <identifier type="doi">10.1007/978-3-030-73879-2_10</identifier>
    <enrichment key="PeerReviewed">no</enrichment>
    <enrichment key="opus.source">publish</enrichment>
    <enrichment key="SourceTitle">Integer Programming and Combinatorial Optimization: 22nd International Conference, IPCO 2021, pp. 134-147, Vol.22, 2021</enrichment>
    <author>Antonia Chmiela</author>
    <submitter>Antonia Chmiela</submitter>
    <author>Gonzalo Muñoz</author>
    <author>Felipe Serrano</author>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Intersection cuts</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>QCQPs</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Quadratic-free sets</value>
    </subject>
    <collection role="msc" number="90C20">Quadratic programming</collection>
    <collection role="msc" number="90C26">Nonconvex programming, global optimization</collection>
    <collection role="msc" number="90C30">Nonlinear programming</collection>
    <collection role="projects" number="MODAL-SynLab">MODAL-SynLab</collection>
    <collection role="projects" number="MODAL-Gesamt">MODAL-Gesamt</collection>
    <collection role="projects" number="EnBA-M">EnBA-M</collection>
    <collection role="institutes" number="ais2t">AI in Society, Science, and Technology</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/7999/ZIBReport_20-29.pdf</file>
  </doc>
</export-example>
