[Clp] Help: Use Clp in Dev C++ and solve the infinity norm minimization
William H. Patton
pattonwh at comcast.net
Wed Nov 30 20:16:55 EST 2011
Ok, It can be an LP the constraints are the deviation slacks for the
N*N elements of the M matrix.
Here is a MathProg formulation and the cplex type Lp generated.
>>>>>>>>>>>>>>>>>>>>
/*
On 11/29/2011 9:53 PM, RiCo wrote:
What I want to do is to solve a problem like this (the minimization of a
Matrix equation):
M=[1 0 2 3; 2 -1 3 5; 4 1 -1 2; 0 -3 4 3];
N=[3 0 4; 1 5 2; 7 1 3; 2 2 1];
K=[1 0 2 3; 2 -1 3 5];
minimize( norm(M-N*X*K,Inf) infinity norm is max of the abs values
of the cells.
return X
(M- ( (N*X) *K) ), M is 4x4, N is 4x3 so X must be 3x? and K is 2x4.
What is the ?; It must be 2. So you have 6 variables Xij {
i=1..3,j=1..2}.
*/
# set of rows of M and cols
set I; # rows of M,N 4
set J; # cols of M,K 4
set K; # rows of K 2
set N; # cols of N 3
# dependent variables
param MM {i in I, j in J };
param NN {i in I, n in N };
param KK {k in K, j in J };
# independent variable
var x {i in I, n in N } >=0;
# define equation variables
var yp {i in I, j in J} , >= 0; # positive deviation
var yn {i in I, j in J} , >= 0; # negative deviation
var z >= 0; # min the max of the (M-N*X*K) for each row of M
var nnx {i in I, n in N} ;
# define objective function
minimize deviation: z;
# define deviation constrains
s.t. u_deviation {i in I, j in J} : z >= yp[i,j] + yn[i,j];
/*
# define equation constraint (M-N*X*K) by cells of N
//s.t. equation {i in I, j in J} : M[i,j] - ( NXK[i,j] ) = yp[i,j] -
yn[i,j];
fix i,p sum {k in ?} ( N[i,k] *
x[k,p]) = NX[i,p]
fix i,j sum {p in P} ( Nx[i,p] *
K[p,j]) = NXK[i,j]
*/
s.t. distance {i in I, j in J} : sum {k in K} (
sum {n in N} (
NN[i,n] * x[n,k]
)
* KK[k,j]
) - MM[i,j] = yp[i,j]
- yn[i,j];
*/* this next one is extra --- just use to check NNX sub product for
above.*/*
s.t. NNXtemp {i in I, k in K} : sum {n in N} (
NN[i,n] * x[n,k]
)
= nnx[i,k] ;
/* */
solve;
/*
*
* DATA section
*
M=[1 0 2 3; 2 -1 3 5; 4 1 -1 2; 0 -3 4 3]; I,J
N=[3 0 4; 1 5 2; 7 1 3; 2 2 1]; I,N
K=[1 0 2 3; 2 -1 3 5]; K,J
*/
data;
set I := 1 2 3 4;
set J := 1 2 3 4;
set K := 1 2;
set N := 1 2 3;
# I J row col
param MM : 1 2 3 4 :=
1 1 0 2 3
2 2 -1 3 5
3 4 1 -1 2
4 0 -3 4 3
;
# I N 4x3
param NN : 1 2 3 :=
1 3 0 4
2 1 5 2
3 7 1 3
4 2 2 1
;
# X is N K 3x2
# K N 2x3
param KK : 1 2 3 4 :=
1 1 0 2 3
2 2 -1 3 5
;
end;
>>>>>>>>>>>>>>>>>>>>>>>>>>>
CPLEX ,lp file
\* Objective function *\
Minimize
deviation: +z
\* Constraints *\
Subject To
u_deviation[1,1]: -yp[1,1] -yn[1,1] +z >= 0
u_deviation[1,2]: -yp[1,2] -yn[1,2] +z >= 0
u_deviation[1,3]: -yp[1,3] -yn[1,3] +z >= 0
u_deviation[1,4]: -yp[1,4] -yn[1,4] +z >= 0
u_deviation[2,1]: -yp[2,1] -yn[2,1] +z >= 0
u_deviation[2,2]: -yp[2,2] -yn[2,2] +z >= 0
u_deviation[2,3]: -yp[2,3] -yn[2,3] +z >= 0
u_deviation[2,4]: -yp[2,4] -yn[2,4] +z >= 0
u_deviation[3,1]: -yp[3,1] -yn[3,1] +z >= 0
u_deviation[3,2]: -yp[3,2] -yn[3,2] +z >= 0
u_deviation[3,3]: -yp[3,3] -yn[3,3] +z >= 0
u_deviation[3,4]: -yp[3,4] -yn[3,4] +z >= 0
u_deviation[4,1]: -yp[4,1] -yn[4,1] +z >= 0
u_deviation[4,2]: -yp[4,2] -yn[4,2] +z >= 0
u_deviation[4,3]: -yp[4,3] -yn[4,3] +z >= 0
u_deviation[4,4]: -yp[4,4] -yn[4,4] +z >= 0
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
distance[1,2]: -3 x[1,2] -4 x[3,2] -yp[1,2] +yn[1,2] = -0
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
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
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
distance[2,2]: -x[1,2] -5 x[2,2] -2 x[3,2] -yp[2,2] +yn[2,2] = -1
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
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
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
distance[3,2]: -7 x[1,2] -x[2,2] -3 x[3,2] -yp[3,2] +yn[3,2] = 1
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
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
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
distance[4,2]: -2 x[1,2] -2 x[2,2] -x[3,2] -yp[4,2] +yn[4,2] = -3
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
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
NNXtemp[1,1]: +3 x[1,1] +4 x[3,1] -nnx[1,1] = -0
NNXtemp[1,2]: +3 x[1,2] +4 x[3,2] -nnx[1,2] = -0
NNXtemp[2,1]: +x[1,1] +5 x[2,1] +2 x[3,1] -nnx[2,1] = -0
NNXtemp[2,2]: +x[1,2] +5 x[2,2] +2 x[3,2] -nnx[2,2] = -0
NNXtemp[3,1]: +7 x[1,1] +x[2,1] +3 x[3,1] -nnx[3,1] = -0
NNXtemp[3,2]: +7 x[1,2] +x[2,2] +3 x[3,2] -nnx[3,2] = -0
NNXtemp[4,1]: +2 x[1,1] +2 x[2,1] +x[3,1] -nnx[4,1] = -0
NNXtemp[4,2]: +2 x[1,2] +2 x[2,2] +x[3,2] -nnx[4,2] = -0
\* Variable bounds *\
Bounds
nnx[1,1] >= -Inf
nnx[1,2] >= -Inf
nnx[2,1] >= -Inf
nnx[2,2] >= -Inf
nnx[3,1] >= -Inf
nnx[3,2] >= -Inf
nnx[4,1] >= -Inf
nnx[4,2] >= -Inf
End
On 11/30/2011 11:11 AM, William H. Patton wrote:
> I would start in any matlab clone first.
> Then I would not try the api. rather look at the text file input forms
> like .lp for rowise entry
> or The harder .MPS for column oriented input.
>
> I cannot understand your example. I assume that the M,N,X,K are
> expressed as row vectors.
> and parenthesis go (M- ( (N*X) *K) ), M is 4x4, N is 4x3 so X
> must be 3x? and K is 2x4.
> What is the ?; It must be 2. So you have 6 variables Xij {
> i=1..3,j=1..2}.
> Then (M- ( (N*X) *K) ) has 16 terms on these 6 variables.
> The infinity norm is the Max of what? Presumably this form.
> What are the constraints? the 6 vars positive? or free?
>
> Lets look at a smaller case M = {1} N = {3} K = { 2} then the
> problem is MAX{x}( 1 - 3*x*2 );
> 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.
>
> 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.
> >>*very big size* - this could be trouble because LP usually likes
> sparse structures. Your formulation is initially dense
> Start small and verify as in your example.
> There really is no good reason to use C or the API as the generator
> for matrix posed problems.
> I would try gnu *mathprog *or a matlab clone or something from the R
> statistics repository.
> http://www.cs.unb.ca/~bremner/docs/glpk/gmpl.pdf
> Decision tree: http://plato.asu.edu/guide.html
>
> William
>
> On 11/29/2011 9:53 PM, RiCo wrote:
>> Hi,
>>
>> 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.
>>
>> I wrote a C program using Dev C++ and want to call the API of Clp.
>>
>> What I want to do is to solve a problem like this (the minimization
>> of a Matrix equation):
>>
>> M=[1 0 2 3; 2 -1 3 5; 4 1 -1 2; 0 -3 4 3];
>> N=[3 0 4; 1 5 2; 7 1 3; 2 2 1];
>> K=[1 0 2 3; 2 -1 3 5];
>> minimize( norm(M-N*X*K,Inf) )
>> return X
>>
>> 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.
>>
>> I wish someone could help me with this issue. Any advice is very
>> appreciated.
>>
>> Thank you so much.
>>
>>
>>
>>
>>
>>
>> _______________________________________________
>> Clp mailing list
>> Clp at list.coin-or.org
>> http://list.coin-or.org/mailman/listinfo/clp
>
>
> _______________________________________________
> Clp mailing list
> Clp at list.coin-or.org
> http://list.coin-or.org/mailman/listinfo/clp
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://list.coin-or.org/pipermail/clp/attachments/20111130/df54ea16/attachment.html>
More information about the Clp
mailing list