Take the simple regression model Y = b0 + X*b1, where Y is an n-vector and X is an n-vector. Suppose n=4, and Y = [1 2 3 4] and X = [19 13 81 6]. b0 (the constant term) and b1 (the coefficent) are unknowns. Define 8 more variables: rp1, rp2, rp3, rp4, rn1, rn2, rn3, rn4. The linear program model that finds the L1 regression estimates for b0 and b1 is: min rp1 + rp2 + rp3 + rp4 + rn1 + rn2 + rn3 + rn4 subject to: 1 = b0 + 19*b1 + rp1 - rn1 2 = b0 + 13*b1 + rp2 - rn2 3 = b0 + 18*b1 + rp3 - rn3 4 = b0 + 6*b1 + rp4 - rn4 and rp1>=0, rp2>=0, rp3>=0, rp4>=0, rn1>=0, rn2>=0, rn3>=0, rn4>=0 (and no restrictions on b0, b1) Hope this helps. -Marc
________________________________ From: Reginald Beardsley [mailto:[email protected]] Sent: Thursday, August 12, 2010 3:16 PM To: Meketon, Marc Cc: Wendel Alexandre Xavier de Melo; [email protected] Subject: RE: [Help-glpk] What am I missing? Please forgive my being thick headed, but I don't see how to set that up in in a CPLEX file. If I try to set that up it complains about not having a RHS. Can you direct me to a small example? --- On Thu, 8/12/10, Meketon, Marc <[email protected]> wrote: From: Meketon, Marc <[email protected]> Subject: RE: [Help-glpk] What am I missing? To: "Reginald Beardsley" <[email protected]> Cc: "Wendel Alexandre Xavier de Melo" <[email protected]>, [email protected] Date: Thursday, August 12, 2010, 1:27 PM 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 ________________________________ From: [email protected] [mailto:[email protected]] On Behalf Of Wendel Alexandre Xavier de Melo Sent: Thursday, August 12, 2010 2:08 PM To: Reginald Beardsley; [email protected] Subject: Re: [Help-glpk] What am I missing? 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 <[email protected]> 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 <[email protected]> wrote: From: Wendel Alexandre Xavier de Melo <[email protected]> Subject: Re: [Help-glpk] What am I missing? To: "Reginald Beardsley" <[email protected]> Date: Thursday, August 12, 2010, 12:45 PM Hi Reginald What is the your error message? Best regards Wendel 2010/8/12 Reginald Beardsley <[email protected] <http://mc/[email protected]> > 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 [email protected] <http://mc/[email protected]> 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. ------------------------------------------------------------------------ ---- ---------------------------------------------------------------------------- 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. ----------------------------------------------------------------------------
_______________________________________________ Help-glpk mailing list [email protected] http://lists.gnu.org/mailman/listinfo/help-glpk
