I hope this clears it up. This is a non linear function optimization. What is the best way to solve it?

Regards,
Sudhamsh.

lambda * sum(y) -> min
s.t.
x <= y (vectors)
x >= -y (vectors)
other_required_constraints

you could also ask or-exchange.com

   I am trying to solve a problem of the form:  f(x) - lambda||x||1 (this term is the first norm of x). This in itself is not a linear program since lamba||x|| term makes in non-linear. Can anyone suggest how I could solve this? Ideally I would like to convert this into a linear program and use a LP solver. But, I can't seem to find a way to do that.

  Any help or advise will be greatly appreciated.

Regards,
Sudhamsh.

See a small benchmark results here

So, for vectorized functions CPython currently may work faster, because SSE are not implemented properly in PyPy yet.

According to a PyPy developer proposition I have filed a bugreport , but they will go for it after SSE branch.

These 211 elements of 544 are already present in PyPy (obtained via len(dir(numpy)), however, some of the items are modules):

False_ Inf Infinity NAN NINF NZERO NaN PINF PZERO True_ abs absolute add alen all alltrue amax amin any arange arccos arccosh arcsin arcsinh arctan arctan2 arctanh argmax argmin argsort around array array2string array_equal array_repr array_str arrayprint asanyarray asarray average base_repr bitwise_and bitwise_not bitwise_or bitwise_xor bool8 bool_ byte ceil character choose clip compress concatenate copysign core cos cosh count_reduce_items cumprod cumproduct cumsum deg2rad degrees diagonal divide dot dtype e empty equal exp exp2 expm1 fabs flatiter flexible float32 float64 float_ floating floor floor_divide fmax fmin fmod fromnumeric fromstring generic greater greater_equal identity inexact inf infty int16 int32 int64 int8 int_ intc integer intp invert isfinite isinf isna isnan isneginf isposinf left_shift less less_equal little_endian log log10 log1p log2 logaddexp logaddexp2 logical_and logical_not logical_or logical_xor longlong math max maximum mean min minimum multiarray multiply nan ndarray ndim negative newaxis nonzero not_equal number numeric ones pi power prod product ptp put pypy rad2deg radians rank ravel reciprocal repeat reshape resize right_shift round_ searchsorted set_string_function shape short sign signbit signedinteger sin sinh size sometrue sort sqrt square squeeze std str_ subtract sum swapaxes sys take tan tanh trace transpose true_divide trunc typeinfo ubyte ufunc uint16 uint32 uint64 uint8 uintc uintp ulonglong unicode_ unsignedinteger ushort var void where zeros

And for OpenOpt / FuncDesigner mostly these functions are missing in PyPy yet:

array_equal nanargmax hstack diag nanmin atleast_1d asscalar eye zeros_like tile empty_like array_equiv asfarray nanargmin vstack nansum copy diff cross flipud isscalar insert nanmax

From the top-10 7 packages are proprietary, MPS is format (not software), and only 2 are free: GLPK (only linear problems, LP and MILP), and OpenOpt.

And OpenOpt is the only one package from the Top-10 with permissive license (BSD), that allows using it in any software, possibly commercial closed-source one.

See http://top-topics.thefullwiki.org/Mathe … n_software

and local snapshots taken today:

    Topic     Wikipedia  topic views (AFAIK for 2 weeks)
1     Mathematica     1,279    
2     CPLEX     126    
3     MPS (format)     96    
4     AMPL     89    
5     General Algebraic Modeling System     89    
6     GAUSS (software)     67    
7     GNU Linear Programming Kit     66    
8     MapleSim     61    
9     APMonitor     60    
10     OpenOpt     48    
11     ASCEND     43    
12     Concorde TSP Solver     29    
13     CUTEr     27    
14     IOSO     23    
15     SNOPT     20    
16     DIDO (optimal control)     20    
17     NMath     20    
18     TOMLAB     19    
19     ASTOS     18    
20     PROPT     18    
21     MCSim     17    
22     FortSP     16    
23     IPOPT     15    
24     KNITRO     15    
25     Nl (format)     14    
26     MINTO     12    
27     OPL Development Studio     12    
28     Gurobi     11    
29     Investigative Optimization Library     10    
30     Inverse (program)     8    
31     Galahad library     7    
32     TOMNET     7    
33     TOMVIEW     less than 5 views    
34     FortMP     less than 5 views    
35     MINOS (optimization software)     less than 5 views    
36     PENOPT     less than 5 views    
37     TomSym     less than 5 views    
38     Madeline (software)     less than 5 views    

