Gil Kalai’s blog

## A Diameter Problem (6): Abstract Objective Functions

Posted on November 4, 2008 by

George Dantzig and Leonid Khachyan

In this part we will not progress on the diameter problem that we discussed in the earlier posts but will rather describe a closely related problem for directed graphs associated with ordered families of sets. The role models for these directed graphs are the directed graphs of polytopes where the direction of the edges is described by a linear objective function.

### 7. Linear programming and the simplex algorithm.

Our diameter problem for families of sets was based on a mathematical abstraction (and a generalization) of the Hirsch Conjecture which asserts that the diameter of the graph $G(P)$ of a $d$-polytope $P$ with $n$ facets is at most $n-d$. Hirsch, in fact, made the conjecture also for graphs of unbounded polyhedra – namely the intersection of $n$ closed halfspaces in $R^d$. But in the unbounded case, Klee and Walkup found a counterexample with diameter $n-d+$ [$d/5$]. The abstract problem we considered extends also to the unbounded case and  $n-d+$ [$d/5$] is the best known lower bound for the abstract case as well. It is not known if there is a polynomial (in terms of $d$ and $n$) upper bound for the diameter of graphs of d-polytopes with n facets.

Hirsch’s conjecture was motivated by the simplex algorithm for linear programming.  Let us talk a little more about it: Linear programming is the problem of maximizing a linear objective function $\phi(x)=b_1x_1+ b_2 x_2 \dots +b_dx_d$ subject to a system of n linear inequalities in the variables $x_1,x_2,\dots,x_d$.

$a_{11}x_1 + x_{12}x_2 + \dots + x_{1d}x_d \le c_1$,

$a_{21}x_1 + x_{22}x_2 + \dots + x_{2d}x_d \le c_2$,

…

$a_{n1}x_1 + x_{n2}x_2 + \dots + x_{nd}x_d \le c_n$,

The set of solutions to the system of inequalities is a convex polyhedron. (If it is bounded it is a polytope.)  A linear objective function makes a graph of a polytope (or a polyhedron) into a digraph (directed graph). If you like graphs you would love digraphs, and if you like graphs of polytopes, you would like the digraphs associated with them.

The geometric description of Dantzig’s simplex algorithm is as follows: the system of inequalities describes a convex d-dimensional polyhedron $P$. (This polyhedron is called the feasible polyhedron.) The maximum of $\phi$ is attained at a face $F$ of $P$. We start with an initial vertex (extreme point) $v$ of the polyhedron and look at its neighbors in $G(P)$. Unless $v \in F$ there is a neighbor $u$ of $v$ that satisfies $\phi(u) > \phi (v)$. When you find such a vertex move from $v$ to $u$ and repeat!

### 8. Abstract objective functions and unique sink orientation.

Let $P$ be a simple d-polytope and let $\phi$ be a linear objective function which is not constant on any edge of the polytope. Remember, the graph of $P$, $G(P)$ is a $d$-regular graph. We can now direct every edge $u,v$ from $u$ to $v$ if $\phi (v) > \phi (u)$. Here are two important properties of this digraph.

(AC) It is acyclic! (no cycles)

(US’) It has a unique SINK, namely a unique vertex such that all edges containing it are directed towards it.

The unique sink property is in fact the property that enables the simplex algorithm to work!

When we consider a face of the polytope $F$ and its own graph $G(F)$ then again our linear objective function induces an orientation of the edges of $G(F)$ which is acyclic and also has the unique sink property. Every subgraph of an acyclic graph is acyclic. But having the unique sink property for a graph does not imply it for a subgraph. We can now describe the general unique sink properties of digraphs of polytopes:

(US) For every face F of the polytope, the directed graph induced on the vertices of $F$ has a unique sink.

A unique sink acyclic orientation of the graph of a polytope is an orientation of the edges of the graph which satisfies properties (AC) and (US).

An abstract objective function of a $d$-polytope is an ordering $<$ of the vertices of the polytope such that the directed graph obtained by directing an edge from $u$ to $v$ if  $u<v$ is a unique sink acyclic orientation. (Of course, coming from an ordering the orientation is automatically acyclic.)

### 9. Questions and answers regarding the simplex algorithm.

Q: What is a polyhedron, is it just a fancy name for a polytope?

A: A polyhedron is the intersection of closed half spaces in $R^d$. A bounded polyhedron is a polytope.

Q: How do you find the initial feasible vertex v?

A: Ohh, good point. Usually you need a first stage of the algorithm to reach a feasible vertex. This is sometimes referred to as Phase 1 of the algorithm, and moving from a feasible vertex to the optimal one is called Phase 2. But you can transform every LP problem to another one in which the origin is a feasible polyhedron so for the purpose of studying the worst-case behavior of the simplex algorithm it is enough to study phase 2.

Q: How do you choose to which neighbor to move?

A: Ahh, this is a good question. Often, there are many ways to do it and a rule for making the choice is called a pivot rule. Which pivot rule to take, for theoretical purposes as well as practical purposes is important.

Q: Is the simplex algorithm a polynomial time algorithm?

A: We do not know any pivot rule that leads to a polynomial algorithm in the sense that the number of pivot steps is bounded above by a polynomial function of $d$ and $n$.

Q: Is there a polynomial algorithm for LP?

A: Yes, Katchian proved in 1979 that the Nemirovski-Shor ellipsoid algorithm is a polynomial time algorithm for LP.

Q: Didn’t you neglect to mention some important things?

A: Quite a few. In particular, I ignored issues of degeneracy, for example if the feasible polyhedron is not simple.

Before we go on to describe an even more abstract objective functions, let me recall section 2 about the connection between the abstract combinatorial graphs based on families of sets and the graphs of polytopes. If this is already fresh in your memory you can safely skip it.

