Hi everybody,
After solving the min(a,b) problem, I have found another issue with
the formalization. I attach the code so you can test it. The current
scenario is:
- A set of elements and a set of possible types.
- Each type has an associated bandwidth so the bandwidth of each
element must be the bandwidth of its type.
- Minimum and maximum thresholds for the number of elements in the
system per type. Some elements may not be used.
- The objective is to minimize the number of elements used in the
system. Right now, it is only the number of elements but in a future it
will contain the cost associated with the work performed per element.
The problem is associated with assigning bandwidth to elements. It
seems that the solver has problems when I include equations such as:
s.t. available_bandwidth_on_elements {e in Elements}: bandwidth[e] ==
sum{t in Type} (elementType[e, t] * bandwidth_per_type[t]);
If I use the equal, the solver introduces more elements than
expected from the minimum threshold. If I change to greater or equal,
the solver puts non-zero values in the bandwidth of unused elements.
Any idea on how to model this type of assignations? The bandwidth
variable is not part of the objective function, but I need these type
of auxiliar variables to create future constraints in the model. Let's
say I want to calculate the minimum number of elements such as a
multicast message arrives on time to every element in the system and
the total work is performed using the mimimum number of elements.
Regards,
Daniel
#
# Linear programming model for solving the available bandwidth on the system.
# @author: dhiguero
#
#set Elements := {'e1', 'e2', 'e3', 'e4', 'e5', 'e6'};
set Elements := {'e1', 'e2', 'e3', 'e4'};
set Type := {'A', 'B'};
param min_type_A := 1;
param min_type_B := 1;
param max_type_A := 2;
param max_type_B := 2;
param Ma := 90;
param Mb := 90;
param MaxBandwidth := 100;
param element_cost_per_type {t in Type};
param bandwidth_per_type {t in Type};
var min_bandwidth {source in Elements, dest in Elements}, binary;
var elementType {e in Elements, t in Type}, binary;
var bandwidth {e in Elements}, >= 0;
var bandwidth_ij {source in Elements, dest in Elements}, >= 0;
minimize total_element_cost: (sum{e in Elements, t in Type} elementType[e, t]);
###############################################################################
# 1.- Constraints regarding minimum number of elements of each type.
###############################################################################
s.t. oneTypePerElement{e in Elements} : sum{t in Type} elementType[e, t] <= 1;
s.t. checkMinTypeA: sum {e in Elements} elementType[e, 'A'] >= min_type_A;
s.t. checkMinTypeB: sum {e in Elements} elementType[e, 'B'] >= min_type_B;
s.t. checkMaxTypeA: sum {e in Elements} elementType[e, 'A'] <= max_type_A;
s.t. checkMaxTypeB: sum {e in Elements} elementType[e, 'B'] <= max_type_B;
###############################################################################
# 2.- Bandwidth availability between elements.
###############################################################################
s.t. available_bandwidth_on_elements {e in Elements}: bandwidth[e] == sum{t in
Type} (elementType[e, t] * bandwidth_per_type[t]);
/* Restrictions suggested by Andrew Makhorin */
s.t. bandwidth_limit_by_source {source in Elements, dest in Elements} :
bandwidth_ij[source, dest] <= bandwidth[source];
s.t. bandwidth_limit_by_target {source in Elements, dest in Elements} :
bandwidth_ij[source, dest] <= bandwidth[dest];
/* Option suggested by Michael Hennebry */
s.t. eq1 {source in Elements, dest in Elements}: bandwidth_ij[source, dest] >=
bandwidth[source] - (Ma*min_bandwidth[source, dest]);
s.t. eq2 {source in Elements, dest in Elements}: bandwidth_ij[source, dest] >=
bandwidth[dest] - (Mb*(1-min_bandwidth[source, dest]));
/* Upper limit in c = min (a,b) -> c + c <= a + b */
s.t. eq3 {source in Elements, dest in Elements}: bandwidth_ij[source, dest] +
bandwidth_ij[source, dest] <= bandwidth[source] + bandwidth[dest];
###############################################################################
/*
Solve the problem and show the results.
*/
###############################################################################
solve;
printf "\nType Assignment\n";
printf
"=======================================================================\n";
for {t in Type} {
printf "\t%s", t;
}
printf "\n";
for { e in Elements} {
printf "%s -", e;
for{t in Type}{
printf "\t%d", elementType[e, t];
}
printf "\n";
}
printf "---------------------------------\n";
printf "BW";
for { t in Type } {
printf "\t%d", bandwidth_per_type[t];
}
printf "\n\nAvailable Bandwidth on each element\n";
printf
"=======================================================================\n";
for {e in Elements}{
printf "%s\t%d\n", e, bandwidth[e];
}
printf "\nAvailable Bandwidth between elements\n";
printf
"=======================================================================\n";
for {e in Elements}{
printf "\t%s", e;
}printf "\n";
for {source in Elements}{
printf "%s", source;
for {dest in Elements}{
printf "\t%d", bandwidth_ij[source, dest];
}
printf "\n";
}printf "\n";
printf "\nDetailed result\n";
printf
"=======================================================================\n";
printf "Number elements: %d\n", sum{e in Elements, t in Type} elementType[e, t];
printf "Elements cost: %d\n", (sum{e in Elements, t in Type} elementType[e, t]
* element_cost_per_type[t]);
data;
param element_cost_per_type := A 15
B 10;
param bandwidth_per_type := A 100
B 50;
end;
_______________________________________________
Help-glpk mailing list
[email protected]
http://lists.gnu.org/mailman/listinfo/help-glpk
