Notice

This record has been edited as far as possible, missing data will be added when the version of record is issued.

Show simple item record

dc.contributor.author
Paat, Joseph
dc.contributor.author
Schlöter, Miriam
dc.contributor.author
Speakman, Emily
dc.date.accessioned
2021-07-20T22:22:38Z
dc.date.available
2021-07-15T10:31:47Z
dc.date.available
2021-07-20T22:22:38Z
dc.date.issued
2021
dc.identifier.issn
0025-5610
dc.identifier.issn
1436-4646
dc.identifier.other
10.1007/s10107-021-01658-7
en_US
dc.identifier.uri
http://hdl.handle.net/20.500.11850/494926
dc.description.abstract
Lattice-free gradient polyhedra can be used to certify optimality for mixed integer convex minimization models. We consider how to construct these polyhedra for unconstrained models with two integer variables under the assumption that all level sets are bounded. In this setting, a classic result of Bell, Doignon, and Scarf states the existence of a lattice-free gradient polyhedron with at most four facets. We present an algorithm for creating a sequence of gradient polyhedra, each of which has at most four facets, that finitely converges to a lattice-free gradient polyhedron. Each update requires constantly many gradient evaluations. Our updates imitate the gradient descent algorithm, and consequently, it yields a gradient descent type of algorithm for problems with two integer variables.
en_US
dc.language.iso
en
en_US
dc.publisher
Springer
en_US
dc.title
Constructing lattice-free gradient polyhedra in dimension two
en_US
dc.type
Journal Article
dc.date.published
2021-05-15
ethz.journal.title
Mathematical Programming
ethz.journal.abbreviated
Math. program.
ethz.size
25 p.
en_US
ethz.identifier.wos
ethz.publication.place
Heidelberg
en_US
ethz.publication.status
published
en_US
ethz.leitzahl
ETH Zürich::00002 - ETH Zürich::00012 - Lehre und Forschung::00007 - Departemente::02000 - Dep. Mathematik / Dep. of Mathematics::02502 - Institut für Operations Research / Institute for Operations Research::03873 - Weismantel, Robert / Weismantel, Robert
ethz.leitzahl.certified
ETH Zürich::00002 - ETH Zürich::00012 - Lehre und Forschung::00007 - Departemente::02000 - Dep. Mathematik / Dep. of Mathematics::02502 - Institut für Operations Research / Institute for Operations Research::03873 - Weismantel, Robert / Weismantel, Robert
ethz.date.deposited
2021-07-15T10:32:27Z
ethz.source
WOS
ethz.eth
yes
en_US
ethz.availability
Metadata only
en_US
ethz.rosetta.exportRequired
true
ethz.COinS
ctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.atitle=Constructing%20lattice-free%20gradient%20polyhedra%20in%20dimension%20two&rft.jtitle=Mathematical%20Programming&rft.date=2021&rft.issn=0025-5610&1436-4646&rft.au=Paat,%20Joseph&Schl%C3%B6ter,%20Miriam&Speakman,%20Emily&rft.genre=article&rft_id=info:doi/10.1007/s10107-021-01658-7&
 Search print copy at ETH Library

Files in this item

FilesSizeFormatOpen in viewer

There are no files associated with this item.

Publication type

Show simple item record