Algebraic and Geometric Ideas in Discrete Optimisation I

Duration: 46 mins 2 secs

Share this media item:

Embed this media item:

<iframe width="_width_" height="_height_" src="https://sms.cam.ac.uk/media/1520890/embed" frameborder="0" scrolling="no" allowfullscreen></iframe>

Choose size:

About this item

Available Formats

About this item

Description:	De Loera, J (University of California, Davis) Monday 15 July 2013, 14:00-14:45


Created:	2013-07-17 12:03
Collection:	Polynomial Optimisation
Publisher:	Isaac Newton Institute
Copyright:	De Loera, J
Language:	eng (English)


Abstract:	It is common knowledge that the understanding of the combinatorial geometry of convex bodies has helped speed up algorithms in discrete optimization. For example, cutting planes and facet-description of polyhedra have been crucial in the success of branch-and-bound algorithms for mixed integer linear programming. Another example, is how the ellipsoid method can be used to prove polynomiality results in combinatorial optimization. For the future, the importance of algebraic-combinatorial geometry in optimization appears even greater. In the past 5 years advances in algebraic-geometric algorithms have been used to prove unexpected new results on the computation of non-linear integer programs. These lectures will introduce the audience to new techniques. I will describe several algorithms and explain why we can now prove theorems that were beyond our reach before, mostly about integer optimization with non-linear objectives. I will also describe attempts to turn these two algorithms into practical computation, not just in theoretical results. This a nice story collecting results by various authors and now contained in our monograph recently published by SIAM-MOS.

Abstract:

It is common knowledge that the understanding of the combinatorial geometry of convex bodies has helped speed up algorithms in discrete optimization. For example, cutting planes and facet-description of polyhedra have been crucial in the success of branch-and-bound algorithms for mixed integer linear programming. Another example, is how the ellipsoid method can be used to prove polynomiality results in combinatorial optimization. For the future, the importance of algebraic-combinatorial geometry in optimization appears even greater.

In the past 5 years advances in algebraic-geometric algorithms have been used to prove unexpected new results on the computation of non-linear integer programs. These lectures will introduce the audience to new techniques. I will describe several algorithms and explain why we can now prove theorems that were beyond our reach before, mostly about integer optimization with non-linear objectives. I will also describe attempts to turn these two algorithms into practical computation, not just in theoretical results.

This a nice story collecting results by various authors and now contained in our monograph recently published by SIAM-MOS.

Available Formats

Format	Quality	Bitrate	Size
MPEG-4 Video	640x360	1.93 Mbits/sec	668.96 MB	View	Download
WebM	640x360	1.08 Mbits/sec	372.90 MB	View	Download
iPod Video	480x270	522.06 kbits/sec	176.02 MB	View	Download
MP3	44100 Hz	249.81 kbits/sec	84.29 MB	Listen	Download
Auto *	(Allows browser to choose a format it supports)