Invited Session Thu.3.MA 001

Thursday, 15:15 - 16:45 h, Room: MA 001

Cluster 14: Mixed-integer nonlinear programming [...]

Mixed-integer nonlinear programming


Chair: Jon Lee



Thursday, 15:15 - 15:40 h, Room: MA 001, Talk 1

Shmuel Onn
Integer programming in polynomial time via Graver bases


I will overview our algorithmic theory which uses Graver bases to
solve linear and nonlinear integer programming problems in variable
dimension in polynomial time. I will demonstrate the power of this
theory by describing some of its many applications including to multiway
statistical table problems, multicommodity flows and stochastic integer
programming, and will show that this theory is universal and provides
a new parametrization of all of integer programming. I will also mention
a very recent drastic improvement from polynomial to cubic running time.
The talk draws from my recent monograph on nonlinear discrete optimization
and is based on several papers joint with several colleagues including
Berstein, De Loera, Hemmecke, Lee, Romanchuk, Rothblum and Weismantel.



Thursday, 15:45 - 16:10 h, Room: MA 001, Talk 2

Renata Sotirov
SDP relaxations for the graph partition problem


In [R. Sotirov. A powerful semidefinite programming relaxation for the graph partition problem. Manuscript 2011] we derived a semidefinite programming relaxation for the general graph partition problem (GPP) that is based on matrix lifting. This relaxation provides competitive bounds that can be computed with little computational effort for graphs with up till 100 vertices.
Here, we further investigate matrix and vector lifting SDP relaxations for the GPP on highly symmetric graphs, and improve the best known bounds for certain graphs with symmetry.



Thursday, 16:15 - 16:40 h, Room: MA 001, Talk 3

Raymond Hemmecke
N-fold integer programming in cubic time

Coauthors: Shmuel Onn, Lyubov Romanchuk


In this talk we present a cubic-time algorithm for solving N-fold integer programs together with some first computational experiments on its performance.


  There are three major facts that should be watched out for in all payday loans in the United States. Cialis Professional online is capableto release you reliably from the erection problems, its improved formula gives the new properties to the drug.