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 * Modelling the proportional fairness using the Lagrange Optimization
10 * Approach. For a detailed description see:
11 * "ssh://username@scm.gforge.inria.fr/svn/memo/people/pvelho/lagrange/ppf.ps".
14 #include "xbt/sysdep.h"
15 #include "xbt/mallocator.h"
16 #include "maxmin_private.h"
23 #define LAMBDA_STEP 0.01
26 XBT_LOG_NEW_DEFAULT_SUBCATEGORY(surf_lagrange, surf,
27 "Logging specific to SURF (lagrange)");
29 XBT_LOG_NEW_SUBCATEGORY(surf_writelambda, surf,
30 "Generates the lambda.in file. WARNING: the size of this file might be a few GBs.");
32 void lagrange_solve(lmm_system_t sys);
34 void lagrange_solve(lmm_system_t sys)
39 int max_iterations= 1000000;
40 double epsilon_min_error = 0.00001;
41 double overall_error = 1;
42 double sigma_step = LAMBDA_STEP;
43 //double capacity_error=0, bound_error=0;
47 * Variables to manipulate the data structure proposed to model the maxmin
48 * fairness. See docummentation for more details.
50 xbt_swag_t elem_list = NULL;
51 //lmm_element_t elem = NULL;
52 lmm_element_t elem1 = NULL;
55 xbt_swag_t cnst_list = NULL;
56 //lmm_constraint_t cnst = NULL;
57 lmm_constraint_t cnst1 = NULL;
58 //lmm_constraint_t cnst2 = NULL;
61 xbt_swag_t var_list = NULL;
62 //lmm_variable_t var = NULL;
63 lmm_variable_t var1 = NULL;
64 lmm_variable_t var2 = NULL;
71 double lambda_partial=0;
74 FILE *gnuplot_file=NULL;
75 //char print_buf[1024];
76 //char *trace_buf=xbt_malloc0(sizeof(char));
80 DEBUG0("Iterative method configuration snapshot =====>");
81 DEBUG1("#### Maximum number of iterations : %d", max_iterations);
82 DEBUG1("#### Minimum error tolerated : %e", epsilon_min_error);
83 DEBUG1("#### Step : %e", sigma_step);
86 if ( !(sys->modified))
90 * Initialize the var list variable with only the active variables.
91 * Associate an index in the swag variables. Initialize mu.
93 var_list = &(sys->variable_set);
95 xbt_swag_foreach(var1, var_list) {
96 if((var1->bound > 0.0) || (var1->weight <= 0.0)){
97 DEBUG1("#### NOTE var1(%d) is a boundless variable", i);
103 DEBUG2("#### var1(%d)->mu: %e", i, var1->mu);
104 DEBUG2("#### var1(%d)->weight: %e", i, var1->weight);
111 cnst_list=&(sys->active_constraint_set);
112 xbt_swag_foreach(cnst1, cnst_list) {
114 cnst1->new_lambda = 2.0;
115 DEBUG2("#### cnst1(%p)->lambda: %e", cnst1, cnst1->lambda);
118 if(XBT_LOG_ISENABLED(surf_writelambda, xbt_log_priority_debug)) {
119 gnuplot_file = fopen("lambda.in", "w");
120 fprintf(gnuplot_file, "# iteration lambda1 lambda2 lambda3 ... lambdaP\n");
125 * While doesn't reach a minimun error or a number maximum of iterations.
127 while(overall_error > epsilon_min_error && iteration < max_iterations){
130 * Compute the value of ----------- (\lambda^k, \mu^k) this portion
132 * of code depends on function f(x).
134 var_list = &(sys->variable_set);
135 xbt_swag_foreach(var1, var_list) {
137 if((var1->bound > 0) || (var1->weight <=0) ){
138 //for each link with capacity cnsts[i] that uses flow of variable var1 do
139 for(i=0; i<var1->cnsts_number; i++)
140 mu_partial += (var1->cnsts[i].constraint)->lambda;
142 mu_partial = -1.0 / mu_partial + var1->bound;
143 var1->new_mu = var1->mu - sigma_step * mu_partial;
145 if(var1->new_mu < 0){
153 * Compute the value of ------------- (\lambda^k, \mu^k) this portion
155 * of code depends on function f(x).
158 if(XBT_LOG_ISENABLED(surf_writelambda, xbt_log_priority_debug)) {
159 fprintf(gnuplot_file, "\n%d",iteration);
161 xbt_swag_foreach(cnst1, cnst_list) {
166 elem_list = &(cnst1->element_set);
168 xbt_swag_foreach(elem1, elem_list) {
170 var2 = elem1->variable;
172 if(var2->weight<=0) continue;
176 for(i=0; i<var2->cnsts_number; i++){
177 tmp += (var2->cnsts[i].constraint)->lambda;
185 if (tmp==cnst1->lambda)
187 lambda_partial += (-1.0 / tmp);
191 cnst1->new_lambda = LAMBDA_STEP;
193 lambda_partial += cnst1->bound;
194 if(watch_out && (lambda_partial>0)) {
195 /* INFO6("Watch Out (%d) %p! lambda_partial: %e; lambda : %e ; (%e %e) \n",iteration, cnst1, */
196 /* lambda_partial, cnst1->lambda, cnst1->lambda / 2, */
197 /* cnst1->lambda - sigma_step * lambda_partial); */
199 if(cnst1->lambda < 0) WARN2("Value of cnst1->lambda(%p) = %e < 0", cnst1, cnst1->lambda);
200 if((cnst1->lambda - sigma_step * lambda_partial) < 0) WARN1("Value of lambda_new = %e < 0", (cnst1->lambda - sigma_step * lambda_partial));
202 if(cnst1->lambda - sigma_step * lambda_partial < cnst1->lambda / 2)
203 cnst1->new_lambda = cnst1->lambda / 2;
205 cnst1->new_lambda = cnst1->lambda - sigma_step * lambda_partial;
207 cnst1->new_lambda = cnst1->lambda - sigma_step * lambda_partial;
208 if(cnst1->new_lambda < 0){
209 cnst1->new_lambda = 0;
213 if(XBT_LOG_ISENABLED(surf_writelambda, xbt_log_priority_debug)) {
214 fprintf(gnuplot_file, " %e", cnst1->lambda);
221 * Now computes the values of each variable (\rho) based on
222 * the values of \lambda and \mu.
225 xbt_swag_foreach(var1, var_list) {
230 for(i=0; i<var1->cnsts_number; i++){
231 tmp += (var1->cnsts[i].constraint)->lambda;
236 //computes de overall_error
237 if(overall_error < fabs(var1->value - 1.0/tmp)){
238 overall_error = fabs(var1->value - 1.0/tmp);
241 var1->value = 1.0 / tmp;
247 /* Updating lambda's and mu's */
248 xbt_swag_foreach(var1, var_list)
249 if(!((var1->bound > 0.0) || (var1->weight <= 0.0)))
250 var1->mu = var1->new_mu;
253 xbt_swag_foreach(cnst1, cnst_list)
254 cnst1->lambda = cnst1->new_lambda;
260 //verify the KKT property
261 xbt_swag_foreach(cnst1, cnst_list){
263 elem_list = &(cnst1->element_set);
264 xbt_swag_foreach(elem1, elem_list) {
265 var1 = elem1->variable;
266 if(var1->weight<=0) continue;
270 tmp = tmp - cnst1->bound;
273 if(tmp != 0 || cnst1->lambda != 0){
274 WARN4("The link %s(%p) doesn't match the KKT property, value expected (=0) got (lambda=%e) (sum_rho=%e)", (char *)cnst1->id, cnst1, cnst1->lambda, tmp);
280 xbt_swag_foreach(var1, var_list){
281 if(var1->bound <= 0 || var1->weight <= 0) continue;
283 tmp = (var1->value - var1->bound);
286 if(tmp != 0 || var1->mu != 0){
287 WARN4("The flow %s(%p) doesn't match the KKT property, value expected (=0) got (lambda=%e) (sum_rho=%e)", (char *)var1->id, var1, var1->mu, tmp);
295 if(overall_error <= epsilon_min_error){
296 DEBUG1("The method converge in %d iterations.", iteration);
298 WARN1("Method reach %d iterations, which is the maxmimun number of iterations allowed.", iteration);
302 if(XBT_LOG_ISENABLED(surf_writelambda, xbt_log_priority_debug)) {
303 fclose(gnuplot_file);
311 /* * Now computes the values of each variable (\rho) based on */
312 /* * the values of \lambda and \mu. */
314 /* var_list = &(sys->variable_set); */
315 /* xbt_swag_foreach(var1, var_list) { */
317 /* for(i=0; i<var1->cnsts_number; i++){ */
318 /* elem1 = &(var1->cnsts[i]); */
319 /* tmp += (elem1->constraint)->lambda + var1->mu; */
321 /* var1->weight = 1 / tmp; */
323 /* DEBUG2("var1->weight (id=%s) : %e", (char *)var1->id, var1->weight); */