Opened 9 years ago

Closed 9 years ago

Last modified 9 years ago

#13650 closed enhancement (fixed)

Base rings for MIP backends

Reported by: vbraun Owned by: ncohen
Priority: major Milestone: sage-5.5
Component: linear programming Keywords:
Cc: dimpase, ncohen Merged in: sage-5.5.rc0
Authors: Volker Braun, Dmitrii Pasechnik Reviewers: Dmitrii Pasechnik, Volker Braun
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: #13646, #12533 Stopgaps:

Status badges

Description (last modified by vbraun)

The MIP backends just need a method base_ring(), say, that returns the base ring that the backend wants.

Apply

Attachments (2)

trac_13650_base_ring.patch (2.3 KB) - added by dimpase 9 years ago.
the initial patch
trac_13650_normalize_coefficients.patch (13.0 KB) - added by vbraun 9 years ago.
Updated patch

Download all attachments as: .zip

Change History (14)

comment:1 Changed 9 years ago by vbraun

  • Cc dimpase ncohen added
  • Dependencies set to #13646, #12533
  • Description modified (diff)

comment:2 Changed 9 years ago by dimpase

OK, this is easy, I hope. I'll work on this tonight. As far as I understand, the base ring is RDF for all the backends, expect PPL.

Actually, is it even needed to provide base_ring() in the backends that have RDF as the base ring? Can't PPL backend just overwrite it? I gather Python has such an option:

    class A(object):
        ...
       def a(self):
           ....
    class  B(A):
       ...
       def _A__a(self):
           ...
     

so B overwrites A.a() this way. Or is this wrong/not applicable?

Last edited 9 years ago by dimpase (previous) (diff)

comment:3 follow-up: Changed 9 years ago by vbraun

Yes, it would be desirable to define base_ring() in GenericBackend to be RDF and only override it as needed in derived classes.

Changed 9 years ago by dimpase

the initial patch

comment:4 in reply to: ↑ 3 Changed 9 years ago by dimpase

Replying to vbraun:

Yes, it would be desirable to define base_ring() in GenericBackend to be RDF and only override it as needed in derived classes.

patch uploaded. Trivial, it seems...

comment:5 Changed 9 years ago by vbraun

Just for the record, rings in Sage have already a .zero() method. R(0) is fine too.

comment:6 follow-up: Changed 9 years ago by vbraun

I'll hook this into the LinearFunctionsParent?, patch coming...

Does anybody mind if we typeset the linear functions more like polynomials? That is,

sage: R.<x_0,x_1> = QQ[]
sage: 1+2*x_0+3*x_1
2*x_0 + 3*x_1 + 1

instead of

sage: p = MixedIntegerLinearProgram()
sage: x = p.new_variable()
sage: 1+2*x[0]+3*x[1]
1 +2 x_0 +3 x_1

I think spaces around +/- and explicit * are more readable, and would make the output more uniform.

comment:7 in reply to: ↑ 6 Changed 9 years ago by dimpase

Replying to vbraun:

Does anybody mind if we typeset the linear functions more like polynomials? That is,

This is not what the classic file formats for inputting LPs do, see e.g.

http://www.gurobi.com/documentation/5.0/reference-manual/node746

Designed for punchcards, I reckon :-)

Myself, I'd prefer it polynomial way though. I think, ideally, this should be customizable.

comment:8 Changed 9 years ago by vbraun

  • Authors set to Volker Braun, Dima Pasechnik
  • Description modified (diff)
  • Reviewers set to Dima Pasechnik, Volker Braun
  • Status changed from new to needs_review

The patch now enforces that the coefficients are in the base ring. Also, pretty printing is fixed. There is also a way to change the default for the multiplication symbol if you want to.

I noticed that the mip.show() code doesn't use the pretty printing of linear functions but rolls its own, so its output is unchanged for now.

Changed 9 years ago by vbraun

Updated patch

comment:9 Changed 9 years ago by vbraun

Example of normalizing the coefficients:

    sage: p = MixedIntegerLinearProgram(maximization=False, solver = 'GLPK')
    sage: p.base_ring()
    Real Double Field
    sage: x = p.new_variable()
    sage: 0.5 + 3/2*x[1]
    0.5 + 1.5*x_0

    sage: p = MixedIntegerLinearProgram(maximization=False, solver = 'ppl')
    sage: p.base_ring()
    Rational Field
    sage: x = p.new_variable()
    sage: 0.5 + 3/2*x[1]
    1/2 + 3/2*x_0

comment:10 Changed 9 years ago by dimpase

  • Status changed from needs_review to positive_review

comment:11 Changed 9 years ago by jdemeyer

  • Merged in set to sage-5.5.rc0
  • Resolution set to fixed
  • Status changed from positive_review to closed

comment:12 Changed 9 years ago by jdemeyer

  • Authors changed from Volker Braun, Dima Pasechnik to Volker Braun, Dmitrii Pasechnik
  • Reviewers changed from Dima Pasechnik, Volker Braun to Dmitrii Pasechnik, Volker Braun
Note: See TracTickets for help on using tickets.