Question about write_lp

10 views
Skip to first unread message

Jernej

unread,
Jun 7, 2016, 6:56:31 AM6/7/16
to sage-support, sergio. cabello, vid.s...@gmail.com, urska...@student.fmf.uni-lj.si
Hello,

I think there might be a bug in how write_lp handles the objective function. Consider the following simple ILP formulation for signed domination 

===
def signed(G):
    I = MixedIntegerLinearProgram(maximization=false)
    x = I.new_variable(binary=True)
    for u in G:
        I.add_constraint(I.sum(2*x[v]-1 for v in (G[u]+[u])) >=1 )
    I.set_objective(I.sum(2*x[u]-1 for u in G))
    return I
===

The respective formulation for the Petersen graph gives the following objective function,

===
G = graphs.PetersenGraph()
I = signed(G)
I.show()

Minimization:
2.0 x_0 + 2.0 x_1 + 2.0 x_2 + 2.0 x_3 + 2.0 x_4 + 2.0 x_5 + 2.0 x_6 + 2.0 x_7 + 2.0 x_8 + 2.0 x_9 - 10.0
.................
===

which is fine. Now if we write the LP problem to a file the subtracted constant is missed:

===
I.write_lp('foo')
$ cat foo.lp
Minimize
obj: 2 x0 + 2 x1 + 2 x2 + 2 x3 + 2 x4 + 2 x5 + 2 x6 + 2 x7 + 2 x8 + 2 x9
.........
===

Hence by solving this LP in Sage or with a *.lp solver, one obtains different results. Am I missing something or is this a bug in write_lp?

Best,

Jernej





Reply all
Reply to author
Forward
0 new messages