Opened 10 years ago

Closed 10 years ago

Last modified 10 years ago

#13650 closed enhancement (fixed)

Base rings for MIP backends

Reported by: Volker Braun Owned by: Nathann Cohen
Priority: major Milestone: sage-5.5
Component: linear programming Keywords:
Cc: Dima Pasechnik, Nathann Cohen 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 Volker Braun)

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 Dima Pasechnik 10 years ago.
the initial patch
trac_13650_normalize_coefficients.patch (13.0 KB) - added by Volker Braun 10 years ago.
Updated patch

Download all attachments as: .zip

Change History (14)

comment:1 Changed 10 years ago by Volker Braun

Cc: Dima Pasechnik Nathann Cohen added
Dependencies: #13646, #12533
Description: modified (diff)

comment:2 Changed 10 years ago by Dima Pasechnik

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 10 years ago by Dima Pasechnik (previous) (diff)

comment:3 Changed 10 years ago by Volker Braun

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

Changed 10 years ago by Dima Pasechnik

Attachment: trac_13650_base_ring.patch added

the initial patch

comment:4 in reply to:  3 Changed 10 years ago by Dima Pasechnik

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 10 years ago by Volker Braun

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

comment:6 Changed 10 years ago by Volker Braun

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 10 years ago by Dima Pasechnik

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 10 years ago by Volker Braun

Authors: Volker Braun, Dima Pasechnik
Description: modified (diff)
Reviewers: Dima Pasechnik, Volker Braun
Status: newneeds_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 10 years ago by Volker Braun

Updated patch

comment:9 Changed 10 years ago by Volker Braun

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 10 years ago by Dima Pasechnik

Status: needs_reviewpositive_review

comment:11 Changed 10 years ago by Jeroen Demeyer

Merged in: sage-5.5.rc0
Resolution: fixed
Status: positive_reviewclosed

comment:12 Changed 10 years ago by Jeroen Demeyer

Authors: Volker Braun, Dima PasechnikVolker Braun, Dmitrii Pasechnik
Reviewers: Dima Pasechnik, Volker BraunDmitrii Pasechnik, Volker Braun
Note: See TracTickets for help on using tickets.