I'll not have computer with openopt and lpsolve installed sooner than tomorrow, currently you can replace those lines by
from numpy import asarray
lp_handle = List(asarray(...)),...
Pay attention that your example differs from openopt - you solve it before exporting. You'd better try to export w/o solving before it.

Yeah! that made the trick! because my matrix is uni-modular  the results where always integers, so I could even get the sensitivity report. By the way just for improving OpenOpt when I export the MILP to MPS I couldn't get the solution with r=p.solve('glpk', iprint =-1, ) here is the output for the record:

CODE:

Traceback (most recent call last):
  File "C:\Users\Noone\Desktop\Universidad\Programación Matemática\tarea1.py", line 83, in <module>
    r=p.solve('glpk', iprint =-1, )
  File "C:\Python27\lib\site-packages\openopt-0.38-py2.7.egg\openopt\kernel\baseProblem.py", line 236, in solve
    return runProbSolver(self, *args, **kwargs)
  File "C:\Python27\lib\site-packages\openopt-0.38-py2.7.egg\openopt\kernel\runProbSolver.py", line 249, in runProbSolver
    solver(p)
  File "C:\Python27\lib\site-packages\openopt-0.38-py2.7.egg\openopt\solvers\CVXOPT\glpk_oo.py", line 16, in __solver__
    return CVXOPT_LP_Solver(p, 'glpk')
  File "C:\Python27\lib\site-packages\openopt-0.38-py2.7.egg\openopt\solvers\CVXOPT\CVXOPT_LP_Solver.py", line 19, in CVXOPT_LP_Solver
    xBounds2Matrix(p)
  File "C:\Python27\lib\site-packages\openopt-0.38-py2.7.egg\openopt\kernel\ooMisc.py", line 32, in xBounds2Matrix
    if p.useSparse is True or (isspmatrix(p.A) or (scipyInstalled and nLB+nUB>=p.A.shape[0]) and p.useSparse is not False):
AttributeError: 'NoneType' object has no attribute 'shape'

Thanks for everything Dmitrey! you saved my life!
I'm in debt with you, anything u need ask me, I maybe not that good at programming, but I love it.

Regards Francisco

hi,
ask cvxopt google group, I could implement it if and only if it's available via CVXOPT API.
Another solution could be export to MPS format file and edit it somehow or run by glpk binary with some options.
BTW I guess it would look much easier as FuncDesigner code.
Regards, D.

OK, it's seems that the simplest solution was just to write it to MPS and then to run it directly with glpsol.exe (the GLPK binary), first i had a huge problem installing lpSolve, however I compiled it with the python binding (there wasn't an executable for python 2.7) , to get to know the exportToMps command i just copied the one example you have in your page, it didn't work, but it finds the solution to the problem using lpSolve, however the output will say lot more than my words:

Code:

# -*- coding: utf-8 -*-
"""
Created on Thu Apr 26 15:34:32 2012

@author: Noone
"""

from numpy import *
from openopt import MILP
from lp_solve import lpsolve 

f = [1, 2, 3, 4, 5, 4, 2, 1]
    
# indexing starts from ZERO!
# while in native lpsolve-python wrapper from 1
# so if you used [5,8] for native lp_solve python binding
# you should use [4,7] instead
intVars = [4, 7]

lb = -1.5 * ones(8)
ub = 15 * ones(8)
A = zeros((5, 8))
b = zeros(5)
for i in xrange(5):
    for j in xrange(8):
        A[i,j] = -8+sin(8*i) + cos(15*j)
    b[i] = -150 + 80*sin(80*i)

p = MILP(f=f, lb=lb, ub=ub, A=A, b=b, intVars=intVars)

# if file name not ends with '.MPS' or '.mps'
# then '.mps' will be appended
r=p.solve('lpSolve')
success = p.exportToMPS('milp_1')

Output:

------------------------- OpenOpt 0.38 -------------------------
solver: lpSolve   problem: unnamed    type: MILP   goal: minimum
iter   objFunVal   log10(maxResidual)   
    0  0.000e+00               2.36
