<html>
<head>
<meta content="text/html; charset=ISO-8859-1"
http-equiv="Content-Type">
</head>
<body text="#000000" bgcolor="#FFFFFF">
Ok, It can be an LP the constraints are the deviation slacks for
the N*N elements of the M matrix.<br>
<br>
Here is a MathProg formulation and the cplex type Lp generated.<br>
>>>>>>>>>>>>>>>>>>>><br>
/*<br>
On 11/29/2011 9:53 PM, RiCo wrote:<br>
What I want to do is to solve a problem like this (the minimization
of a Matrix equation):<br>
<br>
M=[1 0 2 3; 2 -1 3 5; 4 1 -1 2; 0 -3 4 3];<br>
N=[3 0 4; 1 5 2; 7 1 3; 2 2 1];<br>
K=[1 0 2 3; 2 -1 3 5];<br>
minimize( norm(M-N*X*K,Inf) infinity norm is max of the abs
values of the cells.<br>
return X<br>
<br>
(M- ( (N*X) *K) ), M is 4x4, N is 4x3 so X must be 3x? and K
is 2x4.<br>
What is the ?; It must be 2. So you have 6 variables Xij {
i=1..3,j=1..2}.<br>
<br>
*/<br>
<br>
# set of rows of M and cols<br>
<br>
set I; # rows of M,N 4<br>
set J; # cols of M,K 4<br>
set K; # rows of K 2<br>
set N; # cols of N 3<br>
<br>
<br>
<br>
<br>
<br>
# dependent variables<br>
param MM {i in I, j in J };<br>
param NN {i in I, n in N };<br>
param KK {k in K, j in J };<br>
<br>
# independent variable<br>
<br>
var x {i in I, n in N } >=0;<br>
<br>
# define equation variables<br>
var yp {i in I, j in J} , >= 0; # positive deviation<br>
var yn {i in I, j in J} , >= 0; # negative deviation<br>
var z >= 0; # min the max of the (M-N*X*K) for each row of
M<br>
var nnx {i in I, n in N} ;<br>
<br>
<br>
# define objective function<br>
<br>
minimize deviation: z;<br>
<br>
# define deviation constrains<br>
<br>
s.t. u_deviation {i in I, j in J} : z >= yp[i,j] + yn[i,j];<br>
<br>
<br>
/*<br>
# define equation constraint (M-N*X*K) by cells of N<br>
<br>
//s.t. equation {i in I, j in J} : M[i,j] - ( NXK[i,j] ) = yp[i,j]
- yn[i,j];<br>
fix i,p sum {k in ?} ( N[i,k] *
x[k,p]) = NX[i,p]<br>
fix i,j sum {p in P} ( Nx[i,p] *
K[p,j]) = NXK[i,j]<br>
*/<br>
s.t. distance {i in I, j in J} : sum {k in K} (<br>
sum {n in N} (<br>
NN[i,n] *
x[n,k]<br>
)<br>
* KK[k,j]<br>
) - MM[i,j] =
yp[i,j] - yn[i,j];<br>
<br>
<b>/* this next one is extra --- just use to check NNX sub
product for above.*/</b><br>
s.t. NNXtemp {i in I, k in K} : sum {n in N} (<br>
NN[i,n] *
x[n,k]<br>
)<br>
= nnx[i,k] ;<br>
/* */<br>
solve;<br>
<br>
<br>
<br>
/*<br>
*<br>
* DATA section<br>
*<br>
M=[1 0 2 3; 2 -1 3 5; 4 1 -1 2; 0 -3 4 3]; I,J<br>
N=[3 0 4; 1 5 2; 7 1 3; 2 2 1]; I,N<br>
K=[1 0 2 3; 2 -1 3 5]; K,J<br>
*/<br>
<br>
data;<br>
set I := 1 2 3 4;<br>
set J := 1 2 3 4;<br>
set K := 1 2;<br>
set N := 1 2 3;<br>
<br>
# I J row col<br>
param MM : 1 2 3 4 :=<br>
1 1 0 2 3<br>
2 2 -1 3 5<br>
3 4 1 -1 2<br>
4 0 -3 4 3<br>
;<br>
<br>
# I N 4x3<br>
param NN : 1 2 3 :=<br>
1 3 0 4<br>
2 1 5 2<br>
3 7 1 3<br>
4 2 2 1<br>
;<br>
<br>
# X is N K 3x2<br>
# K N 2x3<br>
param KK : 1 2 3 4 :=<br>
1 1 0 2 3<br>
2 2 -1 3 5<br>
;<br>
<br>
end;<br>
<br>
<br>
<br>
>>>>>>>>>>>>>>>>>>>>>>>>>>><br>
<br>
CPLEX ,lp file<br>
\* Objective function *\<br>
Minimize<br>
deviation: +z<br>
<br>
\* Constraints *\<br>
Subject To<br>
u_deviation[1,1]: -yp[1,1] -yn[1,1] +z >= 0<br>
u_deviation[1,2]: -yp[1,2] -yn[1,2] +z >= 0<br>
u_deviation[1,3]: -yp[1,3] -yn[1,3] +z >= 0<br>
u_deviation[1,4]: -yp[1,4] -yn[1,4] +z >= 0<br>
u_deviation[2,1]: -yp[2,1] -yn[2,1] +z >= 0<br>
u_deviation[2,2]: -yp[2,2] -yn[2,2] +z >= 0<br>
u_deviation[2,3]: -yp[2,3] -yn[2,3] +z >= 0<br>
u_deviation[2,4]: -yp[2,4] -yn[2,4] +z >= 0<br>
u_deviation[3,1]: -yp[3,1] -yn[3,1] +z >= 0<br>
u_deviation[3,2]: -yp[3,2] -yn[3,2] +z >= 0<br>
u_deviation[3,3]: -yp[3,3] -yn[3,3] +z >= 0<br>
u_deviation[3,4]: -yp[3,4] -yn[3,4] +z >= 0<br>
u_deviation[4,1]: -yp[4,1] -yn[4,1] +z >= 0<br>
u_deviation[4,2]: -yp[4,2] -yn[4,2] +z >= 0<br>
u_deviation[4,3]: -yp[4,3] -yn[4,3] +z >= 0<br>
u_deviation[4,4]: -yp[4,4] -yn[4,4] +z >= 0<br>
distance[1,1]: +3 x[1,1] +4 x[3,1] +6 x[1,2] +8 x[3,2] -yp[1,1]
+yn[1,1] = 1<br>
distance[1,2]: -3 x[1,2] -4 x[3,2] -yp[1,2] +yn[1,2] = -0<br>
distance[1,3]: +6 x[1,1] +8 x[3,1] +9 x[1,2] +12 x[3,2] -yp[1,3]
+yn[1,3] = 2<br>
distance[1,4]: +9 x[1,1] +12 x[3,1] +15 x[1,2] +20 x[3,2] -yp[1,4]
+yn[1,4] = 3<br>
distance[2,1]: +x[1,1] +5 x[2,1] +2 x[3,1] +2 x[1,2] +10 x[2,2] +4
x[3,2] -yp[2,1] +yn[2,1] = 2<br>
distance[2,2]: -x[1,2] -5 x[2,2] -2 x[3,2] -yp[2,2] +yn[2,2] = -1<br>
distance[2,3]: +2 x[1,1] +10 x[2,1] +4 x[3,1] +3 x[1,2] +15 x[2,2]
+6 x[3,2] -yp[2,3] +yn[2,3] = 3<br>
distance[2,4]: +3 x[1,1] +15 x[2,1] +6 x[3,1] +5 x[1,2] +25 x[2,2]
+10 x[3,2] -yp[2,4] +yn[2,4] = 5<br>
distance[3,1]: +7 x[1,1] +x[2,1] +3 x[3,1] +14 x[1,2] +2 x[2,2] +6
x[3,2] -yp[3,1] +yn[3,1] = 4<br>
distance[3,2]: -7 x[1,2] -x[2,2] -3 x[3,2] -yp[3,2] +yn[3,2] = 1<br>
distance[3,3]: +14 x[1,1] +2 x[2,1] +6 x[3,1] +21 x[1,2] +3 x[2,2]
+9 x[3,2] -yp[3,3] +yn[3,3] = -1<br>
distance[3,4]: +21 x[1,1] +3 x[2,1] +9 x[3,1] +35 x[1,2] +5 x[2,2]
+15 x[3,2] -yp[3,4] +yn[3,4] = 2<br>
distance[4,1]: +2 x[1,1] +2 x[2,1] +x[3,1] +4 x[1,2] +4 x[2,2] +2
x[3,2] -yp[4,1] +yn[4,1] = -0<br>
distance[4,2]: -2 x[1,2] -2 x[2,2] -x[3,2] -yp[4,2] +yn[4,2] = -3<br>
distance[4,3]: +4 x[1,1] +4 x[2,1] +2 x[3,1] +6 x[1,2] +6 x[2,2] +3
x[3,2] -yp[4,3] +yn[4,3] = 4<br>
distance[4,4]: +6 x[1,1] +6 x[2,1] +3 x[3,1] +10 x[1,2] +10 x[2,2]
+5 x[3,2] -yp[4,4] +yn[4,4] = 3<br>
NNXtemp[1,1]: +3 x[1,1] +4 x[3,1] -nnx[1,1] = -0<br>
NNXtemp[1,2]: +3 x[1,2] +4 x[3,2] -nnx[1,2] = -0<br>
NNXtemp[2,1]: +x[1,1] +5 x[2,1] +2 x[3,1] -nnx[2,1] = -0<br>
NNXtemp[2,2]: +x[1,2] +5 x[2,2] +2 x[3,2] -nnx[2,2] = -0<br>
NNXtemp[3,1]: +7 x[1,1] +x[2,1] +3 x[3,1] -nnx[3,1] = -0<br>
NNXtemp[3,2]: +7 x[1,2] +x[2,2] +3 x[3,2] -nnx[3,2] = -0<br>
NNXtemp[4,1]: +2 x[1,1] +2 x[2,1] +x[3,1] -nnx[4,1] = -0<br>
NNXtemp[4,2]: +2 x[1,2] +2 x[2,2] +x[3,2] -nnx[4,2] = -0<br>
<br>
\* Variable bounds *\<br>
Bounds<br>
nnx[1,1] >= -Inf<br>
nnx[1,2] >= -Inf<br>
nnx[2,1] >= -Inf<br>
nnx[2,2] >= -Inf<br>
nnx[3,1] >= -Inf<br>
nnx[3,2] >= -Inf<br>
nnx[4,1] >= -Inf<br>
nnx[4,2] >= -Inf<br>
<br>
End<br>
On 11/30/2011 11:11 AM, William H. Patton wrote:
<blockquote cite="mid:4ED663A9.1030203@comcast.net" type="cite">
<meta content="text/html; charset=ISO-8859-1"
http-equiv="Content-Type">
I would start in any matlab clone first.<br>
Then I would not try the api. rather look at the text file input
forms like .lp for rowise entry<br>
or The harder .MPS for column oriented input.<br>
<br>
I cannot understand your example. I assume that the M,N,X,K are
expressed as row vectors.<br>
and parenthesis go (M- ( (N*X) *K) ), M is 4x4, N is 4x3
so X must be 3x? and K is 2x4.<br>
What is the ?; It must be 2. So you have 6 variables Xij {
i=1..3,j=1..2}.<br>
Then (M- ( (N*X) *K) ) has 16 terms on these 6 variables.<br>
The infinity norm is the Max of what? Presumably this form.<br>
What are the constraints? the 6 vars positive? or free?<br>
<br>
Lets look at a smaller case M = {1} N = {3} K = { 2} then the
problem is MAX{x}( 1 - 3*x*2 );<br>
This is not much like an LP. I do not see it being much different
in 2 or 10 variables. It appears as just a form with no
constraint equations.<br>
<br>
Is it accidental that K is the first 2 rows of M? If not then
rewrite M as {K,L} and look for a simplification.<br>
>><b>very big size</b> - this could be trouble because LP
usually likes sparse structures. Your formulation is initially
dense<br>
Start small and verify as in your example.<br>
There really is no good reason to use C or the API as the
generator for matrix posed problems.<br>
I would try gnu <b>mathprog </b>or a matlab clone or something
from the R statistics repository.<br>
<a moz-do-not-send="true" class="moz-txt-link-freetext"
href="http://www.cs.unb.ca/%7Ebremner/docs/glpk/gmpl.pdf">http://www.cs.unb.ca/~bremner/docs/glpk/gmpl.pdf</a><br>
Decision tree: <a moz-do-not-send="true"
class="moz-txt-link-freetext"
href="http://plato.asu.edu/guide.html">http://plato.asu.edu/guide.html</a><br>
<br>
William<br>
<br>
On 11/29/2011 9:53 PM, RiCo wrote:
<blockquote
cite="mid:CAJveyzC=MwzrPWH3QfogR8iOUzvc5u635Kzts7m=4+Lq2ZNhBQ@mail.gmail.com"
type="cite">Hi,
<div><br>
</div>
<div>I have read the installation guide. Since I am new in
C/C++ and Clp, I am sorry but I don' understand how and where
to implement the "make" instruction to tell the Dev C++ to
link to Clp. There are many details which are complex to me. </div>
<div><br>
</div>
<div>I wrote a C program using Dev C++ and want to call the API
of Clp.</div>
<div><br>
</div>
<div>What I want to do is to solve a problem like this (the
minimization of a Matrix equation):</div>
<div><br>
</div>
<div>
<div>M=[1 0 2 3; 2 -1 3 5; 4 1 -1 2; 0 -3 4 3];</div>
<div>N=[3 0 4; 1 5 2; 7 1 3; 2 2 1];</div>
<div>K=[1 0 2 3; 2 -1 3 5];</div>
</div>
<div>minimize( norm(M-N*X*K,Inf) )</div>
<div>return X </div>
<div><br>
</div>
<div>In real case, M, N, and K are all in very big size. My C
program will generate these three matrix. I hope to call Clp
API to solve this minimization problem. </div>
<div><br>
</div>
<div>I wish someone could help me with this issue. Any advice is
very appreciated. </div>
<div><br>
</div>
<div>Thank you so much.</div>
<div><br>
</div>
<div><br>
</div>
<div><br>
</div>
<div><br>
</div>
<br>
<fieldset class="mimeAttachmentHeader"></fieldset>
<br>
<pre wrap="">_______________________________________________
Clp mailing list
<a moz-do-not-send="true" class="moz-txt-link-abbreviated" href="mailto:Clp@list.coin-or.org">Clp@list.coin-or.org</a>
<a moz-do-not-send="true" class="moz-txt-link-freetext" href="http://list.coin-or.org/mailman/listinfo/clp">http://list.coin-or.org/mailman/listinfo/clp</a>
</pre>
</blockquote>
<br>
<fieldset class="mimeAttachmentHeader"></fieldset>
<br>
<pre wrap="">_______________________________________________
Clp mailing list
<a class="moz-txt-link-abbreviated" href="mailto:Clp@list.coin-or.org">Clp@list.coin-or.org</a>
<a class="moz-txt-link-freetext" href="http://list.coin-or.org/mailman/listinfo/clp">http://list.coin-or.org/mailman/listinfo/clp</a>
</pre>
</blockquote>
</body>
</html>