Commits

Volker Braun committed aff7889

fixed chained inequalities for MIP

  • Participants
  • Parent commits 9739d8c

Comments (0)

Files changed (7)

+trac_13653_exception_fix.patch
 trac_13646_fix_mip.patch
 trac_12533_arbitrary_precision_LP_solver_backend_for_5.3_vb.patch
+trac_13650_base_ring.patch
+trac_13650_normalize_coefficients.patch
+trac_12091_constraints_parents.patch
 13579_secure_tmp.patch
 trac_13579_fix_test_executable.patch
 trac_13211_fix_gap_doctests.patch

File trac_11763-polyhedra_coercion_folded.2.patch

 # User Volker Braun <vbraun@stp.dias.ie>
 # Date 1315501129 14400
 # Node ID 72fa3dd63afb47e375297e85483bc1358eacf998
-# Parent 29434d3b8ee58b4beb9ca6a64334c6f766c9665e
+# Parent 1b1e12bf62ad00310f4a66f4b9d1d0b93e1c038b
 Trac #11763: Add ZZ as allowed base ring for polyhedra
 * * *
 Trac #11763: Parents for polyhedra
              [0 1 1]
              [1 0 1]
              [1 1 0]
-@@ -321,168 +302,112 @@
+@@ -292,168 +273,112 @@
              Vrep = face.element.ambient_Vrepresentation()
              if len(Vrep) == 2:
                  set_adjacent(Vrep[0], Vrep[1])
      def _is_subpolyhedron(self, other):
          """
          Test whether ``self`` is a (not necessarily strict)
-@@ -505,19 +430,16 @@
+@@ -476,19 +401,16 @@
              sage: Q._is_subpolyhedron(P)
              True
          """
          - ``**kwds`` -- optional keyword parameters.
  
          See :func:`render_2d`, :func:`render_3d`, :func:`render_4d`
-@@ -541,10 +463,8 @@
+@@ -512,10 +434,8 @@
          raise NotImplementedError('Plotting of '+str(self.ambient_dim())+
                                    '-dimensional polyhedra not implemented')
  
      def _repr_(self):
          """
          Return a description of the polyhedron.
-@@ -553,10 +473,10 @@
+@@ -524,10 +444,10 @@
  
              sage: poly_test = Polyhedron(vertices = [[1,2,3,4],[2,1,3,4],[4,3,2,1]])
              sage: poly_test._repr_()
          """
          desc = ''
          if self.n_vertices()==0:
-@@ -564,8 +484,10 @@
+@@ -535,8 +455,10 @@
          else:
              desc += 'A ' + repr(self.dim()) + '-dimensional polyhedron'
          desc += ' in '
          desc += '^' + repr(self.ambient_dim())
  
          if self.n_vertices()>0:
-@@ -573,14 +495,14 @@
+@@ -544,14 +466,14 @@
              desc += repr(self.n_vertices())
              if self.n_vertices()==1: desc += ' vertex'
              else:                    desc += ' vertices'
              if self.n_lines()>0:
                  if self.n_rays()>0: desc += ", "
                  else:               desc += " and "
-@@ -590,7 +512,6 @@
+@@ -561,7 +483,6 @@
  
          return desc
  
      def cdd_Hrepresentation(self):
          """
          Write the inequalities/equations data of the polyhedron in
-@@ -618,18 +539,21 @@
+@@ -589,18 +510,21 @@
          try:
              cdd_type = self._cdd_type
          except AttributeError:
          OUTPUT:
  
          A string. If you save the output to filename.ext then you can
-@@ -652,14 +576,18 @@
+@@ -623,14 +547,18 @@
          try:
              cdd_type = self._cdd_type
          except AttributeError:
      def n_equations(self):
          """
          Return the number of equations. The representation will
-@@ -672,13 +600,9 @@
+@@ -643,13 +571,9 @@
              sage: p.n_equations()
              1
          """
      def n_inequalities(self):
          """
          Return the number of inequalities. The representation will
-@@ -690,29 +614,16 @@
+@@ -661,29 +585,16 @@
              sage: p = Polyhedron(vertices = [[1,0,0],[0,1,0],[0,0,1]])
              sage: p.n_inequalities()
              3
      def n_vertices(self):
          """
          Return the number of vertices. The representation will
-@@ -724,14 +635,9 @@
+@@ -695,14 +606,9 @@
              sage: p.n_vertices()
              2
          """
      def n_rays(self):
          """
          Return the number of rays. The representation will
-@@ -743,14 +649,9 @@
+@@ -714,14 +620,9 @@
              sage: p.n_rays()
              1
          """
      def n_lines(self):
          """
          Return the number of lines. The representation will
-@@ -762,12 +663,7 @@
+@@ -733,12 +634,7 @@
              sage: p.n_lines()
              1
          """
  
      def Hrepresentation(self, index=None):
          """
-@@ -775,29 +671,29 @@
+@@ -746,29 +642,29 @@
          either an inequality or a equation.
  
          INPUT:
  
      def Hrep_generator(self):
          """
-@@ -805,7 +701,7 @@
+@@ -776,7 +672,7 @@
          (inequalities or equations).
  
          EXAMPLES::
              sage: p = polytopes.n_cube(3)
              sage: p.Hrep_generator().next()
              An inequality (0, 0, -1) x + 1 >= 0
-@@ -813,7 +709,7 @@
+@@ -784,7 +680,7 @@
          for H in self.Hrepresentation():
              yield H
  
      def n_Hrepresentation(self):
          """
          Return the number of objects that make up the
-@@ -833,18 +729,17 @@
+@@ -804,18 +700,17 @@
          """
          return len(self.Hrepresentation())
  
          The optional argument is an index in
          `0...n_Vrepresentation()`. If present, the V-representation
          object at the given index will be returned. Without an
-@@ -858,12 +753,12 @@
+@@ -829,12 +724,12 @@
              sage: p.Vrepresentation(0) == p.Vrepresentation() [0]
              True
          """
      def n_Vrepresentation(self):
          """
          Return the number of objects that make up the
-@@ -883,7 +778,6 @@
+@@ -854,7 +749,6 @@
          """
          return len(self.Vrepresentation())
  
      def Vrep_generator(self):
          """
          Returns an iterator over the objects of the V-representation
-@@ -901,9 +795,8 @@
+@@ -872,9 +766,8 @@
          for V in self.Vrepresentation():
              yield V
  
          Return the list of face indices (i.e. indices of
          H-representation objects) and the indices of faces adjacent to
          them.
-@@ -918,6 +811,10 @@
+@@ -889,6 +782,10 @@
  
              sage: p = polytopes.permutahedron(4)
              sage: p.facial_adjacencies()[0:3]
              [[0, [1, 2, 5, 10, 12, 13]], [1, [0, 2, 5, 7, 9, 11]], [2, [0, 1, 10, 11]]]
              sage: f0 = p.Hrepresentation(0)
              sage: f0.index() == 0
-@@ -926,6 +823,8 @@
+@@ -897,6 +794,8 @@
              sage: p.facial_adjacencies()[0] == f0_adjacencies
              True
          """
          try:
              return self._facial_adjacencies
          except AttributeError:
-@@ -935,11 +834,10 @@
+@@ -906,11 +805,10 @@
                    ] for h in self.Hrepresentation() ]
              return self._facial_adjacencies
  
          .. NOTE::
  
              Instead of working with face/vertex indices, it is
-@@ -957,6 +855,9 @@
+@@ -928,6 +826,9 @@
  
              sage: p = Polyhedron(vertices = [[5,0,0],[0,5,0],[5,5,0],[0,0,0],[2,2,5]])
              sage: p.facial_incidences()
              [[0, [0, 1, 3, 4]],
               [1, [0, 1, 2]],
               [2, [0, 2, 3]],
-@@ -981,6 +882,8 @@
+@@ -952,6 +853,8 @@
              sage: p.incidence_matrix().column(4)
              (0, 1, 1, 0, 1)
          """
          try:
              return self._facial_incidences
          except AttributeError:
