3 /* Copyright (c) 2007 Arnaud Legrand, Pedro Velho. All rights reserved. */
5 /* This program is free software; you can redistribute it and/or modify it
6 * under the terms of the license (GNU LGPL) which comes with this package. */
9 #include "xbt/sysdep.h"
11 #include "maxmin_private.h"
14 #include <declarations.h>
20 XBT_LOG_NEW_DEFAULT_SUBCATEGORY(surf_sdp, surf,
21 "Logging specific to SURF (sdp)");
28 ########################################################################
29 ######################## Simple Proportionnal fairness #################
30 ########################################################################
31 ####### Original problem ##########
40 # We assume in the following that n=2^K
42 ####### Standard SDP form #########
44 # A SDP can be written in the following standard form:
46 # (P) min c1*x1+c2*x2+...+cm*xm
47 # st F1*x1+F2*x2+...+Fm*xm-F0=X
50 # Where F1, F2, ..., Fm are symetric matrixes of size n by n. The
51 # constraint X>0 means that X must be positive semidefinite positive.
53 ########## Equivalent SDP #########
57 # y(k,i) for k in [0,K] and i in [1,2^k]
62 # y(2,1) y(2,2) y(2,3) y(2,4)
63 # y(3,1) y(3,2) y(3,3) y(3,4) y(3,5) y(3,6) y(3,7) y(3,8)
64 # -------------------------------------------------------
65 # x_1 x_2 x_3 x_4 x_5 x_6 x_7 x_8
68 # Structure Constraints:
70 # forall k in [0,K-1], and i in [1,2^k]
71 # [ y(k, 2i-1) y(k-1, i) ]
72 # [ y(k-1, i ) y(k, 2i) ]
76 # Capacity Constraints:
78 # -(A.y(K,*))_l >= - b_l
80 # Positivity Constraints:
81 # forall k in [0,K], and i in [1,2^k]
90 //typedef struct lmm_system {
92 // s_xbt_swag_t variable_set; /* a list of lmm_variable_t */
93 // s_xbt_swag_t constraint_set; /* a list of lmm_constraint_t */
94 // s_xbt_swag_t active_constraint_set; /* a list of lmm_constraint_t */
95 // s_xbt_swag_t saturated_variable_set; /* a list of lmm_variable_t */
96 // s_xbt_swag_t saturated_constraint_set; /* a list of lmm_constraint_t_t */
97 // xbt_mallocator_t variable_mallocator;
100 #define get_y(a,b) (pow(2,a)+b-1)
102 void sdp_solve(lmm_system_t sys)
104 lmm_variable_t var = NULL;
107 * SDP mapping variables.
114 int nb_cnsts_capacity=0;
115 int nb_cnsts_struct=0;
116 int nb_cnsts_positivy=0;
120 FILE *sdpout = fopen("SDPA-printf.tmp","w");
127 * CSDP library specific variables.
129 struct blockmatrix C;
130 struct blockmatrix X,Z;
134 struct constraintmatrix *constraints;
137 lmm_constraint_t cnst = NULL;
138 lmm_element_t elem = NULL;
139 xbt_swag_t cnst_list = NULL;
140 xbt_swag_t var_list = NULL;
141 xbt_swag_t elem_list = NULL;
142 double min_usage = -1;
145 if ( !(sys->modified))
149 * Those fields are the top level description of the platform furnished in the xml file.
151 flows = xbt_swag_size(&(sys->variable_set));
152 links = xbt_swag_size(&(sys->active_constraint_set));
155 * This number is found based on the tree structure explained on top.
157 K = (int)log((double)flows)/log(2.0);
160 * The number of variables in the SDP style.
162 nb_var = get_y(K, pow(2,K));
165 * Find the size of each group of constraints.
167 nb_cnsts_capacity = links + ((int)pow(2,K)) - flows;
168 nb_cnsts_struct = (int)pow(2,K) - 1;
169 nb_cnsts_positivy = (int)pow(2,K);
172 * The total number of constraints.
174 nb_cnsts = nb_cnsts_capacity + nb_cnsts_struct + nb_cnsts_positivy;
178 * Keep track of which blocks have off diagonal entries.
180 isdiag=(int *)calloc((nb_cnsts+1), sizeof(int));
181 for (i=1; i<=nb_cnsts; i++)
184 C.nblocks = nb_cnsts;
185 C.blocks = (struct blockrec *) calloc((C.nblocks+1),sizeof(struct blockrec));
186 constraints = (struct constraintmatrix *)calloc((nb_var+1),sizeof(struct constraintmatrix));
188 for(i = 1; i <= nb_var; i++){
189 constraints[i].blocks=NULL;
192 a = (double *)calloc(nb_var+1, sizeof(double));
201 * For each constraint block do.
203 for(i = 1; i <= nb_cnsts; i++){
206 * Structured blocks are size 2 and all others are size 1.
208 if(i <= nb_cnsts_struct){
210 fprintf(sdpout,"2 ");
213 fprintf(sdpout,"1 ");
217 * All blocks are matrices.
219 C.blocks[block_num].blockcategory = MATRIX;
220 C.blocks[block_num].blocksize = block_size;
221 C.blocks[block_num].data.mat = (double *)calloc(block_size * block_size, sizeof(double));
226 fprintf(sdpout,"\n");
230 * Creates de objective function array.
232 a = (double *)calloc((nb_var+1), sizeof(double));
234 for(i = 1; i <= nb_var; i++){
236 fprintf(sdpout,"-1 ");
239 fprintf(sdpout,"0 ");
243 fprintf(sdpout,"\n");
247 * Structure contraint blocks.
251 for(k = 1; k <= K; k++){
252 for(i = 1; i <= pow(2,k-1); i++){
253 matno=get_y(k,2*i-1);
254 fprintf(sdpout,"%d %d 1 1 1\n", matno , block_num);
255 addentry(constraints, &C, matno, block_num, 1, 1, 1.0, C.blocks[block_num].blocksize);
258 fprintf(sdpout,"%d %d 2 2 1\n", matno , block_num);
259 addentry(constraints, &C, matno, block_num, 2, 2, 1.0, C.blocks[block_num].blocksize);
262 fprintf(sdpout,"%d %d 1 2 1\n", matno , block_num);
263 addentry(constraints, &C, matno, block_num, 1, 2, 1.0, C.blocks[block_num].blocksize);
266 fprintf(sdpout,"%d %d 2 1 1\n", matno , block_num);
267 addentry(constraints, &C, matno, block_num, 2, 1, 1.0, C.blocks[block_num].blocksize);
269 isdiag[block_num] = 0;