# Sebastian Pokutta's Blog

Mathematics and related topics

## The Scottish Café revisited

This is a try to bring together mathematicians and alike in a virtual spot to discuss mathematics and research.

The Scottish Café (PolishKawiarnia Szkocka) was the café in Lwów (now Lviv) where, in the 1930s and 1940s, mathematicians from the Lwów School collaboratively discussedresearch problems, particularly in functional analysis and topology.

Stanislaw Ulam recounts that the tables of the café had marble tops, so they could write in pencil, directly on the table, during their discussions. To keep the results from being lost, and after becoming annoyed with their writing directly on the table tops, Stefan Banach‘s wife provided the mathematicians with a large notebook, which was used for writing the problems and answers and eventually became known as the Scottish Book. The book—a collection of solved, unsolved, and even probably unsolvable problems—could be borrowed by any of the guests of the café. Solving any of the problems was rewarded with prizes, with the most difficult and challenging problems having expensive prizes (during the Great Depression and on the eve of World War II), such as a bottle of fine brandy.[1]

For problem 153, which was later recognized as being closely related to Stefan Banach’s “basis problem“, Stanislaw Mazur offered the prize of a live goose. This problem was solved only in 1972 by Per Enflo, who was presented with the live goose in a ceremony that was broadcast throughout Poland.[2]

I have been thinking about “the scottish café” for a while and i was wondering whether it is possible to have “something” like this in a virtual, decentralized fashion. Last night I accidentally participated in a “google hangout” and I thought that this might be a good platform for this.

At this point I do not have any idea what a good setup and rules etc. is. But you are most welcome to join and provide your ideas and feedback.

A proposed initial setup could be either a classic seminar talk + discussion or free discussion about a pre-specified topic. The first one might be easier in terms of getting things started whereas the second one is more in the original spirit of the café. While I personally would prefer the second one in the mid-term it might be better to get things started with the first one.

Technological platform should be google+ with its post/hangout features.
The Scottish Café will be maintained by Lars Schewe and myself at the moment. However if you are interested in helping us to get things started, please drop us a line.

Written by Sebastian

February 3, 2012 at 12:45 pm

## On linear programming formulations for the TSP polytope

Next week I am planning to give a talk on our recent paper which is joint work with Samuel Fiorini, Serge Massar, Hans Raj Tiwary, and Ronald de Wolf where we consider linear and semidefinite extended formulations and we prove that any linear programming formulation of the traveling salesman polytope has super-polynomial size (independent of P-vs-NP). From the abstract:

We solve a 20-year old problem posed by M. Yannakakis and prove that there exists no polynomial-size linear program (LP) whose associated polytope projects to the traveling salesman polytope, even if the LP is not required to be symmetric. Moreover, we prove that this holds also for the maximum cut problem and the stable set problem. These results follow from a new connection that we make between one-way quantum communication protocols and semidefinite programming reformulations of LPs.

The history of this problem is quite interested. From Gerd Woeginger’s P-versus-NP page (See also Mike Trick’s blog post on Swart’s attempts):

In 1986/87 Ted Swart (University of Guelph) wrote a number of papers (some of them had the title: “P=NP”) that gave linear programming formulations of polynomial size for the Hamiltonian cycle problem. Since linear programming is polynomially solvable and Hamiltonian cycle is NP-hard, Swart deduced that P=NP.

In 1988, Mihalis Yannakakis closed the discussion with his paper “Expressing combinatorial optimization problems by linear programs” (Proceedings of STOC 1988, pp. 223-228). Yannakakis proved that expressing the traveling salesman problem by a symmetric linear program (as in Swart’s approach) requires exponential size. The journal version of this paper has been published in Journal of Computer and System Sciences 43, 1991, pp. 441-466.