-@@ -990,7 +893,6 @@
+@@ -961,7 +864,6 @@
                    ] for h in self.Hrepresentation() ]
              return self._facial_incidences
  
      def vertex_adjacencies(self):
          """
          Return a list of vertex indices and their adjacent vertices.
-@@ -1015,6 +917,9 @@
+@@ -986,6 +888,9 @@
  
              sage: permuta3 = Polyhedron(vertices = permutations([1,2,3,4]))
              sage: permuta3.vertex_adjacencies()[0:3]
              [[0, [1, 2, 6]], [1, [0, 3, 7]], [2, [0, 4, 8]]]
              sage: v0 = permuta3.Vrepresentation(0)
              sage: v0.index() == 0
-@@ -1025,6 +930,8 @@
+@@ -996,6 +901,8 @@
              sage: permuta3.vertex_adjacencies()[0] == v0_adjacencies
              True
          """
          try:
              return self._vertex_adjacencies
          except AttributeError:
-@@ -1034,11 +941,10 @@
+@@ -1005,11 +912,10 @@
                    ] for v in self.Vrepresentation() ]
              return self._vertex_adjacencies
  
          .. NOTE::
  
              Instead of working with face/vertex indices, you can use
-@@ -1049,6 +955,9 @@
+@@ -1020,6 +926,9 @@
  
              sage: p = polytopes.n_simplex(3)
              sage: p.vertex_incidences()
              [[0, [0, 1, 2]], [1, [0, 1, 3]], [2, [0, 2, 3]], [3, [1, 2, 3]]]
              sage: v0 = p.Vrepresentation(0)
              sage: v0.index() == 0
-@@ -1056,6 +965,8 @@
+@@ -1027,6 +936,8 @@
              sage: p.vertex_incidences()[0] == [ v0.index(), [h.index() for h in v0.incident()] ]
              True
          """
          try:
              return self._vertex_incidences
          except AttributeError:
-@@ -1065,14 +976,13 @@
+@@ -1036,14 +947,13 @@
                    ] for v in self.Vrepresentation() ]
              return self._vertex_incidences
  
          A generator of the inequality Hrepresentation objects.
  
          EXAMPLES::
-@@ -1093,24 +1003,48 @@
+@@ -1064,24 +974,48 @@
              if H.is_inequality():
                  yield H
  
              sage: ieqs[0]
              [-6, 0, 1, 1, 1]
              sage: ieqs[-1]
-@@ -1118,26 +1052,25 @@
+@@ -1089,26 +1023,25 @@
              sage: ieqs == [list(x) for x in p3.inequality_generator()]
              True
          """
      def equation_generator(self):
          """
          Return a generator for the linear equations satisfied by the
-@@ -1154,31 +1087,45 @@
+@@ -1125,31 +1058,45 @@
              if H.is_equation():
                  yield H
  
  
      def linearities(self):
          """
-@@ -1192,42 +1139,41 @@
+@@ -1163,42 +1110,41 @@
  
              sage: test_p = Polyhedron(vertices = [[1,2,3,4],[2,1,3,4],[4,3,2,1],[3,4,1,2]])
              sage: test_p.linearities()
      def vertex_generator(self):
          """
          Return a generator for the vertices of the polyhedron.
-@@ -1257,7 +1203,68 @@
+@@ -1228,7 +1174,68 @@
          for V in self.Vrepresentation():
              if V.is_vertex():
                  yield V
  
      def ray_generator(self):
          """
-@@ -1274,34 +1281,48 @@
+@@ -1245,34 +1252,48 @@
              if V.is_ray():
                  yield V
  
  
      def line_generator(self):
          """
-@@ -1317,36 +1338,47 @@
+@@ -1288,36 +1309,47 @@
              if V.is_line():
                  yield V
  
          OUTPUT:
  
          A generator for pairs of vertices, one pair per edge.
-@@ -1368,45 +1400,41 @@
+@@ -1339,45 +1371,41 @@
                  if self.vertex_adjacency_matrix()[i,j] == 0: continue
                  yield (obj[i], obj[j])
  
  
      def ambient_dim(self):
          r"""
-@@ -1418,9 +1446,8 @@
+@@ -1389,9 +1417,8 @@
              sage: poly_test.ambient_dim()
              4
          """
      def dim(self):
          """
          Return the dimension of the polyhedron.
-@@ -1432,29 +1459,10 @@
+@@ -1403,29 +1430,10 @@
              3
              sage: simplex.ambient_dim()
              4
      def vertex_adjacency_matrix(self):
          """
          Return the binary matrix of vertex adjacencies.
-@@ -1468,11 +1476,11 @@
-             [1 1 1 0 1]
-             [1 1 1 1 0]
+@@ -1470,11 +1478,11 @@
+             (0, 0, 0, 0, 1) A ray in the direction (1, 1)
+             (0, 0, 1, 1, 0) A vertex at (3, 0)
          """
 -        if '_V_adjacency_matrix' not in self.__dict__:
 -            self._init_vertex_adjacency_matrix()
      def facet_adjacency_matrix(self):
          """
          Return the adjacency matrix for the facets and hyperplanes.
-@@ -1486,11 +1494,9 @@
+@@ -1488,11 +1496,9 @@
              [1 1 1 0 1]
              [1 1 1 1 0]
          """
      def incidence_matrix(self):
          """
          Return the incidence matrix.
-@@ -1503,7 +1509,7 @@
+@@ -1505,7 +1511,7 @@
              :meth:`Vrepresentation`
  
          EXAMPLES::
              sage: p = polytopes.cuboctahedron()
              sage: p.incidence_matrix()
              [0 0 1 1 0 1 0 0 0 0 1 0 0 0]
-@@ -1535,18 +1541,13 @@
+@@ -1537,18 +1543,13 @@
              sage: p.incidence_matrix() [2,0]   # note: not symmetric
              0
          """
  
      def base_ring(self):
          """
-@@ -1560,84 +1561,13 @@
+@@ -1562,84 +1563,13 @@
          EXAMPLES::
  
              sage: triangle = Polyhedron(vertices = [[1,0],[0,1],[1,1]])
      @cached_method
      def center(self):
          """
-@@ -1694,14 +1624,13 @@
+@@ -1696,14 +1626,13 @@
          distance measure.
  
          EXAMPLES::
      def is_compact(self):
          """
          Test for boundedness of the polytope.
-@@ -1717,7 +1646,6 @@
+@@ -1719,7 +1648,6 @@
          """
          return self.n_rays()==0 and self.n_lines()==0
  
      def is_simple(self):
          """
          Test for simplicity of a polytope.
-@@ -1741,9 +1669,9 @@
+@@ -1743,9 +1671,9 @@
              adj = [a for a in v.neighbors()]
              if len(adj) != self.dim():
                  return False
      def gale_transform(self):
          """
          Return the Gale transform of a polytope as described in the
-@@ -1763,7 +1691,7 @@
+@@ -1765,7 +1693,7 @@
              sage: p2 = p.prism()
              sage: p2.gale_transform()
              [(1, 0), (0, 1), (-1, -1), (-1, 0), (0, -1), (1, 1)]
          REFERENCES:
  
              Lectures in Geometric Combinatorics, R.R.Thomas, 2006, AMS Press.
