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'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.

I'm trying to use solver bvls.

Following your docs, I did "f2py -c -m bvls bvls.f" but the solver does not work.
(Stays in x0, or diverges.)

I guess that the problem might be the in the fact that I use x86_64 Windows, MINGW compiler, as packed in the Enthought Python distribution.

In case you can help me, I'd be grateful.

Stepan

My name is Sudhamsh Reddy. I am a grad student at university of Texas at Arlington, USA. I am trying to use the openopt python library to solve a LCP problem. I am using python version 2.7.2, numpy 1.5.1 and openopt 0.34. I am getting a numpy error. I am including a snapshot of my code with the output error details.
\
\
Code:
#!/usr/bin/python

from numpy import *
from scipy import *
from openopt import LCP

M = array([[0, 0, -3.0, -1.0], [0,0,-3.0,-1.0], [-3.0,-1.0,0,0], [-10.0,-2.0,0,0]])

q = array([[-1.0],[-1.0],[-1.0],[-1.0]])

p=LCP(M,q)
a=p.solve('lcpsolve')

------------------------------------

Error:

sudhamsh@sudhamsh-Parallels-Virtual-Platform:~$ python lcp_nash.py

------------------------- OpenOpt 0.34 -------------------------
solver: lcp   problem: unnamed    type: LCP
iter   objFunVal   
    0  4.000e+00
Traceback (most recent call last):
  File "lcp_nash.py", line 22, in <module>
    a=p.solve('lcpsolve')
  File "/usr/lib/pymodules/python2.7/openopt/kernel/baseProblem.py", line 235, in solve
    return runProbSolver(self, *args, **kwargs)
  File "/usr/lib/pymodules/python2.7/openopt/kernel/runProbSolver.py", line 237, in runProbSolver
    solver(p)
  File "/usr/lib/pymodules/python2.7/openopt/solvers/HongKongOpt/lcpsolve_oo.py", line 20, in __solver__
    w, z, retcode = LCPSolve(p.M,p.q, pivtol=self.pivtol)
  File "/usr/lib/pymodules/python2.7/openopt/solvers/HongKongOpt/LCPSolve.py", line 58, in LCPSolve
    tableau = hstack([eye(dimen), -M, -ones((dimen, 1)), asarray(asmatrix(q).T)])
  File "/usr/lib/pymodules/python2.7/numpy/core/shape_base.py", line 258, in hstack
    return _nx.concatenate(map(atleast_1d,tup),1)
ValueError: array dimensions must agree except for d_0

        if phase==1:
            A_free = A[:,i_free.squeeze()]
            if m_free<=k:               
                if m_free>0:
                    p_free=np.linalg.lstsq(-A_free,r)[0]               
            else:               
                q1,r1=qr(A_free.T)
                p_free=-q1.dot(np.solve(r1.T,r))
            p=np.zeros((m,1))
            p[i_free.squeeze()]=p_free

The situation is like this:
i = 3;    m_free = 0;    i_free = [[True], [False], [False]];    p_free.shape = (2,1)

The problem seems to be that for m_free=0, the variable p_free is not assigned, so it contains a value from previous computation.  In my case, it's shape was not suitable, so I got an error message.

Could you please give me a hint how this can be fixed?  (If you commit a fix, I can find it there.)

Thank you very much.

I'm trying to develop  C code for solving some distributed optimization problems which employs IPOPT.

I'm trying to solve problems  in a FOR loop ( at each step i define a new Ipopt problem and then i free it with FreeIpoptProblem), but after the first step the IPOPT solver starts and i get a segmentation fault.

Everything in the first step runs just dandy, i get status==Solve_Succeeded, etc.

I tried it as direct code in my main function, then i defined a separate function where i call Ipoptsolve, but to no avail, same result.

Has anyone encountered this issue before?

Any advice would be appreciated, thanks.

I wish someone collaborate on this discussion. Sundials and others are too complex?
Excel too slow when necessary to integrate!

  I am Sándor Kolumbán, a Hungarian PhD student and I am using interalg fo solve some global optimization problems with multiple global minima.

  As interalg is an interval analytic solver I assume it evaluates the whole decision space. It may be that my assumption is wrong, but in case it is not, I have some questions:

1.: The end result of the optimization is given as a single point. I would have expected to get a small box that contains the global minimum. Why is this? I understand that the underlying interval analysis module does not count the rounding errors but even so, returning a point estimate is not what I expected?

2.: My functions always have more than one global minima but only one of them is found. Since the location of the other global minima has to be examined somehow that it does not contain a better point I would have expected to get that other point as well. Is there any reason for the other global optimum points not being delivered?

3.: I would like to read about the algorithm that is implemented in the toolbox. Can you point to a paper or some literature?

Best regards,

Kolumbán

I have faced a non-linear problem in my modeling. My model is as follows:
max sigma {x_i}
s.t.
   x_i.y_i=z_i  1<i<n
   ....
   some linear constrains

In this models, x_i, y_i, and z_i are continuous variables for {1<i<n}. As you can see we have a product term in constrains. My question is if this problem is P or NP? I strongly think it is NP. This is because the I found that the product term can be approximated by peicewise linear optimization techniques (