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

 

Abstract:
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

 

Abstract:
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

 

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

 

  signature loans . But it is worth noting that these tests were carried out on the blood cells. Therefore, it's too early to say about scientific evidence of Viagra influence on blood clots.