-@@ -1771,7 +1699,7 @@
+@@ -1773,7 +1701,7 @@
          if not self.is_compact(): raise ValueError('Not a polytope.')
  
          A = matrix(self.n_vertices(),
          A = A.transpose()
          A_ker = A.right_kernel()
          return A_ker.basis_matrix().transpose().rows()
-@@ -1800,14 +1728,14 @@
+@@ -1802,14 +1730,14 @@
          - ``fine`` -- boolean (default: ``False``). Whether the
            triangulations must be fine, that is, make use of all points
            of the configuration.
            * ``True``: Only regular triangulations.
  
            * ``False``: Only non-regular triangulations.
-@@ -1826,7 +1754,7 @@
+@@ -1828,7 +1756,7 @@
          :class:`~sage.geometry.triangulation.point_configuration.Triangulation`. The
          indices in the triangulation correspond to the
          :meth:`Vrepresentation` objects.
          EXAMPLES::
  
              sage: cube = polytopes.n_cube(3)
-@@ -1841,7 +1769,7 @@
+@@ -1843,7 +1771,7 @@
              [A vertex at (-1, -1, -1), A vertex at (-1, -1, 1),
               A vertex at (-1, 1, -1), A vertex at (1, 1, 1)]
              sage: Polyhedron(simplex_vertices)
          """
          if not self.is_compact():
              raise NotImplementedError('I can only triangulate compact polytopes.')
-@@ -1870,18 +1798,24 @@
+@@ -1872,18 +1800,24 @@
  
              sage: Polyhedron(vertices = [[5,0,0],[0,5,0],[5,5,0],[2,2,5]]
              ...             ).triangulated_facial_incidences()
              [[0, [1, 2, 5]], [0, [2, 5, 3]], [0, [5, 3, 4]], [1, [0, 1, 2]],
               [2, [0, 2, 3]], [3, [0, 3, 4]], [4, [0, 4, 5]], [5, [0, 1, 5]]]
          """
-@@ -1936,7 +1870,6 @@
+@@ -1938,7 +1872,6 @@
          self._triangulated_facial_incidences = t_fac_incs
          return t_fac_incs
  
      def simplicial_complex(self):
          """
          Return a simplicial complex from a triangulation of the polytope.
-@@ -1968,56 +1901,134 @@
+@@ -1970,56 +1903,134 @@
          return SimplicialComplex(vertex_set = self.n_vertices(),
                                   maximal_faces = [x[1] for x in self.triangulated_facial_incidences()])
  
  
          OUTPUT:
  
-@@ -2030,66 +2041,68 @@
+@@ -2032,66 +2043,68 @@
               sage: p = Polyhedron(vertices = [[t,t^2,t^3] for t in srange(2,6)])
               sage: p.vertex_generator().next()
               A vertex at (2, 4, 8)
      def convex_hull(self, other):
          """
          Return the convex hull of the set-theoretic union of the two
-@@ -2116,12 +2129,9 @@
+@@ -2118,12 +2131,9 @@
          hull_vertices = self.vertices() + other.vertices()
          hull_rays = self.rays() + other.rays()
          hull_lines = self.lines() + other.lines()
      def intersection(self, other):
          """
          Return the intersection of one polyhedron with another.
-@@ -2134,42 +2144,54 @@
+@@ -2136,42 +2146,54 @@
  
          The intersection.
  
          EXAMPLES::
  
              sage: cube = polytopes.n_cube(3)
-@@ -2190,7 +2212,7 @@
+@@ -2192,7 +2214,7 @@
  
          return Polyhedron(vertices=new_vertices, rays=new_rays,
                            lines=new_lines,
  
  
      def _make_polyhedron_face(self, Vindices, Hindices):
-@@ -2207,8 +2229,8 @@
+@@ -2209,8 +2231,8 @@
            face.
  
          OUTPUT:
          whether the input data actually defines a face.
  
          EXAMPLES::
-@@ -2217,18 +2239,19 @@
+@@ -2219,18 +2241,19 @@
              sage: square._make_polyhedron_face((0,2), (1,))
              <0,2>
          """
  
          In the case of a full-dimensional polytope, the faces are
          pairs (vertices, inequalities) of the spanning vertices and
-@@ -2263,7 +2286,7 @@
+@@ -2265,7 +2288,7 @@
          * Lines are removed before calling
            :func:`Hasse_diagram_from_incidences`, and then added back
            to each face V-representation except for the "empty face".
          * Equations are removed before calling
            :func:`Hasse_diagram_from_incidences`, and then added back
            to each face H-representation.
-@@ -2299,14 +2322,14 @@
+@@ -2301,14 +2324,14 @@
              (A vertex at (-1, -1), A vertex at (1, -1))
              sage: a_face.ambient_Hrepresentation()
              (An inequality (0, 1) x + 1 >= 0,)
          Note that if the polyhedron contains lines then there is a
          dimension gap between the empty face and the first non-empty
          face in the face lattice::
-@@ -2356,7 +2379,7 @@
+@@ -2358,7 +2381,7 @@
          REFERENCES:
  
          ..  [KP2002]
              Volker Kaibel and Marc E. Pfetsch, "Computing the Face
              Lattice of a Polytope from its Vertex-Facet Incidences",
              Computational Geometry: Theory and Applications, Volume
-@@ -2364,29 +2387,24 @@
+@@ -2366,29 +2389,24 @@
              http://portal.acm.org/citation.cfm?id=763203 and free of
              charge at http://arxiv.org/abs/math/0106043
          """
          atoms_vertices = [ Vindex_to_atom[v.index()] for v in self.vertex_generator() ]
          equations = [ e.index() for e in self.equation_generator() ]
          lines     = [ l.index() for l in self.line_generator() ]
-@@ -2400,18 +2418,96 @@
+@@ -2402,18 +2420,96 @@
              return self._make_polyhedron_face(Vindices, Hindices)
  
          from sage.geometry.hasse_diagram import Hasse_diagram_from_incidences
          Returns a vector whose ``i``-th entry is the number of
          ``i``-dimensional faces of the polytope.
  
-@@ -2422,13 +2518,9 @@
+@@ -2424,13 +2520,9 @@
              sage: p.f_vector()
              (1, 7, 12, 7, 1)
          """
      def vertex_graph(self):
          """
          Return a graph in which the vertices correspond to vertices
-@@ -2443,25 +2535,21 @@
+@@ -2445,25 +2537,21 @@
              sage: s4.is_eulerian()
              True
          """
              sage: p
              A 3-dimensional polyhedron in QQ^3 defined as the convex hull of 5 vertices
              sage: p.polar()
-@@ -2469,10 +2557,9 @@
+@@ -2471,10 +2559,9 @@
          """
          assert self.is_compact(), "Not a polytope."
  
  
      def pyramid(self):
          """
-@@ -2480,8 +2567,10 @@
+@@ -2482,8 +2569,10 @@
  
          EXAMPLES::
  
              sage: egyptian_pyramid.n_vertices()
              5
              sage: for v in egyptian_pyramid.vertex_generator(): print v
-@@ -2492,11 +2581,9 @@
+@@ -2494,11 +2583,9 @@
              A vertex at (1, 0, 0)
          """
          new_verts = \
  
      def bipyramid(self):
          """
-@@ -2518,7 +2605,7 @@
+@@ -2520,7 +2607,7 @@
               [0, 0, 1, 0],
               [0, 1, 0, 0],
               [1, 0, 0, 0]]
          Now check that bipyramids of cross-polytopes are cross-polytopes::
  
              sage: q2 = [list(v) for v in polytopes.cross_polytope(4).vertex_generator()]
-@@ -2531,9 +2618,7 @@
+@@ -2533,9 +2620,7 @@
              [[-1] + list(self.center())]
          new_rays = [[0] + r for r in self.rays()]
          new_lines = [[0] + list(l) for l in self.lines()]
  
      def prism(self):
          """
-@@ -2544,7 +2629,7 @@
+@@ -2546,7 +2631,7 @@
              sage: square = polytopes.n_cube(2)
              sage: cube = square.prism()
              sage: cube
              sage: hypercube = cube.prism()
              sage: hypercube.n_vertices()
              16
-@@ -2553,10 +2638,9 @@
+@@ -2555,10 +2640,9 @@
          new_verts.extend( [ [0] + v for v in self.vertices()] )
          new_verts.extend( [ [1] + v for v in self.vertices()] )
          new_rays =        [ [0] + r for r in self.rays()]
  
      def projection(self):
          """
-@@ -2573,7 +2657,6 @@
+@@ -2575,7 +2659,6 @@
          self.projection = Projection(self)
          return self.projection
  
      def render_solid(self, **kwds):
          """
          Return a solid rendering of a 2- or 3-d polytope.
-@@ -2592,7 +2675,6 @@
+@@ -2594,7 +2677,6 @@
              return proj.render_fill_2d(**kwds)
          raise ValueError, "render_solid is only defined for 2 and 3 dimensional polyhedra."
  
      def render_wireframe(self, **kwds):
          """
          For polytopes in 2 or 3 dimensions, return the edges
