The L1 norm problem has a
different formulation.
If you want to find an m-vector B
of unknowns (the "beta's" in a linear regression setting) so that for
n-vector Y (the "dependent" variables) and X (n x m) matrix (the
"independent" variable), and you want to minimize the L1 norm of
||Y-XB||, the resulting LP is something like
Find two n-vectors RP and RN
(positive residuals and negative residuals) so that
min
RP(transpose) 1 + RN(transpose) 1
subject to:
Y - XB = RP -
RN
and RP >=0 and RN >=
0
here the notation RP(transpose) 1
is the vector product of the RP vector with the vector of all 1's.
So the objective value is the sum of the elements of RP plus the sum of
the elements of RN.
Looking at your model, I don't see
anything similar.
-Marc
Well, you got the message:
"PROBLEM HAS NO FEASIBLE
SOLUTION"
So, I think that your problem does not have any
solution that satisfies all your constraints... There are no error in
your GMPL code. I suggest you verify your mathematical
model.
Good luck
Wendel Alexandre Melo
Master degree
student
Federal University of Rio de Janeiro
2010/8/12 Reginald Beardsley
<address@hidden>
sun_x86%rhb {3967} /app/pkgs/gnu/glpk/4.44/bin/glpsol
--lp aa GLPSOL: GLPK LP/MIP Solver, v4.44 Parameter(s)
specified in the command line: --lp aa Reading
problem data from `aa'... 24 rows, 5 columns, 93
non-zeros 33 lines were read GLPK Simplex Optimizer,
v4.44 24 rows, 5 columns, 93
non-zeros Preprocessing... 23 rows, 4 columns, 92
non-zeros Scaling... A: min|aij| =
1.184e-01 max|aij| = 1.000e+00 ratio =
8.446e+00 Problem data seem to be well scaled Constructing
initial basis... Size of triangular part =
1 0: obj =
-1.875260000e+01 infeas = 1.875e+01
(22) 3: obj =
-4.969124211e-02 infeas = 4.848e-02 (20) PROBLEM
HAS NO FEASIBLE SOLUTION glp_simplex: unable to recover
undefined or non-optimal solution Time used: 0.0
secs Memory used: 0.1 Mb (56761 bytes) sun_x86%rhb {3968}
--- On Thu, 8/12/10, Wendel Alexandre Xavier de
Melo <address@hidden>
wrote:
From:
Wendel Alexandre Xavier de Melo <address@hidden> Subject:
Re: [Help-glpk] What am I missing? To: "Reginald Beardsley"
<address@hidden> Date:
Thursday, August 12, 2010, 12:45 PM
Hi Reginald
What is the your error message?
Best regards
Wendel
2010/8/12 Reginald Beardsley <address@hidden>
I'm
trying to use glpk for the first time. I can run plan.lp OK,
but when I try to set up my own problem, it fails. Looking
at the examples and rereading the manual has not gotten
through my thick head what I'm doing wrong.
I'm
attempting a basis pursuit, so I want to find the
coefficients for a set of wavelets from a dictionary that
sum to the measured data subject to an L1 norm. This example
is exact. x0=1 x1=0 x2=2 x3=3. sum is the sum of the last
column (i.e. RHS).
Thanks, Reg
Here's my
attempt to construct an example using CPLEX
format:
minimize z : + 21 x0 + 13.27 x1 + 6.769 x2
+ 5.262 x3 - 50.3246 subject to t1 : + 1 x0 + 1 x1 + 1
x2 + 1 x3 = 6 t2 : + 0.9912 x0 + 0.9206 x1 + 0.6255 x2 +
0.465 x3 = 3.637 t3 : + 0.9826 x0 + 0.8524 x1 + 0.4832 x2
+ 0.3568 x3 = 3.02 t4 : + 0.9741 x0 + 0.7936 x1 + 0.4075
x2 + 0.3008 x3 = 2.692 t5 : + 0.9657 x0 + 0.7426 x1 +
0.3591 x2 + 0.265 x3 = 2.479 t6 : + 0.9575 x0 + 0.6981 x1
+ 0.3246 x2 + 0.2396 x3 = 2.325 t7 : + 0.9493 x0 + 0.6591
x1 + 0.2985 x2 + 0.2203 x3 = 2.207 t8 : + 0.9414 x0 +
0.6248 x1 + 0.2778 x2 + 0.2051 x3 = 2.112 t9 : + 0.9335
x0 + 0.5944 x1 + 0.261 x2 + 0.1926 x3 = 2.033 t10 : +
0.9258 x0 + 0.5674 x1 + 0.2468 x2 + 0.1822 x3 = 1.966 t11
: + 0.9181 x0 + 0.5433 x1 + 0.2348 x2 + 0.1733 x3 =
1.907 t12 : + 0.9106 x0 + 0.5216 x1 + 0.2243 x2 + 0.1656
x3 = 1.856 t13 : + 0.9032 x0 + 0.502 x1 + 0.2151 x2 +
0.1588 x3 = 1.81 t14 : + 0.896 x0 + 0.4843 x1 + 0.207 x2
+ 0.1528 x3 = 1.768 t15 : + 0.8888 x0 + 0.4682 x1 +
0.1997 x2 + 0.1474 x3 = 1.731 t16 : + 0.8817 x0 + 0.4535
x1 + 0.1932 x2 + 0.1426 x3 = 1.696 t17 : + 0.8748 x0 +
0.44 x1 + 0.1872 x2 + 0.1382 x3 = 1.664 t18 : + 0.8679 x0
+ 0.4275 x1 + 0.1818 x2 + 0.1342 x3 = 1.634 t19 : +
0.8612 x0 + 0.416 x1 + 0.1768 x2 + 0.1305 x3 = 1.606 t20
: + 0.8545 x0 + 0.4054 x1 + 0.1722 x2 + 0.1271 x3 =
1.58 t21 : + 0.848 x0 + 0.3955 x1 + 0.168 x2 + 0.124 x3 =
1.556 t22 : + 0.8415 x0 + 0.3863 x1 + 0.164 x2 + 0.1211
x3 = 1.533 t23 : + 0.8352 x0 + 0.3777 x1 + 0.1603 x2 +
0.1184 x3 = 1.511 bounds x0 >= 0.0 x1 >=
0.0 x2 >= 0.0 x3 >=
0.0 end
_______________________________________________ Help-glpk
mailing list address@hidden http://lists.gnu.org/mailman/listinfo/help-glpk
--
Wendel
|
--
Wendel
----------------------------------------------------------------------------
This e-mail and any attachments may be confidential or legally
privileged. If you received this message in error or are not the
intended recipient, you should destroy the e-mail message and any
attachments or copies, and you are prohibited from retaining,
distributing, disclosing or using any information contained herein.
Please inform us of the erroneous delivery by return e-mail.
Thank you for your
cooperation.
----------------------------------------------------------------------------