ILP with GLPK

[Francisco]

I have a big problem simplified as:
max f
s.t:
Ax<=b
x is binary

is there a way to get it into the commands easily, I'm not making my
point clear, to adjust it to your program following the examples i got
to this:

prob = LpProblem("Perrera", LpMaximize)
x = LpVariable.dicts("perros",binVars,0,1,LpInteger)
prob += lpSum([x[w]*f[w] for w in binVars]), "sum of genetical
beneficense"
for w in range(3*80):
prob+= lpSum(x[w]*A[w][d] for d in binVars) <= b[w]
prob.writeLP("ComputerPlantProblem.lp")
prob.solve(GLPK(msg = 0))
print "Status:", LpStatus[prob.status]
#for v in prob.variables():
# print v.name, "=", v.varValue
print "Total Costs = ", value(prob.objective)


First of all I think the way I'm doing it, it's not even near to
optimal, it takes like 2 minutes just to write the LP problem, and
just 2 seconds to solve it, and it gives me a different answer that I
got from another LP solver.

Second how do i get the sensitivity analysis?

For your time thanks!!
Regards, Francisco

[Stuart Mitchell]

Hmm sounds like it is taking too long to set up. Can you please send me the complete file so i can have a look (directly if you don't want to post it to the group).

There is no sensitivity analysis for interger programing problems. Also, you may have many solutions with the same optimal objective function, so just compare the objective rather than the solution values when comparing different solvers.

Stu

--
You received this message because you are subscribed to the Google Groups "pulp-or-discuss" group.
To post to this group, send email to pulp-or...@googlegroups.com.
To unsubscribe from this group, send email to pulp-or-discu...@googlegroups.com.
For more options, visit this group at http://groups.google.com/group/pulp-or-discuss?hl=en.

[Francisco]

Hi Stu.
I sent the code and data to your mail, thanks for your time!

Regards Francisco.

On 26 abr, 06:42, Stuart Mitchell <s...@stuartmitchell.com> wrote:
> Hmm sounds like it is taking too long to set up. Can you please send me the
> complete file so i can have a look (directly if you don't want to post it
> to the group).
>
> There is no sensitivity analysis for interger programing problems. Also,
> you may have many solutions with the same optimal objective function, so
> just compare the objective rather than the solution values when comparing
> different solvers.
>
> Stu

[Stuart Mitchell]

For a large speedup replace the following with

> > for w in range(3*80):
> >    prob+= lpSum(x[w]*A[w][d] for d in binVars) <= b[w]

for w in range(3*80):

    # use the faster way to generate constraints

    prob+= LpAffineExpression([(x[w], A[w][d]) for d in binVars]) <= b[w]

About the differences between your code and another I can't comment unless I have more information about the type of problem, or the other formulation

Stu

--

Stuart Mitchell

PhD Engineering Science

Extraordinary Freelance Programmer and Optimisation Guru

www.stuartmitchell.com

[Francisco]

just for the record, cos I already got what i was searching for, the
code of the other is basically the same, and I use the same solver but
with an API (OpenOpt, CVXOPT-GLPK)
something like:

# -*- coding: utf-8 -*-
"""
Created on Mon Apr 23 18:43:57 2012

@author: Noone
"""

import xlrd
from openopt import *
from numpy import *
from lpsolve55 import *
from scipy import *
#from cvxopt import *
wb = xlrd.open_workbook('datos.xls')
wb.sheet_names()

sh=wb.sheet_by_index(0)
m=[]
h=[]
p=[]
def chunks(l, inicio,largo):
return l[inicio:inicio+largo]

for rownum in range(80):#grupo 1
temp=sh.row_values(rownum+7)
m=m+chunks(temp, 8, 80)
#print m
h=h+chunks(temp, 92, 80)

for rownum in range(673, 673+80):#maximo de hembras por perro
temp=sh.row_values(rownum)
p.append(temp[8])

lb = zeros(80**2*2)
ub = ones(80**2*2)

# making my matrix according to restrictions
def matriz(n):
O=[ [0]*n**2*2 for y in range(n*3) ]
for x in range(n*2):
for z in range(x*n,((x+1)*n)):
O[x].insert(z,1)
O[x].pop(z+1)
for x in range (n):
for z in range(n):
O[n*2+x].insert((z)*n+x,1)
O[n*2+x].pop((z)*n+x+1)
return O
I=matriz(80)
pp=[1]*160

#objective function, just the beneficence from each point
f = m+h

#Matrix subject to restrictions
A=I

#Restriction values
b=p+pp

#Range of Vars
intVars=range(80**2*2)

#Actualizing the MILP:
p = MILP(f, A=A, b=b, lb=lb, ub=ub, goal='max')

#success = p.exportToMPS('milp_1')

r=p.solve('glpk', iprint =-1, )

print 'objFunValue:', r.ff
print 'x_opt:', r.xf

OUTPUT:

objFunValue: 12898.0

with PULP i got that each variable is getting result 1, so it's
logical that it isn't getting the restrictions, by the way, it was a
nice trick the LpAffineExpression, it made me save a lot of time.

whatsoever the PULP OUTPUT was:

Total Costs = 77022.0

for v in prob.variables():

print v.name, "=", v.varValue

OUTPUT:

perros_9986 = 1
perros_9987 = 1
perros_9988 = 1
perros_9989 = 1
perros_999 = 1
perros_9990 = 1
perros_9991 = 1
perros_9992 = 1
perros_9993 = 1 ...... and for ever and ever 1.


See you around!! and thanks for your time once again!

Regards, Francisco

[Stuart Mitchell]

I think I found your mistake

for w in range(3*80):

    # use the faster way to generate constraints

    prob+= LpAffineExpression([(x[w], A[w][d]) for d in binVars]) <= b[w]

should be

for w in range(3*80):

    # use the faster way to generate constraints

    prob+= LpAffineExpression([(x[d], A[w][d]) for d in binVars]) <= b[w]

This then gives the correct answer, btw in pulp I would formulate this in a much more readable manner as you don't need to construct the A matrix in this manner.

INTEGER OPTIMAL SOLUTION FOUND

Time used:   0.1 secs

Memory used: 7.8 Mb (8212464 bytes)

Writing MIP solution to `/tmp/4014-pulp.sol'...

Status: Optimal

Total Costs =  12898.0

[Francisco Huerta]

WOW, it was so obvious! i should have thought about that, and for that I'm sorry, by the way i thought that constructing the A that way was going to be simpler to insert it to any solver, of course no one, but me would be able to understand it.

I'm starting to think that maybe PULP it's more like for educational purposes, and not for big problems, but maybe just because I'm still a noob!!

I'm very thankful!!
I could get the sensitivity report, because the matrix was uni-modular so the variable solutions where always integers.

2012/4/27 Stuart Mitchell <s...@stuartmitchell.com>