-@@ -2612,7 +2694,6 @@
+@@ -2614,7 +2696,6 @@
              return proj.render_outline_2d(**kwds)
          raise ValueError, "render_wireframe is only defined for 2 and 3 dimensional polyhedra."
  
      def schlegel_projection(self, projection_dir = None, height = 1.1):
          """
          Returns a projection object whose transformed coordinates are
-@@ -2629,12 +2710,12 @@
+@@ -2631,12 +2712,12 @@
          """
          proj = self.projection()
          if projection_dir == None:
  
      def lrs_volume(self, verbose = False):
          """
-@@ -2655,7 +2736,7 @@
+@@ -2657,7 +2738,7 @@
              2.0
  
          REFERENCES:
               David Avis's lrs program.
          """
          if is_package_installed('lrs') != True:
-@@ -2686,7 +2767,6 @@
+@@ -2688,7 +2769,6 @@
  
          raise ValueError, "lrs did not return a volume"
  
      def contains(self, point):
          """
          Test whether the polyhedron contains the given ``point``.
-@@ -2703,7 +2783,7 @@
+@@ -2705,7 +2785,7 @@
          Boolean.
  
          EXAMPLES::
              sage: P = Polyhedron(vertices=[[1,1],[1,-1],[0,0]])
              sage: P.contains( [1,0] )
              True
-@@ -2724,17 +2804,17 @@
+@@ -2726,17 +2806,17 @@
              True
              sage: ray.contains(['hello', 'kitty'])   # no common ring for coordinates
              False
              sage: full.contains([])
              True
              sage: full.contains([0])
-@@ -2746,17 +2826,16 @@
+@@ -2748,17 +2828,16 @@
              if len(point)>0:
                  return False
              else:
      def interior_contains(self, point):
          """
          Test whether the interior of the polyhedron contains the
-@@ -2766,15 +2845,15 @@
+@@ -2768,15 +2847,15 @@
          :meth:`relative_interior_contains`.
  
          INPUT:
              sage: P = Polyhedron(vertices=[[0,0],[1,1],[1,-1]])
              sage: P.contains( [1,0] )
              True
-@@ -2793,7 +2872,7 @@
+@@ -2795,7 +2874,7 @@
          The empty polyhedron needs extra care, see trac #10238::
  
              sage: empty = Polyhedron(); empty
              sage: empty.interior_contains([])
              False
          """
-@@ -2803,17 +2882,16 @@
+@@ -2805,17 +2884,16 @@
              if len(point)>0:
                  return False
              else:
      def relative_interior_contains(self, point):
          """
          Test whether the relative interior of the polyhedron
-@@ -2822,15 +2900,15 @@
+@@ -2824,15 +2902,15 @@
          See also :meth:`contains` and :meth:`interior_contains`.
  
          INPUT:
              sage: P = Polyhedron(vertices=[(1,0), (-1,0)])
              sage: P.contains( (0,0) )
              True
-@@ -2844,7 +2922,7 @@
+@@ -2846,7 +2924,7 @@
          The empty polyhedron needs extra care, see trac #10238::
  
              sage: empty = Polyhedron(); empty
              sage: empty.relative_interior_contains([])
              False
          """
-@@ -2854,11 +2932,11 @@
+@@ -2856,11 +2934,11 @@
              if len(point)>0:
                  return False
              else:
          for eq in self.equation_generator():
              if not eq.contains(p):
                  return False
-@@ -2872,7 +2950,7 @@
+@@ -2874,7 +2952,7 @@
      def is_simplex(self):
          r"""
          Return whether the polyhedron is a simplex.
          EXAMPLES::
  
              sage: Polyhedron([(0,0,0), (1,0,0), (0,1,0)]).is_simplex()
-@@ -2884,34 +2962,34 @@
+@@ -2886,34 +2964,34 @@
          """
          return self.is_compact() and (self.dim()+1==self.n_vertices())
  
          INPUT:
  
          - ``envelope`` -- boolean (default: ``False``). If the
-@@ -2942,7 +3020,7 @@
+@@ -2944,7 +3022,7 @@
          is returned.
  
          EXAMPLES:
          First, a polyhedron with integral vertices::
  
              sage: P = Polyhedron( vertices = [(1, 0), (0, 1), (-1, 0), (0, -1)])
-@@ -2970,33 +3048,13 @@
+@@ -2972,33 +3050,13 @@
          if not self.is_compact():
              raise NotImplementedError, 'Only compact lattice polytopes are allowed.'
  
              vertices = []
              for v in self.vertex_generator():
                  vbox = [ set([floor(x),ceil(x)]) for x in v ]
-@@ -3005,8 +3063,7 @@
+@@ -3007,8 +3065,7 @@
  
          # construct the (enveloping) lattice polytope
          from sage.geometry.lattice_polytope import LatticePolytope
  
      def _integral_points_PALP(self):
          r"""
-@@ -3015,12 +3072,12 @@
+@@ -3017,12 +3074,12 @@
          This method is for testing purposes and will eventually be removed.
  
          OUTPUT:
              sage: Polyhedron(vertices=[(-1,-1),(1,0),(1,1),(0,1)])._integral_points_PALP()
              [(-1, -1), (0, 1), (1, 0), (1, 1), (0, 0)]
              sage: Polyhedron(vertices=[(-1/2,-1/2),(1,0),(1,1),(0,1)]).lattice_polytope(True).points()
-@@ -3053,7 +3110,7 @@
+@@ -3055,7 +3112,7 @@
  
          - ``integral`` -- Boolean (default: ``False``). Whether to
            only allow integral coordinates in the bounding box.
          OUTPUT:
  
          A pair of tuples ``(box_min, box_max)`` where ``box_min`` are
-@@ -3074,8 +3131,10 @@
+@@ -3076,8 +3133,10 @@
          box_max = []
          if self.n_vertices==0:
              raise ValueError('Empty polytope is not allowed')
              max_coord = max(coords)
              min_coord = min(coords)
              if integral:
-@@ -3085,7 +3144,7 @@
+@@ -3087,7 +3146,7 @@
                  box_max.append(max_coord)
                  box_min.append(min_coord)
          return (tuple(box_min), tuple(box_max))
      def integral_points(self, threshold=100000):
          r"""
          Return the integral points in the polyhedron.
-@@ -3099,12 +3158,12 @@
+@@ -3101,12 +3160,12 @@
            algorith as long as the bounding box is smaller than this.
  
          OUTPUT:
              sage: Polyhedron(vertices=[(-1,-1),(1,0),(1,1),(0,1)]).integral_points()
              ((-1, -1), (0, 0), (0, 1), (1, 0), (1, 1))
  
-@@ -3132,7 +3191,7 @@
+@@ -3134,7 +3193,7 @@
  
              sage: v = [(1,0,7,-1), (-2,-2,4,-3), (-1,-1,-1,4), (2,9,0,-5), (-2,-1,5,1)]
              sage: simplex = Polyhedron(v); simplex
              sage: len(simplex.integral_points())
              49
  
-@@ -3181,7 +3240,8 @@
+@@ -3183,7 +3242,8 @@
              points.update(new_points)
          # assert all(self.contains(p) for p in points)   # slow
          return tuple(points)
      def combinatorial_automorphism_group(self):
          """
          Computes the combinatorial automorphism group of the vertex
-@@ -3200,9 +3260,9 @@
+@@ -3202,9 +3262,9 @@
          chosen to be shifted by ``+1``. That is, ``i`` in the
          permutation group corresponds to the V-representation object
          ``self.Vrepresentation(i-1)``.
              sage: quadrangle = Polyhedron(vertices=[(0,0),(1,0),(0,1),(2,3)])
              sage: quadrangle.combinatorial_automorphism_group()
              Permutation Group with generators [(2,3), (1,2)(3,4)]
