Sunday, August 30, 2009

Fair division using a spreadsheet and Ruby

It has taken me a month to get over the idea that someone expected this blog not to be the ranting of an inane balding drunk but actually good. Still it is time to get back to the drunken inane rambling.

There is no point having all these cool algorithms unless people can actually use them. So what is a good way to actually get the data into the program? We'll spreadsheets are used for this sort of thing all the time. Unfortunately I cannot figure out how to get openoffice, excel or gnumeric's solver to carry out this minimax fair division program.

Ruby has a cool library called roo for interacting with spreadsheets. So heres a program to get the data out of a spreadsheet and send it off to GLPK

require 'rubygems'
require 'roo'

#open office version
# oo = Openoffice.new("spreadsheetOO.ods")
# o2 = Openoffice.new("spreadsheetOO.ods")

#excell version
oo = Excel.new("spreadsheetOO.xls")
o2 = Excel.new("spreadsheetOO.xls")
oo.default_sheet = oo.sheets.first

o2.default_sheet ="Sheet2"
st="" #data being written toa file
div= o2.last_column


#start writing data to model file
st<< "data;\n"
st<< "param m := #{oo.last_row-1};\n"

st<< "param n := #{div};\n"
#the non divisible is whatever is left
st<< "param o := #{oo.last_column};\n"

st<< "param c :"
i=1
(oo.last_column).times{st<< "#{i} "
i=i+1}
st<< ":=\n"

# number of people
i=1

2.upto(oo.last_row) do |line|
st<< "#{i} "
1.upto(oo.last_column) do |col|
st<< "#{Integer oo.cell(line,col)} "#Integer

end
st<< "\n";
i=i+1
end
st<< ";\n"
st<< "param d :"
i=1
(o2.last_column).times{st<< "#{i} "
i=i+1}
i=1
st<< ":=\n"
2.upto(o2.last_row) do |line|
st<< "#{i} "
1.upto(o2.last_column) do |col|
st<<"#{Integer o2.cell(line,col)} "
end
st<< "\n";
i=i+1
end


st<< ";\nend;"

#write data to a file
File.open("data","w")do |file|
file.write(st)
end

#call glpk program on the data
system('./glpsol -m fair.mod -d data -o fair.sol');


The input spreadsheets are openoffice and excelin the first row is the list of items.
Every other row is each persons valuation for each item. The first sheet is the indivisible items and the second sheet are the divisible ones. Unfortunately roo does not allow you write to these spreadsheets so I cannot print out the answer to a spreadsheet.

The roo interface to the google docs spreadsheet does allow cells to be written to. So getting that version up and running is the next task.