In his paper, Yannakakis posed the question whether one can show such a lower bound unconditionally, i.e., without the symmetry assumption and Yannakakis conjectured that symmetry ‘should not help much’. This sounded reasonable however no proof was known. In 2010, to the surprise of many, Kaibel, Pashkovich, and Theis proved that there exist polytopes whose symmetric extension complexity (the number of facets of the polytope) is super-polynomial, whereas there exists asymmetric extended formulations that use only polynomially many inequalities; i.e., symmetry does matter. On top of that, the considered polytopes were closely related to the matching polytope (used by Yannakakis to establish the TSP result) which rekindled the discussion on the (unconditional) extension complexity of the travelling salesman polytope and Kaibel asked whether 0/1-polytopes have extended formulations with a polynomial number of inequalities in general or if there exist 0/1-polytopes that need a super-polynomial number of facets in any extension. Beware! This is not in contradiction or related to the P-vs.-NP question as we only talk about the number of inequalities and not the encoding length of the coefficients. This was settled by Rothvoss in 2011 by a very nice counting argument: there are 0/1-polytopes that need a super-polynomial number of inequalities in any extension.

To make the following slightly more formal, let ${P \subseteq {\mathbb R}^n}$ be a polytope (of some dimension). Then an extended formulation for ${P}$ is another polytope ${Q \subseteq {\mathbb R}^\ell}$ such that there exists a linear projection ${\pi}$ with ${\pi(Q) = P}$. The size of an extension ${Q}$ is now the number of facets of ${Q}$ and the extension complexity of ${P}$ (denoted by: ${\text{xc}(P)}$) is the minimum ${\ell}$ such that there exists an extension of size ${\ell}$. We are interested in ${\text{xc}(P)}$ where ${P}$ is the travelling salesman polytope. Our proof heavily relies on a connection between the extension complexity of a polytope and communication complexity (the basic connection was made by Yannakakis and it was later extended by Faenza, Fiorini, Grappe, and Tiwary and Fiorini, Kaibel, Pashkovich, Theis in 2011). In fact, suppose that we have an inner and outer description of our polytope ${P}$, say ${P = \text{conv}\{v_1, \dots v_n\} = \{x \in {\mathbb R}^n \mid Ax \leq b\}}$. Then we can define the slack matrix ${S(P)}$ as ${S_{ij} = b_i -A_i v_j}$, i.e., the slack of the vertices with respect to the inequalities. The extension complexity of a polytope is now equal to the nonnegative rank of ${S}$ which is essentially equivalent to determining the best protocol to compute the entries of ${S}$ in expectation (Alice gets a row index and Bob a column index). The latter can be bounded from below by the non-deterministic communication complexity and we use a certain matrix ${M_{ab} = (1-a^Tb)^2}$ which has large non-deterministic communication complexity (see de Wolf 2003). This matrix is special as it constitutes the slack for some valid inequalities for the correlation polytope which eventually leads to a exponential lower bound for the extension complexity of the correlation polytope. The latter is affine isomorphic to the cut polytope. Then via a reduction-like mechanism similar lower bounds are established for the stable set polytope (${\text{xc(stableSet)} = 2^{\Omega(n^{1/2})}}$) for a certain family of graphs and then we use the fact that the TSP polytope contains any stable set polytope as a face (Yannakakis) for suitably chosen parameters and we obtain ${\text{xc(TSP)} = 2^{\Omega(n^{1/4})}}$.

Here are the slides:

Written by Sebastian

January 5, 2012 at 3:17 pm

## UniGestalten initiative (Germany-specific)

The ‘Die Junge Akademie’ together with the ‘Stifterverband der Deutschen Wissenschaft’ has launched the very interesting initiative ‘UniGestalten’  to improve working and living at German universities. People can submit and discuss ideas for improving various aspects of teaching, research, administration, and more. From the homepage of the initiative (German):

Wir brauchen Leute, die vor- und nachdenken.
Für neue Perspektiven zum Leben und Arbeiten an der Uni!

Unser Ziel ist es, neue Perspektiven für den Alltag an unseren Hochschulen auszuloten und konkrete Lösungsvorschläge zu entwickeln. Wir wollen zeigen, dass nicht nur große strukturelle Entscheidungen in Wissenschaft, Wirtschaft und Politik etwas verändern können, sondern dass jeder Einzelne etwas bewegen kann. Wir setzen auf die Innovationskraft von Personen und auf die Lernfähigkeit der Organisation. Wir erwarten keinen allumfassenden Masterplan. Im Gegenteil: Wir glauben daran, dass auch kleine Ansätze viel verändern können. Von den Studierenden und Ehemaligen, über Lehrende und Forschende, Beschäftigte aus Technik und Verwaltung, bis hin zu den Partnern aus der Wirtschaft – jeder Einzelne hat seine eigenen Erfahrungen im Unibetrieb gesammelt und kann mit konkreten Ideen das Leben und Arbeiten an der Hochschule von morgen gestalten.