-@@ -3216,11 +3276,7 @@
+@@ -3218,11 +3278,7 @@
              sage: P.combinatorial_automorphism_group()
              Permutation Group with generators [(3,4)]
          """
          G = Graph()
          for edge in self.vertex_graph().edges():
              i = edge[0]
-@@ -3238,11 +3294,10 @@
+@@ -3240,11 +3296,10 @@
          self._combinatorial_automorphism_group = group
          return group
  
          INPUT:
  
          - ``v`` -- a V-representation object or any iterable
-@@ -3256,9 +3311,9 @@
+@@ -3258,9 +3313,9 @@
          A ``self.dim()``-dimensional coordinate vector. It contains
          the coordinates of ``v`` in an arbitrary but fixed basis for
          the affine span of the polyhedron.
              sage: P = Polyhedron(rays=[(1,0,0),(0,1,0)])
              sage: P._affine_coordinates( (-1,-2,-3) )
              (-1, -2)
-@@ -3272,14 +3327,14 @@
+@@ -3274,14 +3329,14 @@
                  v_list = [ v - origin for v in v_list ]
              coordinates = matrix(v_list)
              self._affine_coordinates_pivots = coordinates.pivots()
      def restricted_automorphism_group(self):
          r"""
          Return the restricted automorphism group.
-@@ -3297,14 +3352,14 @@
+@@ -3299,14 +3354,14 @@
          generators with line generators.
  
          For example, take the first quadrant
          .. MATH::
  
              \mathrm{Aut}(Q) =
-@@ -3348,7 +3403,7 @@
+@@ -3350,7 +3405,7 @@
          A :class:`PermutationGroup<sage.groups.perm_gps.permgroup.PermutationGroup_generic>`
          that is isomorphic to the restricted automorphism group is
          returned.
          Note that in Sage, permutation groups always act on positive
          integers while ``self.Vrepresentation()`` is indexed by
          nonnegative integers. The indexing of the permutation group is
-@@ -3416,7 +3471,7 @@
+@@ -3418,7 +3473,7 @@
  
          Floating-point computations are supported with a simple fuzzy
          zero implementation::
              sage: P = Polyhedron(vertices=[(1.0/3.0,0,0),(0,1.0/3.0,0),(0,0,1.0/3.0)], base_ring=RDF)
              sage: P.restricted_automorphism_group()
              Permutation Group with generators [(2,3), (1,2)]
