Posets: Optimize dimension()

f29946bc-ee7b-48cd-9abc-3445948c551d commented 6 years ago

Done now:

For dimension 1 check if the poset is chain; for dimension 2 check if the incomparability graph is a comparability graph for some other poset. Only then proceed to use MILP and hypergraphs.
Remove internal check from the function.

Done earlier:

To doc add a mention about this being NP-complete.
Add a randomized check to tests/*.

To be done later:

Do at least series-parallel decomposition first, compute by parts.
For lattices run irreducibles_poset() first.

CC: @fchapoton @tscrim

Component: combinatorics

Author: Jori Mäntysalo

Branch/Commit: c66804e

Reviewer: Martin Rubey

Issue created by migration from https://trac.sagemath.org/ticket/25562

f29946bc-ee7b-48cd-9abc-3445948c551d commented 6 years ago

Branch: u/jmantysalo/dim-optimize

f29946bc-ee7b-48cd-9abc-3445948c551d commented 6 years ago

Commit: 42eee49

f29946bc-ee7b-48cd-9abc-3445948c551d commented 6 years ago

Description changed:

--- 
+++ 
@@ -1,9 +1,18 @@
-For dimension 1 check if the poset is chain; for dimension 2 check if the incomparability graph is a comparability graph for some other poset. Only then proceed to use MILP and hypergraphs.
+Done now:

-Remove internal check from the function, add a randomized check to `tests/*`.
+- For dimension 1 check if the poset is chain; for dimension 2 check if the incomparability graph is a comparability graph for some other poset. Only then proceed to use MILP and hypergraphs.

-Do at least series-parallel decomposition first, compute by parts.
+- Remove internal check from the function.

-For lattices run `irreducibles_poset()` first.
+Done earlier:

-To doc add a mention about this being NP-complete.
+- To doc add a mention about this being NP-complete.
+
+- Add a randomized check to `tests/*`.
+
+To be done later:
+
+- Do at least series-parallel decomposition first, compute by parts.
+
+- For lattices run `irreducibles_poset()` first.
+

f29946bc-ee7b-48cd-9abc-3445948c551d commented 6 years ago

Author: Jori Mäntysalo

f29946bc-ee7b-48cd-9abc-3445948c551d commented 6 years ago

New commits:

42eee49 Some optimizations for dimension.

f29946bc-ee7b-48cd-9abc-3445948c551d commented 6 years ago

comment:3

I forgot timings. I tested with PP = list(Posets(7)) and before the patch it took about 17 seconds to run sum(P.dimension() for P in PP). After the patch it dropped below 4 seconds.

mantepse commented 6 years ago

comment:4

Hi Jori,

I tried your patch, it looks good. I have a few very minor and trivial documentation suggestions, reproduced below, use them as you see fit.

diff --git a/src/sage/combinat/posets/posets.py b/src/sage/combinat/posets/posets.py
index 022e95e668..f64827d098 100644
--- a/src/sage/combinat/posets/posets.py
+++ b/src/sage/combinat/posets/posets.py
@@ -2968,11 +2968,11 @@ class FinitePoset(UniqueRepresentation, Parent):
         Return the dimension of the Poset.

         The (Dushnik-Miller) dimension of a poset is the minimal
-        number of total orders so that the poset can be defined as
-        "intersection" of all of them. Mathematically said, dimension
-        of a poset defined on a set `X` of points is the smallest
-        integer `n` such that there exists `P_1,...,P_n` linear
-        extensions of `P` satisfying the following property:
+        number of total orders so that the poset is their
+        "intersection".  More precisely, the dimension of a poset
+        defined on a set `X` of points is the smallest integer `n`
+        such that there exist linear extensions `P_1,...,P_n` of `P`
+        satisfying:

         .. MATH::

@@ -3035,8 +3035,9 @@ class FinitePoset(UniqueRepresentation, Parent):
             sage: Poset( (L[0], lambda x, y: all(l.index(x) < l.index(y) for l in L)) ) == P
             True

-        According to Schnyder's theorem, the poset (of height 2) of a graph has
-        dimension `\leq 3` if and only if the graph is planar::
+        According to Schnyder's theorem, the incidence poset (of
+        height 2) of a graph has dimension `\leq 3` if and only if
+        the graph is planar::

             sage: G = graphs.CompleteGraph(4)
             sage: P = Poset(DiGraph({(u,v):[u,v] for u,v,_ in G.edges()}))
@@ -3048,6 +3049,13 @@ class FinitePoset(UniqueRepresentation, Parent):
             sage: P.dimension() # not tested - around 4s with CPLEX
             4

+        The smallest poset of dimension 4, all other posets with at
+        most 8 elements have smaller dimension::
+
+            sage: P = Poset((range(8), sorted([[i,j+4] for i in range(4) for j in range(4) if i != j])))
+            sage: P.dimension()
+            4
+
         TESTS:

         Empty Poset::
@@ -3056,22 +3064,23 @@ class FinitePoset(UniqueRepresentation, Parent):
             0
             sage: Poset().dimension(certificate=True)
             (0, [])
+
         """
         if self.cardinality() == 0:
             return (0, []) if certificate else 0
         if self.is_chain():
             return (1, self.list()) if certificate else 1

-        # Current bound on the chromatic number of the hypergraph
+        # current bound on the chromatic number of the hypergraph
         k = 2
-        # If a realizer is not needed, we can optimize little
+        # if a realizer is not needed, we can optimize a little
         if not certificate:
-            # Polynomial time check for dimension 2
+            # polynomial time check for dimension 2
             from sage.graphs.comparability import greedy_is_comparability as is_comparability
             if is_comparability(self._hasse_diagram.transitive_closure().to_undirected().complement()):
                 return 2
             k = 3
-            # Know max values for dimension
+            # known upper bound for dimension
             max_value = max(self.cardinality() // 2, self.width())

         from sage.numerical.mip import MixedIntegerLinearProgram, MIPSolverException