OpenOpt Warning:
                please install setproctitle module
                (it's available via easy_install and Linux soft channels like apt-get)
    1  2.580e+01            -100.00
istop: 1
Solver:   Time Elapsed = 0.0     CPU Time Elapsed = 0.00237866210869
objFunValue: 25.801451 (feasible, MaxResidual = 0)
Traceback (most recent call last):
  File "C:\Users\Noone\Desktop\Universidad\Programación Matemática\tarea3.py", line 34, in <module>
    success = p.exportToMPS('milp_1')
  File "C:\Python27\lib\site-packages\openopt-0.38-py2.7.egg\openopt\kernel\LP.py", line 93, in exportToMPS
    handler = self.get_lpsolve_handler(maxNameLength, startIndex)
  File "C:\Python27\lib\site-packages\openopt-0.38-py2.7.egg\openopt\kernel\LP.py", line 124, in get_lpsolve_handler
    lp_handle = lp_maker(List(f.flatten()), List(self.Awhole), List(self.bwhole.flatten()), List(self.dwhole.flatten()), \
AttributeError: 'list' object has no attribute 'flatten'

Regards, Francisco

I'm making a binary problem, i've already installed CVOXPT with glpk for OpenOpt, Using Spyder IDE, on Windows 7 x64, and all works like a charm. But how do i do to call some specific glpk options, i want the sensitivity analysis, and to get more output from each point, cos its outputs like 3 points of 12800 or something, whatsoever this is my code:

import xlrd
from openopt import *
from numpy 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])
    #print p

#I=identity(80)
#lb = zeros(80**2*2)
#ub = ones(80**2*2)

#print ub
#print a[0]
#print I
def matriz(n):
    #listoflists=[ [0]*4 ] *5
    O=[ [0]*n**2*2 for y in range(n*3) ]
   # print O
    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)
#print I
#print I
pp=[1]*160

f = m+h
A=I
b=p
print size(b)
b=p+pp
print size(b)

print size(f)
print size(I[0])
print size(I)
print size (b)
binVars=range(80**2*2)
print size(binVars)
#print intVars
#p = MILP(f, A=A, b=b, lb=lb, ub=ub, intVars=intVars, goal='max')
p = MILP(f=f, A=A, b=b, binVars=binVars, goal='max')
r=p.solve('glpk', iprint =-1, )
#r.glp_print_ranges
print 'objFunValue:', r.ff
print 'x_opt:', r.xf

the output:

GLPK Integer Optimizer, v4.47
240 rows, 12800 columns, 19200 non-zeros
12800 integer variables, all of which are binary
Preprocessing...
240 rows, 12800 columns, 19200 non-zeros
12800 integer variables, all of which are binary
Scaling...
A: min|aij| = 1.000e+000  max|aij| = 1.000e+000  ratio = 1.000e+000
Problem data seem to be well scaled
Constructing initial basis...
Size of triangular part = 240
Solving LP relaxation...
GLPK Simplex Optimizer, v4.47
240 rows, 12800 columns, 19200 non-zeros
*     0: obj = -6.660000000e+002  infeas = 0.000e+000 (0)
*   345: obj = -1.289800000e+004  infeas = 0.000e+000 (0)
OPTIMAL SOLUTION FOUND
Integer optimization begins...
+   345: mip =     not found yet >=              -inf        (1; 0)
+   345: >>>>> -1.289800000e+004 >= -1.289800000e+004   0.0% (1; 0)
+   345: mip = -1.289800000e+004 >=     tree is empty   0.0% (0; 1)
INTEGER OPTIMAL SOLUTION FOUND
objFunValue: 12898.0
x_opt: [ 0.  0.  0. ...,  0.  0.  0.]

reading at glpk, the command option should be something like: glpsol ... --ranges file.sen
I know that glpsol it's the binary and not what we are using here...
maybe it should be something to be with the Informational APIs of glpk?

glp_print_ranges should print a human readable sensitivity analysis report

how do I call glpk with this option?

for your time thanks
regards
Francisco

Modern solvers, e.g.  LogMIP, use Convex-Hull or Big-M algorithms for these nonlinear GDP, casting a GDP to series of MINLP, each one is usually solved by a sequence of (possibly nonconvex) NLP, while interalg uses absolutely different method and doesn't create any auxiliary variables and problems.

See also updated chapters of FuncDesigner doc: Boolean variables and functions and Discrete and categorical variables

Since the declared problems for interalg are NP-Hard, sometimes it takes too long to get solution with required accuracy, but sometimes some problems with hundreds of variables were solved during several minutes by slow notebook (here's an example with 100 variables that takes less than 500 seconds on notebook Intel Atom 2 GHz, peak memory consumption 130 MB). Last OpenOpt svn snapshot was used, but I don't think difference with rev 0.38 will be essential in the case.

I expect essential speedup with PyPy (hey say several months till full NumPy support remains), also, I have some ideas for further interalg speedup.

Anyway, it is admirable how quickly you manage to answer every questions!  Thanks for your kind support.