### 2. The connection of our abstract setting with the Hirsch’s Conjecture reminded

The Hirsch Conjecture asserts that the diameter of the graph G(P) of a d-polytope P with n facets is at most n-d. Not even a polynomial upper bound for the diameter in terms of d and n is known. Finding good upper bounds for the diameter of graphs of d-polytopes is one of the central open problems in the study of convex polytopes. If d is fixed then a linear bound in n is known, and the best bound in terms of d and n is $n^{\log d+1}$. We will come back to these results later.

One basic fact to remember is that for every d-polytope P, G(P) is a connected graph. As a matter of fact, a theorem of Balinski asserts that G(P)\$ is d-connected.

The combinatorial diameter problem I mentioned in an earlier post (and which is repeated below) is closely related. Let me now explain the connection.

Let P be a simple d-polytope. Suppose that P is determined by n inequalities, and that each inequality describes a facet of P. Now we can define a family $\cal F$ of subsets of {1,2,…,n} as follows. Let $E_1,E_2,\dots,E_n$ be the n inequalities defining the polytope P, and let $F_1,F_2,\dots, F_n$ be the n corresponding facets. Every vertex v of P belongs to precisely d facets (this is equivalent to P being a simple polytope). Let $S_v$ be the indices of the facets containing v, or, equivalently, the indices of the inequalities which are satisfied as equalities at v. Now, let $\cal F$ be the family of all sets $S_v$ for all vertices of the polytope P.

The following observations are easy.

(1) Two vertices v and w of P are adjacent in the graph of P if and only if $|S_v \cap S_w|=d-1$. Therefore, $G(P)=G({\cal F})$.

(2)  If A is a set of indices, then the vertices v of P such that $A \subset S_v$ are precisely the set of vertices of a lower dimensional face of P. This face is described by all the vertices of P which satisfy all the inequalities indexed by $i \in A$, or equivalently all vertices in P which belong to the intersection of the facets $F_i$ for $i \in A$.

Therefore, for every $A \subset N$, if ${\cal F}[A]$ is not empty the graph $G({\cal F}[A])$ is connected – this graph is just the graph of some lower dimensional polytope. This was the main assumption in our abstract problem.

### 10. Even more abstract objective functions.

We will not discuss actual pivot rules for linear programming in this thread of posts.  This is an interesting topic that we may discuss separately. Linear objective functions transform the graph of the polytope into a directed graph. We replaced graphs of polytopes by very abstract and general graphs associated to families of sets. What about digraphs of polytopes?

Let ${\cal F} = (S_1,S_2,\dots, S_t)$ be an ordered family of $d$-subsets of {1,2,…,n}. Define a digraph or a directed graph $G({\cal F})$ as a digraph whose vertex set is latex \cal F\$ and which has a directed edge from $S_i$ to $S_j$ if $|S_i \cap S_j|=d-1$.

Let ${\cal F}_r = (S_r,S_2,\dots S_t)$.

Make the following assumption:

(*) For every $r$, $G({\cal F_t})$ is connected. Moreover, for every $r$ and every subset $A \subset \{1,2,\dots. n\}$ the graph $G({\cal F}_r[A])$ is connected. (In words, the graph which corresponds to all sets in the family that come after $S_r$ and contain $A$ is connected.)

Now we can define a directed graph by orienting an edge $(S_i ,$ $S_j)$ from $S_i$ to $S_j$ if $i<j$.

Starting from a simple d-polytope $P$ with $n$ facets, we associated to $P$ a family of sets that correspond to the vertices of $P$. When we have an objective function $\phi$, we can order the vertices of $P$ and thus obtain an ordered family that satisfies the assumption (*).  If we start with a simple $d$ polytope with $n$ facets and order the sets which correspond to its vertices according to an abstract objective function we get a more general class of ordered families satisfying (*).

### 11. Shellability again

Remember the notion of shellability in Kimmo Errikson’s poem? Let $K$ be the ideal or simplicial complex spanned by the family $F$. So $K = \{ R \subset \{1,2,\dots, n\}: R \subset S_i$ for some $i, 1 \le i \le t \}$. To say that the ordering of $\cal F$ is an abstract objective function is equivalent to the statement that $K$ is shellable and the ordering of $S_1,S_2,\dots, S_t$ is a shelling order on $K$.

One important consequence of this observation is that not every family of sets satisfying our connectivity conditions can be ordered as to satisfy our new connectivity relation (*).

### 12. Short directed path?

Here is the directed version of our diameter problem. Given an ordered family of sets satisfying our condition (*), we can always have a directed path from every $S_r$ to $S_t$. Can we always guarantee a path of length $n$? A path of length bounded by some $n^c$ for some $c>0$?

### Like this:

This entry was posted in Combinatorics, Convex polytopes, Open problems and tagged Hirsch conjecture, Linear programming. Bookmark the permalink.

### 7 Responses to A Diameter Problem (6): Abstract Objective Functions

1. Pingback: A Diameter problem (7): The Best Known Bound « Combinatorics and more

2. Pingback: Lovasz’s Two Families Theorem « Combinatorics and more

3. Pingback: Telling a Simple Polytope From its Graph « Combinatorics and more

4. Pingback: The Polynomial Hirsch Conjecture: A proposal for Polymath3 « Combinatorics and more

5. Pingback: Subexponential Lower Bound for Randomized Pivot Rules! | Combinatorics and more

6. Pingback: Is Backgammon in P? | Combinatorics and more

7. Pingback: Remote Blogging: Efficiency of the Simplex Method: Quo vadis Hirsch conjecture? | Combinatorics and more

• ### Blogroll

%d bloggers like this:
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 107, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9146566987037659, "perplexity_flag": "head"}