-@@ -3427,16 +3482,13 @@
+@@ -3429,16 +3484,13 @@
              sage: p.restricted_automorphism_group()
              Permutation Group with generators [(2,3)]
          """
              c_list = []
              def rational_approximation(c):
                  # Implementation detail: Return unique integer if two
-@@ -3448,7 +3500,7 @@
+@@ -3450,7 +3502,7 @@
                          return i
                  c_list.append(c)
                  return len(c_list)-1
          # The algorithm identifies the restricted automorphism group
          # with the automorphism group of a edge-colored graph. The
          # nodes of the graph are the V-representation objects. If all
-@@ -3505,266 +3557,3 @@
+@@ -3507,266 +3559,3 @@
  
  
  

File trac_12091_constraints_parents.patch

+# HG changeset patch
+# Parent 9ec5f8100986ada544f324fb383d0a3024168e12
+
+Implement parents for constraints, fix chained inequalities
+
+diff --git a/doc/en/reference/numerical.rst b/doc/en/reference/numerical.rst
+--- a/doc/en/reference/numerical.rst
++++ b/doc/en/reference/numerical.rst
+@@ -6,6 +6,7 @@
+ 
+    sage/numerical/knapsack
+    sage/numerical/mip
++   sage/numerical/linear_functions
+    sage/numerical/optimize
+ 
+ LP Solver backends
+diff --git a/module_list.py b/module_list.py
+--- a/module_list.py
++++ b/module_list.py
+@@ -1254,6 +1254,11 @@
+               include_dirs=[SAGE_INC],
+               libraries=["csage","stdc++"]),
+ 
++    Extension("sage.numerical.linear_functions",
++              ["sage/numerical/linear_functions.pyx"],
++              include_dirs=[SAGE_INC],
++              libraries=["csage","stdc++"]),
++
+     Extension("sage.numerical.backends.generic_backend",
+               ["sage/numerical/backends/generic_backend.pyx"],
+               include_dirs = [SAGE_INC, "sage/c_lib/include/"],
+diff --git a/sage/numerical/linear_functions.pxd b/sage/numerical/linear_functions.pxd
+new file mode 100644
+--- /dev/null
++++ b/sage/numerical/linear_functions.pxd
+@@ -0,0 +1,38 @@
++from sage.structure.parent cimport Parent
++from sage.structure.element cimport ModuleElement, RingElement, Element
++
++
++cdef class LinearFunctionsParent_class(Parent):
++    cpdef _element_constructor_(self, x)
++    cpdef _coerce_map_from_(self, R)
++    cdef object _multiplication_symbol
++    cpdef object _get_multiplication_symbol(self)
++
++cdef class LinearFunction(ModuleElement):
++    cdef dict _f
++    cpdef iteritems(self)
++    cpdef ModuleElement _add_(self, ModuleElement b)
++    cpdef ModuleElement _sub_(self, ModuleElement b)
++    cpdef ModuleElement _lmul_(self, RingElement b)
++    cpdef ModuleElement _rmul_(self, RingElement b)
++    cpdef ModuleElement _neg_(self)
++    cpdef _acted_upon_(self, x, bint self_on_left)
++    cdef _richcmp(left, right, int op)
++    cpdef is_zero(self)
++    cpdef equals(LinearFunction left, LinearFunction right)
++
++cdef class LinearConstraintsParent_class(Parent):
++    cdef LinearFunctionsParent_class _LF
++    cpdef _element_constructor_(self, left, right=?, equality=?)
++    cpdef _coerce_map_from_(self, R)
++
++cdef class LinearConstraint(Element):
++    cdef bint equality
++    cdef list constraints
++    cdef _richcmp(left, right, int op)
++    cdef LinearConstraint _chained_comparator_hack_part1(LinearConstraint left, LinearConstraint right)
++    cdef _chained_comparator_hack_part2(self)
++    cpdef equals(LinearConstraint left, LinearConstraint right)
++
++cdef LinearConstraint _chained_comparator_hack_search
++cdef LinearConstraint _chained_comparator_hack_replace
+diff --git a/sage/numerical/linear_functions.pyx b/sage/numerical/linear_functions.pyx
+new file mode 100644
+--- /dev/null
++++ b/sage/numerical/linear_functions.pyx
+@@ -0,0 +1,1393 @@
++"""
++Linear Functions and Constraints
++
++This module implements linear functions (see :class:`LinearFunction`)
++in formal variables and chained (in)equalities between them (see
++:class:`LinearConstraint`). By convention, these are always written as
++either equalities or less-or-equal. For example::
++
++    sage: p = MixedIntegerLinearProgram()
++    sage: x = p.new_variable()
++    sage: f = 1 + x[1] + 2*x[2];  f     #  a linear function
++    1 + x_0 + 2*x_1
++    sage: type(f)
++    <type 'sage.numerical.linear_functions.LinearFunction'>
++    
++    sage: c = (0 <= f);  c    # a constraint
++    0 <= 1 + x_0 + 2*x_1
++    sage: type(c)
++    <type 'sage.numerical.linear_functions.LinearConstraint'>
++    
++Note that you can use this module without any reference to linear
++programming, it only implements linear functions over a base ring and
++constraints. However, for ease of demonstration we will always
++construct them out of linear programs (see
++:mod:`~sage.numerical.mip`).
++
++Constraints can be equations or (non-strict) inequalities. They can be
++chained::
++
++    sage: p = MixedIntegerLinearProgram()
++    sage: x = p.new_variable()
++    sage: x[0] == x[1] == x[2] == x[3]
++    x_0 == x_1 == x_2 == x_3
++
++    sage: ieq_01234 = x[0] <= x[1] <= x[2] <= x[3] <= x[4]
++    sage: ieq_01234
++    x_0 <= x_1 <= x_2 <= x_3 <= x_4
++
++If necessary, the direction of inequality is flipped to always write
++inqualities as less or equal::
++
++    sage: x[5] >= ieq_01234
++    x_0 <= x_1 <= x_2 <= x_3 <= x_4 <= x_5
++
++    sage: (x[5]<=x[6]) >= ieq_01234
++    x_0 <= x_1 <= x_2 <= x_3 <= x_4 <= x_5 <= x_6
++    sage: (x[5]<=x[6]) <= ieq_01234
++    x_5 <= x_6 <= x_0 <= x_1 <= x_2 <= x_3 <= x_4
++
++TESTS:
++
++See :trac:`12091` ::
++
++    sage: p = MixedIntegerLinearProgram()
++    sage: b = p.new_variable()
++    sage: b[0] <= b[1] <= 2
++    x_0 <= x_1 <= 2
++    sage: list(b[0] <= b[1] <= 2)
++    [x_0, x_1, 2]
++    sage: 1 >= b[1] >= 2*b[0]
++    2*x_0 <= x_1 <= 1
++    sage: b[2] >= b[1] >= 2*b[0]
++    2*x_0 <= x_1 <= x_2
++"""
++
++
++#*****************************************************************************
++#       Copyright (C) 2012 Nathann Cohen <nathann.cohen@gmail.com>
++#       Copyright (C) 2012 Volker Braun <vbraun.name@gmail.com>
++#
++#  Distributed under the terms of the GNU General Public License (GPL)
++#  as published by the Free Software Foundation; either version 2 of
++#  the License, or (at your option) any later version.
++#                  http://www.gnu.org/licenses/
++#*****************************************************************************
++
++include "../ext/stdsage.pxi"
++include "../ext/interrupt.pxi"
++include "../ext/cdefs.pxi"
++
++from sage.structure.parent cimport Parent
++from sage.structure.element cimport ModuleElement, Element
++from sage.misc.cachefunc import cached_function
++
++
++
++#*****************************************************************************
++#
++# Utility functions to test that something is a linear function / constraint
++#
++#*****************************************************************************
++
++def is_LinearFunction(x):
++    """
++    Test whether ``x`` is a linear function
++    
++    INPUT:
++
++    - ``x`` -- anything.
++
++    OUTPUT:
++
++    Boolean.
++    
++    EXAMPLES::
++    
++        sage: p = MixedIntegerLinearProgram()
++        sage: x = p.new_variable()
++        sage: from sage.numerical.linear_functions import is_LinearFunction
++        sage: is_LinearFunction(x[0] - 2*x[2])
++        True
++        sage: is_LinearFunction('a string')
++        False
++    """
++    return isinstance(x, LinearFunction)
++
++def is_LinearConstraint(x):
++    """
++    Test whether ``x`` is a linear constraint
++    
++    INPUT:
++
++    - ``x`` -- anything.
++
++    OUTPUT:
++
++    Boolean.
++    
++    EXAMPLES::
++    
++        sage: p = MixedIntegerLinearProgram()
++        sage: x = p.new_variable()
++        sage: ieq = (x[0] <= x[1])
++        sage: from sage.numerical.linear_functions import is_LinearConstraint
++        sage: is_LinearConstraint(ieq)
++        True
++        sage: is_LinearConstraint('a string')
++        False
++    """
++    return isinstance(x, LinearConstraint)
++
++
++#*****************************************************************************
++#
++# Factory functions for the parents to ensure uniqueness
++#
++#*****************************************************************************
++
++@cached_function
++def LinearFunctionsParent(base_ring):
++    """
++    Return the parent for linear functions over ``base_ring``.
++
++    The output is cached, so only a single parent is ever constructed
++    for a given base ring.
++
++    INPUT:
++
++    - ``base_ring`` -- a ring. The coefficient ring for the linear
++      funcitons.
++
++    OUTPUT:
++
++    The parent of the linear functions over ``base_ring``.
++
++    EXAMPLES::
++
++        sage: from sage.numerical.linear_functions import LinearFunctionsParent
++        sage: LinearFunctionsParent(QQ)
++        Linear functions over Rational Field
++    """
++    return LinearFunctionsParent_class(base_ring)
++
++@cached_function
++def LinearConstraintsParent(linear_functions_parent):
++   """
++   Return the parent for linear functions over ``base_ring``.
++
++   The output is cached, so only a single parent is ever constructed
++   for a given base ring.
++
++    INPUT:
++
++    - ``linear_functions_parent`` -- a
++      :class:`LinearFunctionsParent_class`. The type of linear
++      functions that the constraints are made out of.
++
++    OUTPUT:
++
++    The parent of the linear constraints with the given linear functions.
++
++    EXAMPLES::
++
++        sage: from sage.numerical.linear_functions import \
++        ...       LinearFunctionsParent, LinearConstraintsParent
++        sage: LF = LinearFunctionsParent(QQ)
++        sage: LinearConstraintsParent(LF)
++        Linear constraints over Rational Field
++   """
++   return LinearConstraintsParent_class(linear_functions_parent)
++
++
++
++#*****************************************************************************
++#
++# Parent of linear functions
++#
++#*****************************************************************************
++
++cdef class LinearFunctionsParent_class(Parent):
++    r"""
++    The parent for all linear functions over a fixed base ring.
++
++    .. warning::
++    
++        You should use :func:`LinearFunctionsParent` to construct
++        instances of this class.
++
++    INPUT/OUTPUT:
++
++    See :func:`LinearFunctionsParent`
++
++    EXAMPLES::
++
++        sage: from sage.numerical.linear_functions import LinearFunctionsParent_class
++        sage: LinearFunctionsParent_class
++        <type 'sage.numerical.linear_functions.LinearFunctionsParent_class'>
++    """
++
++    def __init__(self, base_ring):
++        """
++        The Python constructor
++        
++        TESTS::
++
++            sage: from sage.numerical.linear_functions import LinearFunctionsParent
++            sage: LinearFunctionsParent(RDF)
++            Linear functions over Real Double Field
++        """
++        from sage.categories.modules_with_basis import ModulesWithBasis
++        Parent.__init__(self, base=base_ring, category=ModulesWithBasis(base_ring))
++        self._multiplication_symbol = '*'
++
++    def set_multiplication_symbol(self, symbol='*'):
++        """
++        Set the multiplication symbol when pretty-printing linear functions.
++
++        INPUT:
++
++        - ``symbol`` -- string, default: ``'*'``. The multiplication
++          symbol to be used.
++
++        EXAMPLES::
++
++            sage: p = MixedIntegerLinearProgram()
++            sage: x = p.new_variable()
++            sage: f = -1-2*x[0]-3*x[1]
++            sage: LF = f.parent()
++            sage: LF._get_multiplication_symbol()
++            '*'
++            sage: f
++            -1 - 2*x_0 - 3*x_1
++            sage: LF.set_multiplication_symbol(' ')
++            sage: f
++            -1 - 2 x_0 - 3 x_1
++            sage: LF.set_multiplication_symbol()
++            sage: f
++            -1 - 2*x_0 - 3*x_1
++        """
++        self._multiplication_symbol = symbol
++
++    cpdef _get_multiplication_symbol(self):
++        """
++        Return the multiplication symbol.
++        
++        OUTPUT:
++        
++        String. By default, this is ``'*'``.
++        
++        EXAMPLES::
++        
++            sage: LF = MixedIntegerLinearProgram().linear_functions_parent()
++            sage: LF._get_multiplication_symbol()
++            '*'
++        """
++        return self._multiplication_symbol
++
++    def _repr_(self):
++        """
++        Return as string representation
++        
++        EXAMPLES::
++        
++            sage: MixedIntegerLinearProgram().linear_functions_parent()
++            Linear functions over Real Double Field
++        """
++        return 'Linear functions over '+str(self.base_ring())
++
++    cpdef _element_constructor_(self, x):
++        """
++        Construt a :class:`LinearFunction` from ``x``.
++
++        EXAMPLES::
++        
++            sage: p = MixedIntegerLinearProgram()
++            sage: LF = p.linear_functions_parent()
++            sage: LF._element_constructor_(123)
++            123
++            sage: p(123)    # indirect doctest
++            123
++            sage: type(_)
++            <type 'sage.numerical.linear_functions.LinearFunction'>
++
++            sage: p_QQ = MixedIntegerLinearProgram(solver='ppl')
++            sage: LF_QQ = p_QQ.linear_functions_parent()
++            sage: f = LF({-1:1/2, 2:3/4});  f
++            0.5 + 0.75*x_2
++            sage: LF(f) is f
++            True
++            sage: LF_QQ(f)
++            1/2 + 3/4*x_2
++            sage: LF_QQ(f) is f
++            False
++        """
++        if is_LinearFunction(x):
++            if x.parent() is self:
++                return x
++            else:
++                return LinearFunction(self, (<LinearFunction>x)._f)
++        return LinearFunction(self, x)
++
++    cpdef _coerce_map_from_(self, R):
++        """
++        Allow coercion of scalars into linear functions.
++        
++        INPUT:
++        
++        - ``R`` -- a ring.
++        
++        OUTPUT:
++
++        Boolean. Whether there is a coercion map.
++
++        EXAMPLES::
++        
++            sage: p = MixedIntegerLinearProgram()
++            sage: parent = p.linear_functions_parent()
++            sage: parent.coerce(int(2))
++            2
++            sage: parent._coerce_map_from_(int)
++            True
++        """
++        if R in [int, float, long, complex]:
++            return True
++        from sage.rings.real_mpfr import mpfr_prec_min
++        from sage.rings.all import RealField
++        if RealField(mpfr_prec_min()).has_coerce_map_from(R):
++            return True
++        return False
++
++    def _an_element_(self):
++        """
++        Returns an element
++
++        OUTPUT:
++
++        A linear function.
++
++        EXAMPLES::
++
++            sage: p = MixedIntegerLinearProgram().linear_functions_parent()
++            sage: p._an_element_()
++            5*x_2 + 7*x_5
++            sage: p.an_element()   # indirect doctest
++            5*x_2 + 7*x_5
++        """
++        return self._element_constructor_({2:5, 5:7})
++
++
++#*****************************************************************************
++#
++# Elements of linear functions
++#
++#*****************************************************************************
++
++cdef class LinearFunction(ModuleElement):
++    r"""
++    An elementary algebra to represent symbolic linear functions.
++
++    .. warning::
++    
++        You should never instantiate :class:`LinearFunction`
++        manually. Use the element constructor in the parent
++        instead. For convenience, you can also call the
++        :class:`MixedIntegerLinearProgram` instance directly.
++
++    EXAMPLES:
++
++    For example, do this::
++
++        sage: p = MixedIntegerLinearProgram()
++        sage: p({0 : 1, 3 : -8})
++        x_0 - 8*x_3
++
++    or this::
++
++        sage: parent = p.linear_functions_parent()
++        sage: parent({0 : 1, 3 : -8})
++        x_0 - 8*x_3
++
++    instead of this::
++            
++        sage: from sage.numerical.linear_functions import LinearFunction
++        sage: LinearFunction(p.linear_functions_parent(), {0 : 1, 3 : -8})
++        x_0 - 8*x_3
++    """
++
++    def __init__(self, parent, f):
++        r"""
++        Constructor taking a dictionary or a numerical value as its argument.
++
++        A linear function is represented as a dictionary. The
++        values are the coefficient of the variable represented
++        by the keys ( which are integers ). The key ``-1``
++        corresponds to the constant term.
++
++        EXAMPLES:
++
++        With a dictionary::
++
++            sage: p = MixedIntegerLinearProgram()
++            sage: p({0 : 1, 3 : -8})
++            x_0 - 8*x_3
++
++        Using the constructor with a numerical value::
++
++            sage: p = MixedIntegerLinearProgram()
++            sage: p(25)
++            25
++        """
++        ModuleElement.__init__(self, parent)
++        R = self.base_ring()
++        if isinstance(f, dict):
++            self._f = dict( (int(key), R(value)) for key, value in f.iteritems() )
++        else:
++            self._f = {-1: R(f)}
++
++    cpdef iteritems(self):
++        """
++        Iterate over the index, coefficient pairs
++
++        OUTPUT:
++
++        An iterator over the ``(key, coefficient)`` pairs. The keys
++        are integers indexing the variables. The key ``-1``
++        corresponds to the constant term.
++        
++        EXAMPLES::
++        
++            sage: p = MixedIntegerLinearProgram(solver = 'ppl')
++            sage: x = p.new_variable()
++            sage: f = 0.5 + 3/2*x[1] + 0.6*x[3]
++            sage: for id, coeff in f.iteritems():
++            ...      print 'id =', id, '  coeff =', coeff
++            id = 0   coeff = 3/2
++            id = 1   coeff = 3/5
++            id = -1   coeff = 1/2
++        """
++        return self._f.iteritems()
++
++    def dict(self):
++        r"""
++        Returns the dictionary corresponding to the Linear Function.
++
++        OUTPUT:
++
++        The linear function is represented as a dictionary. The value
++        are the coefficient of the variable represented by the keys (
++        which are integers ). The key ``-1`` corresponds to the
++        constant term.
++
++        EXAMPLE::
++
++            sage: p = MixedIntegerLinearProgram()
++            sage: lf = p({0 : 1, 3 : -8})
++            sage: lf.dict()
++            {0: 1.0, 3: -8.0}
++        """
++        return dict(self._f)
++
++    cpdef ModuleElement _add_(self, ModuleElement b):
++        r"""
++        Defining the + operator
++
++        EXAMPLE::
++
++            sage: p = MixedIntegerLinearProgram()
++            sage: p({0 : 1, 3 : -8}) + p({2 : 5, 3 : 2}) - 16
++            -16 + x_0 + 5*x_2 - 6*x_3
++        """
++        e = dict(self._f)
++        for (id,coeff) in b.dict().iteritems():
++            e[id] = self._f.get(id,0) + coeff
++        P = self.parent()
++        return P(e)
++
++    cpdef ModuleElement _neg_(self):
++        r"""
++        Defining the - operator (opposite).
++
++        EXAMPLE::
++
++            sage: p = MixedIntegerLinearProgram()
++            sage: - p({0 : 1, 3 : -8})
++            -1*x_0 + 8*x_3
++        """
++        P = self.parent()
++        return P(dict([(id,-coeff) for (id, coeff) in self._f.iteritems()]))
++
++    cpdef ModuleElement _sub_(self, ModuleElement b):
++        r"""
++        Defining the - operator (substraction).
++
++        EXAMPLE::
++
++            sage: p = MixedIntegerLinearProgram()
++            sage: p({2 : 5, 3 : 2}) - 3
++            -3 + 5*x_2 + 2*x_3
++            sage: p({0 : 1, 3 : -8}) - p({2 : 5, 3 : 2}) - 16
++            -16 + x_0 - 5*x_2 - 10*x_3
++        """
++        e = dict(self._f)
++        for (id,coeff) in b.dict().iteritems():
++            e[id] = self._f.get(id,0) - coeff
++        P = self.parent()
++        return P(e)
++
++    cpdef ModuleElement _rmul_(self, RingElement b):
++        r"""
++        Left multiplication by scalars
++
++        EXAMPLE::
++
++            sage: p = MixedIntegerLinearProgram()
++            sage: p({2 : 5, 3 : 2}) * 3
++            15*x_2 + 6*x_3
++        """
++        P = self.parent()
++        return P(dict([(id,b*coeff) for (id, coeff) in self._f.iteritems()]))
++
++    cpdef ModuleElement _lmul_(self, RingElement b):
++        r"""
++        Right multiplication by scalars
++
++        EXAMPLE::
++
++            sage: p = MixedIntegerLinearProgram()
++            sage: 3 * p({2 : 5, 3 : 2})
++            15*x_2 + 6*x_3
++        """
++        return self._rmul_(b)
++
++    cpdef _acted_upon_(self, x, bint self_on_left):
++       """
++       Act with scalars that do not have a natural coercion into
++       ``self.base_ring()``
++
++       EXAMPLES:
++
++       Note that there is no coercion from ``RR`` to ``QQ``, but you
++       can explicitly convert them::
++
++           sage: 1/2 * 0.6
++           0.300000000000000
++
++       If there were a coercion, then 0.6 would have been coerced into
++       6/10 and the result would have been rational. This is
++       undesirable, which is why there cannot be a coercion on the
++       level of the coefficient rings.
++
++       By declaring an action of ``RR`` on the linear functions over
++       ``QQ`` we make the following possible::
++
++           sage: p = MixedIntegerLinearProgram(solver='ppl')
++           sage: p.base_ring()
++           Rational Field
++           sage: x = p.new_variable()
++           sage: x[0] * 0.6
++           3/5*x_0
++       """
++       R = self.base_ring()
++       try:
++           x_R = R(x)
++       except TypeError:
++           return None
++       return self._rmul_(x_R)
++
++    def _coeff_formatter(self, coeff, constant_term=False):
++        """
++        Pretty-print multiplicative coefficient ``x`` 
++        
++        OUTPUT:
++
++        String, including a trailing space if the coefficient is not
++        one. Empty string otherwise.
++
++        EXAMPLES::
++
++            sage: p = MixedIntegerLinearProgram()
++            sage: f = p(1);  type(f)
++            <type 'sage.numerical.linear_functions.LinearFunction'>
++            sage: f._coeff_formatter(1)
++            ''
++            sage: f._coeff_formatter(1, constant_term=True)
++            '1'
++            sage: f._coeff_formatter(RDF(12.0))
++            '12*'
++            sage: f._coeff_formatter(RDF(12.3))
++            '12.3*'
++
++            sage: q = MixedIntegerLinearProgram(solver='ppl')
++            sage: f = p(1)
++            sage: f._coeff_formatter(13/45)
++            '13/45*'
++        """
++        R = self.base_ring()
++        if coeff == R.one() and not constant_term:
++            return ''
++        try: 
++            from sage.rings.all import ZZ
++            coeff = ZZ(coeff)    # print as integer if possible
++        except TypeError:
++            pass
++        if constant_term:
++            return str(coeff)
++        else:
++            return str(coeff) + self.parent()._get_multiplication_symbol()
++
++    def _repr_(self):
++        r"""
++        Returns a string version of the linear function.
++
++        EXAMPLE::
++
++            sage: p = MixedIntegerLinearProgram(solver='GLPK')
++            sage: p({-1: -15, 2 : -5.1, 3 : 2/3})
++            -15 - 5.1*x_2 + 0.666666666667*x_3
++            sage: p = MixedIntegerLinearProgram(solver='ppl')
++            sage: p({-1: -15, 2 : -5.1, 3 : 2/3})
++            -15 - 51/10*x_2 + 2/3*x_3
++        """
++        cdef dict d = dict(self._f)
++        cdef bint first = True
++        t = ""
++
++        if d.has_key(-1):
++            coeff = d.pop(-1)
++            if coeff!=0:
++                t = self._coeff_formatter(coeff, constant_term=True)
++                first = False
++
++        cdef list l = sorted(d.items())
++        for id,coeff in l:
++            sign = cmp(coeff,0)
++            if sign == 0:
++                continue
++            if not first:
++                if sign == -1:
++                    t += ' - '
++                if sign == +1:
++                    t += ' + '
++                t += self._coeff_formatter(abs(coeff)) + 'x_' + str(id)
++            else:
++                t += self._coeff_formatter(coeff) + 'x_' + str(id)
++            first = False
++        
++        if first:
++            return '0'
++        else:
++            return t
++
++    cpdef is_zero(self):
++        """
++        Test whether ``self`` is zero.
++
++        OUTPUT:
++        
++        Boolean.
++
++        EXAMPLES::
++
++            sage: p = MixedIntegerLinearProgram()
++            sage: x = p.new_variable()
++            sage: (x[1] - x[1] + 0*x[2]).is_zero()
++            True
++        """
++        for coeff in self._f.values():
++            if not coeff.is_zero():
++                return False
++        return True
++
++    cpdef equals(LinearFunction left, LinearFunction right):
++        """
++        Logically compare ``left`` and ``right``.
++
++        OUTPUT:
++
++        Boolean.
++
++        EXAMPLES::
++
++            sage: p = MixedIntegerLinearProgram()
++            sage: x = p.new_variable()
++            sage: (x[1] + 1).equals(3/3 + 1*x[1] + 0*x[2])
++            True
++        """
++        return (left-right).is_zero()
++
++    def __richcmp__(left, right, int op):
++        """
++        Override the rich comparison.
++        
++        The Sage framework sometimes expects that rich comparison
++        results in a boolean value, but we want to return
++        :class:`~sage.numerical.linear_functions.LinearConstraint`
++        objects.
++
++        EXAMPLES::
++
++            sage: p = MixedIntegerLinearProgram()
++            sage: x = p.new_variable()
++            sage: x[0].__le__(x[1])    # indirect doctest
++            x_0 <= x_1
++        """
++        return (<LinearFunction>left)._richcmp(right, op)
++
++    cdef _richcmp(left, right, int op):
++        """
++        Create a inequality or equality object.
++
++        EXAMPLE::
++
++            sage: p = MixedIntegerLinearProgram()
++            sage: from sage.numerical.linear_functions import LinearFunction
++            sage: p({2 : 5, 3 : 2}) <= p({2 : 3, 9 : 2})
++            5*x_2 + 2*x_3 <= 3*x_2 + 2*x_9
++
++            sage: p({2 : 5, 3 : 2}) >= p({2 : 3, 9 : 2})
++            3*x_2 + 2*x_9 <= 5*x_2 + 2*x_3
++
++            sage: p({2 : 5, 3 : 2}) == p({2 : 3, 9 : 2})
++            5*x_2 + 2*x_3 == 3*x_2 + 2*x_9
++
++            sage: p({2 : 5, 3 : 2}) < p({2 : 3, 9 : 2})
++            Traceback (most recent call last):
++            ...
++            ValueError: strict < is not allowed, use <= instead.
++
++            sage: p({2 : 5, 3 : 2}) > p({2 : 3, 9 : 2})
++            Traceback (most recent call last):
++            ...
++            ValueError: strict > is not allowed, use >= instead.
++
++        TESTS::
++
++            sage: cm = sage.structure.element.get_coercion_model()
++            sage: cm.explain(10, p(1), operator.le)
++            Coercion on left operand via
++                Conversion map:
++                  From: Integer Ring
++                  To:   Linear functions over Real Double Field
++            Arithmetic performed after coercions.
++            Result lives in Linear functions over Real Double Field
++            Linear functions over Real Double Field
++
++            sage: x = p.new_variable()
++            sage: operator.le(10, x[0])
++            10 <= x_0
++            sage: x[0] <= 1
++            x_0 <= 1
++            sage: x[0] >= 1
++            1 <= x_0
++            sage: 1 <= x[0]
++            1 <= x_0
++            sage: 1 >= x[0]
++            x_0 <= 1
++       """
++        LF = left.parent()
++        LC = LinearConstraintsParent(LF)
++        equality = (op == Py_EQ)
++        cdef LinearConstraint  left_constraint = LC(left,  equality=equality)
++        cdef LinearConstraint right_constraint = LC(right, equality=equality)
++        if op == Py_LT:
++            raise ValueError("strict < is not allowed, use <= instead.")
++        elif op == Py_EQ:
++            return left_constraint._richcmp(right_constraint, op)
++        elif op == Py_GT:
++            raise ValueError("strict > is not allowed, use >= instead.")
++        elif op == Py_LE:
++            return left_constraint._richcmp(right_constraint, op)
++        elif op == Py_NE:
++            raise ValueError("inequality != is not allowed, use one of <=, ==, >=.")
++        elif op == Py_GE:
++            return left_constraint._richcmp(right_constraint, op)
++        else:
++            assert(False)   # unreachable
++
++    def __hash__(self):
++        r"""
++        Defines a ``__hash__`` function
++
++        EXAMPLE::
++
++            sage: p = MixedIntegerLinearProgram()
++            sage: f = p({2 : 5, 3 : 2})
++            sage: f.__hash__()   # random output
++            103987752
++            sage: d = {}
++            sage: d[f] = 3
++        """
++        return id(self)
++
++
++#*****************************************************************************
++#
++# Parent of linear constraints
++#
++#*****************************************************************************
++
++cdef class LinearConstraintsParent_class(Parent):
++    """
++    Parent for :class:`LinearConstraint`
++