Ihr Beitrag kann eine ganz persönliche Initiative sein, ein konkreter Verbesserungsvorschlag oder ein interessantes Geschäftsmodell. Ihre Kommentare zu den Beiträgen sind uns jedoch genauso wichtig,

um die eingereichten Ideen weiterzuentwickeln. Jeder ist ein Teil dieser CommUNIty!

So if you happen to life/work/study at a German university you should definitely have a look and maybe even submit your own idea.

Written by Sebastian

November 6, 2011 at 10:14 am

Posted in Announcements

## CPLEX free for academic use

Probably I am not the first one to report this but CPLEX is now available for free for academics as part of IBM’s academic initiative (see here):

Full-version CPLEX now available free-of-charge to academics

Posted: Feb 18, 2010 08:30:03 PM

Effective February 15, 2010, IBM is offering no-charge full-version ILOG Optimization products via IBM’s Academic Initiative program (http://www.ibm.com/academicinitiative). This move builds on the availability of limited Teaching Editions available since August 2009, and now provides registered members with renewable one-year access to IBM ILOG OPL-CPLEX, CPLEX, CP Optimizer and CP for both teaching and research use. Registered members can access ILOG Optimization software at: https://www.ibm.com/developerworks/university/software/get_software.html, where they can search for ILOG Optimization or individual solvers by name. Depending on the search criteria, electronic assemblies will be retrieved for IBM ILOG OPL Development Studio, CPLEX, CP Optimizer or CP on all commercially available platforms. To run the software, members will also need to download a key from: https://www.ibm.com/developerworks/university/support/ilog.html, but are no longer required to install ILM. Note that as part of Academic Initiative, IBM also makes its professionally-developed training materials available for use in classrooms and labs at: https://www14.software.ibm.com/webapp/devtool/scholar/web/coursewarePickPage.do?source=ai-course-websphere.

The application is pretty forward and the verification of eligibility is supposed to take “3-5 business days”. But it seems that the accounts are approved much faster (at least in my case).

Written by Sebastian

February 22, 2010 at 2:21 pm

Tagged with , ,

## A polyhedral characterization of border bases

Tomorrow I will give a talk on a recent paper which is joint work with Gábor Braun from the Alfréd Rényi Institute of Mathematics. It deals with the polyhedral characterization of all admissible order ideals (and hence border bases) that exist for a given zero-dimensional ideal. As a hardness result, it also follows that determining an optimal order ideal (w.r.t. to a linear objective function) is NP-hard. This is in particular interesting as it shows that not only computing the L-stable span (the vector space approximation of the ideal) is hard but also choosing a ‘nice’ basis which is a mere basis transformation from a linear algebra point of view (see also my previous post for some more details). Here are the slides:

View this document on Scribd

Written by Sebastian

January 31, 2010 at 7:58 pm

## European Capital of Culture: Ruhr.2010

with one comment

The European Capital of Culture for 2010 is Essen in Germany, on behalf of the Ruhr Area (“Ruhrpott” or “Ruhrgebiet” as we say) and its several cities (e.g. Bochum, Dortmund, Gelsenkirchen, Duisburg, Oberhausen, …). The official homepage can be found here [9]. As I grew up in Essen and practically lived there the first “part” of my life I thought I take the opportunity and provide you with some background information and links, just in case you are in Germany in 2010 and you have a chance to visit that diverse and really interesting area. Unfortunately, some of the articles are in German only, but I tried to provide English resources whenever possible.

According to wikipedia, the Ruhr Area is the fourth largest urban area in Europe with some 7.3 million inhabitants. What is special about this area is its unique industry culture and the transformation in the 90’s away from heavy industry to a more service oriented area (see [2], [3], [4], German only). As you can imagine, this transition brought a lot of initial problems and desperation to people heavily relying on heavy industry for their income and the fact that those people could not be easily moved to different jobs (see [1], German only). Now that this transition is (almost) complete, the Ruhr Area presents its distinguished face to the world as the European Capital of Culture. Also check out the special issue on Spiegel ([3], German only) about Ruhr.2010.

Events and must-sees:

An event planer with events scheduled in 2010 can be found in [8] and following the same link, you can also find the Top-10 attractions in the Ruhrpott (according to Spiegel and I kinda agree).

Impressions from the Ruhr Area:

In [5] you can listen to some “typical” sounds of the Ruhr Area. These sound recordings were taken by Richard Ortmann and represent some of the day to day noises you would have heard (and partly still would hear today). Also check out his sound archive with a more comprehensive collection of sound nostalgia [6]. Probably one of the most famous songs about the Ruhr Area is Herbert Grönemeyer’s “Bochum” (about one of the big cities in this area):

Right now, 09.01.2010 15:47, there is a live show about Ruhr.2010 as the European Capital of Culture on ZDF (one of the German main tv stations). You can find it also in the ZDF mediathek [7] together with many other shows and pictures about the Ruhr Area where you can watch it for free.

Here are a few pictures from various photographers depicting the Ruhr Area:

References:

[1]: “Wir sind die Dinosaurier – und wir wollen nicht aussterben” – Spiegel 11.02.2007 (German only)
[2]: Von der stinkenden Brühe zum Lebenselexier – Spiegel 29.08.2007 (German only)
[3]: Kulturhauptstadt Ruhr.2010 – Spiegel 08.01.2010 (German only)
[4]: Industrie in XXL – Spiegel 22.06.2009 (German only)
[5]: Der Pulsschlag aus Stahl verklingt – Spiegel 20.10.2007 (German only – but for the sounds it does not matter)
[6]: Richard Ortmann – Sound Archive (German only – but for the sounds it does not matter)
[7]: ZDF mediathek’s Ruhr.2010 collection (tv shows and pictures)
[8]: Spiegel Ruhr.2010 event planer including Top 10 attractions (German only – but rather self-explaining)
[9]: Ruhr.2010 – official homepage

Written by Sebastian

January 9, 2010 at 4:39 pm

## GLPK 4.41 released

with one comment

A new version of the GNU Linear Programming Kit (GLPK)  has been released – see here for GLPK tutorials. An updated version of the GUSEK windows GUI will follow probably soon. From the release notes:

GLPK 4.41 — Release Information
********************************

Release date: Dec 21, 2009

GLPK (GNU Linear Programming Kit) is intended for solving large-scale
linear programming (LP), mixed integer linear programming (MIP), and
other related problems. It is a set of routines written in ANSI C and
organized as a callable library.

In this release:

The following new API routines were added:

glp_transform_row     transform explicitly specified row
glp_transform_col     transform explicitly specified column
glp_prim_rtest        perform primal ratio test
glp_dual_rtest        perform dual ratio test

For description of these new routines see a new edition of the
reference manual included in the distribution.

The following API routines are deprecated: lpx_transform_row,
lpx_transform_col, lpx_prim_ratio_test, lpx_dual_ratio_test.

Some improvements were made in the MIP solver (glp_intopt).

The SQL table driver used to read/write data in MathProg models
was changed to allow multiple arguments separated by semicolon
in SQL statements. Thanks to Xypron <xypron.glpk@gmx.de>.

Two new options were added to the glpsol stand-alone solver:
–seed value (to initialize the pseudo-random number generator
used in MathProg models with specified value), and
–ini filename (to use a basis previously saved with -w option
as an initial basis on solving similar LP’s).

Two new MathProg example models were included. Thanks to
Nigel Galloway <nigel_galloway@operamail.com> and Noli Sicad

Scripts to build GLPK with Microsoft Visual Studio 2010 for
both 32-bit and 64-bit Windows were included. Thanks to Xypron
<xypron.glpk@gmx.de> for contribution and testing.

See GLPK web page at <http://www.gnu.org/software/glpk/glpk.html>.

GLPK distribution can be ftp’ed from <ftp://ftp.gnu.org/gnu/glpk/> or
from some mirror ftp sites; see <http://www.gnu.org/order/ftp.html>.

UPDATE (01.01.2010): New version of GUSEK is also available:

I’ve updated the Gusek project on SourceForge:
http://gusek.sourceforge.net

Release 0.2.8 changes:
– GLPK updated to 4.41.
– Added Java files support (as in native SciTE).