Error : Unable to use a value of type optim.prob​lemdef.Opt​imizationV​ariable as an index.

Hello !

I am working on a problem-based optimization task where I need to assign 4 subtasks to 4 different nodes. My approach involves defining an optimization variable as a vector with integer elements ranging from 1 to 4, each representing the node assigned to a subtask.

Here's a snippet of my current setup:

numSubtasks = 4;
numNodes = 4;
taskAssignmentVector = optimvar('taskAssignmentVector', numSubtasks, 'Type', 'integer', 'LowerBound', 1, 'UpperBound', numSubtasks);

My goal is to reshape this vector into a 4x4 binary assignment matrix within the optimization framework. Each row of this matrix should correspond to a subtask, and each column to a node, with '1' indicating the assignment.

I attempted to implement this by creating a function to generate the assignment matrix based on the vector, but I'm facing challenges in using the optimization variable as an index, leading to errors.

 AssignedMatrix = zeros(numSubtasks, numNodes);
        for s = 1:numSubtasks
          nodeAssigned = taskAssignmentVector(s); % Node assigned for each subtask
           AssignedMatrix(s, nodeAssigned) = 1;
        end

Could you please advise on the best approach to reshape this vector into a matrix form within the problem-based optimization framework? I am looking for a way to link the task assignments in the vector with a binary matrix that I can use in my objective function and constraints.

Thank you for your assistance!

Answer 1

[Matt J]

It sounds like the better approach would be to have the 4x4 binary matrix AssignedMatrix be the fundamental unknown optimization variable.

AssignedMatrix = optimvar('AssignedMatrix', [4,4], 'Type', 'integer', 'LowerBound', 0, 'UpperBound', 0);

Once you've done so, the taskAssignmentVector is easily expressed as a linear expression of the AssignedMatrix:

prob=optimproblem;
prob.Constraints.OneToOne1=sum(AssignedMatrix,1)==1;
prob.Constraints.OneToOne2=sum(AssignedMatrix,2)==1;

taskAssignmentVector=AssignedMatrix*(1:4)';

[Maria]

@Matt J thank u for your answer !

fI have tried implementing the code as per your suggestion, but I encountered the following message:

Intlinprog stopped because no point satisfies the constraints.


ans = 

  struct with fields:

    AssignedMatrix: []

i want to ask if should i use AssignmentMatrix in my objective function then what is the utility of taskAssignmentVector .

Thank you once again for your assistance.

[Matt J]

i want to ask if should i use AssignmentMatrix in my objective function then what is the utility of taskAssignmentVector .

You can still use taskAssignmentVector in your objective function and constraints, if it is more directly useful than AssignmentMatrix. It is simply that you will be using it as an OptimizationExpression rather than an OptimizationVariable.

[Maria]

@Matt J i want just to clarify that I am working on an optimization problem where tasks are assigned to different nodes, and I need to calculate the offloading time for each task based on this assignment. The key challenge is that the maximum offloading time across all tasks must be less than a specified threshold. The offloading time can only be calculated after determining the task-to-node association.

i need to know if i can formulate this problem in MATLAB, especially integrating the dynamic calculation of offloading times based on the task-node association matrix?

Thank you very much!

[Matt J]

Yes, you can.

[Maria]

@Matt J

Thank you, i tried already but I am facing an issue with correctly setting up and utilizing the assignment matrix in the optimization problem. I would like to ensure that my implementation of the assignment matrix and the way it interacts with the calculation of offloading times and the objective function is correct.

%Problem Based optimization 

function [solution, exitflag] = ProblemBasedOptimization()numSubtasks = 4;
numNodes = 4;
assignmentMatrix = optimvar('assignmentMatrix', numSubtasks, numNodes, 'Type', 'integer', 'LowerBound', 0, 'UpperBound', 1);
function maxOffloadingTime = calculateMaxOffloadingTime(taskAssignmentVector)
    Offloading_time_subtask = calculateOffloadingTime(x_UAV, y_UAV, z_UAV,x_positions,y_positions,x_haps,y_haps,z_haps,num_vehicles,numUAVs, Task_assignment, taskAssignmentVector, all_subtasks,reordered_tasks,initial_data_sizes,dependency_matrix,transmission_time,P_tx,P_Haps,f_c, c, eta_LoS_Ls,numRBs,B_RB_aerial,Noise_aerial,B_RB_dl,Noise_dl,G_u_linear,G_h_linear,h_LoS,kB,Ts,min_value,max_value,Fmax,coverageRadius,a,b,eta_NLoS_Ls);
    maxOffloadingTime = max(Offloading_time_subtask(:)); 
end
function satisfactionRate = objectiveFunction(assignmentMatrix, QoS_values)
    maxTime = calculateMaxOffloadingTime(taskAssignmentVector);
    satisfactionRate = (maxTime <= QoS_values); % 1 if constraint is satisfied, 0 otherwise
end
prob = optimproblem('ObjectiveSense', 'maximize');
prob.Objective = objectiveFunction(assignmentMatrix, QoS_values); 
% Add constraints
prob.Constraints.OneToOne1=sum(assignmentMatrix,1)==1;
prob.Constraints.OneToOne2=sum(assignmentMatrix,2)==1;
taskAssignmentVector=assignmentMatrix*(1:4)';

 [sol, fval, exitflag, output] = solve(prob);

if exitflag > 0
    optimalAssignment = solution.assignmentMatrix;
else
    disp('No feasible solution found.');
 end
end

this is the error :

Unrecognized function or variable 'taskAssignmentVector'.

Error in ProblemBasedOptimization/objectiveFunction (line 158)
    maxTime = calculateMaxOffloadingTime(taskAssignmentVector);

[Matt J]

function satisfactionRate = objectiveFunction(assignmentMatrix, QoS_values)

   taskAssignmentVector=AssignedMatrix*(1:4)';

    maxTime = calculateMaxOffloadingTime(taskAssignmentVector);
    satisfactionRate = (maxTime <= QoS_values); % 1 if constraint is satisfied, 0 otherwise
end

[Maria]

@Matt J Thank you for your guidance on using taskAssignmentVector directly in the optimization problem. I have attempted to follow your advice, but I'm encountering an issue when it comes to the calculations within my functions.

When I attempt to use assignmentMatrix in my calculations, it seems that the functions are not recognizing it as a regular matrix but rather as an OptimizationVariable object, and I'm unable to perform the necessary calculations. I'm aware that functions should be set up to work with OptimizationExpression objects, but I'm not sure how to adjust my existing functions to accommodate this.

assignmentMatrix(3, 1) + 2*assignmentMatrix(3, 2) + 3*assignmentMatrix(3, 3) + 4*assignmentMatrix(3, 4) 
assignmentMatrix(2, 1) + 2*assignmentMatrix(2, 2) + 3*assignmentMatrix(2, 3) + 4*assignmentMatrix(2, 4)
assignmentMatrix(3, 1) + 2*assignmentMatrix(3, 2) + 3*assignmentMatrix(3, 3) + 4*assignmentMatrix(3, 4)
assignmentMatrix(4, 1) + 2*assignmentMatrix(4, 2) + 3*assignmentMatrix(4, 3) + 4*assignmentMatrix(4, 4)

For instance, when I pass assignmentMatrix to the calculateMaxOffloadingTime function, I notice that it take the input as optimvar instead of binary matrix

I appreciate any further assistance you can provide.

[Matt J]

If you are invoking nonlinear functions in your objective and constraints, then you need to be using fcn2optimexpr. I believe we had a leisurely discussion about that here,

https://www.mathworks.com/matlabcentral/answers/1902580-how-to-solve-conversion-to-logical-from-optim-problemdef-optimizationequality-is-not-possible?s_tid=srchtitle

[Torsten]

Convert your function to an optimization expression if it has optimization variables (like assignmentMatrix) as inputs:

https://uk.mathworks.com/help/optim/ug/fcn2optimexpr.html

[Maria]

@Matt J yes , but it wasn't the same problem and i tried to follow same steps but there is some issues.

@Torsten thank you for your suggestion.I've attempted to implement the changes, but I'm still encountering the same index out-of-bounds error when solving the problem using the genetic algorithm. The error message is as follows:

Solving problem using ga.
Error using optim.problemdef.OptimizationProblem/solve
Index in position 2 exceeds array bounds. Index must not exceed 3.

This issue seems to arise from the size of the assignmentMatrix not being appropriate within my function. Here's the relevant portion of my modified code for your reference:

function maxOffloadingTime = calculateMaxOffloadingTime(assignmentMatrix)
 
    Offloading_time_subtask = calculateOffloadingTime(x_UAV, y_UAV, z_UAV,x_positions,y_positions,x_haps,y_haps,z_haps,num_vehicles,numUAVs, Task_assignment, assignmentMatrix, all_subtasks,reordered_tasks,initial_data_sizes,dependency_matrix,transmission_time,P_tx,P_Haps,f_c, c, eta_LoS_Ls,numRBs,B_RB_aerial,Noise_aerial,B_RB_dl,Noise_dl,G_u_linear,G_h_linear,h_LoS,kB,Ts,min_value,max_value,Fmax,coverageRadius,a,b,eta_NLoS_Ls);

    maxOffloadingTime = max(Offloading_time_subtask(:)); 
end
maxOffloadingTimeExpr = fcn2optimexpr(@calculateMaxOffloadingTime, assignmentMatrix, 'OutputSize', [1, 1]);
prob.Objective = maxOffloadingTimeExpr;

It seems to be related to how the assignmentMatrix is used within the optimization problem, but I'm not certain how to resolve it.

[Matt J]

It would help if you provided a complete piece of code that we can all run and study, even if it contains a fake, simplified version of low-level routines like calculateOffloadingTime() etc...

(In fact, it would be better if those could be simplified).

[Torsten]

It's necessary to know how "assignmentMatrix" is used in the function "calculateOffloadingTime". From the error message, it can not even be concluded that "assignmentMatrix" is the reason for the error you encounter.

And where do you get all the input parameters to "calculateOffloadingTime" from ? Since you don't pass them to "calculateMaxOffloadingTime", "calculateMaxOffloadingTime" must be a nested function. Is this the case in your code ?

[Maria]

@Matt J @Torsten Thank you for your guidance. I understand the need for a complete code to fully grasp the issue, but unfortunately, it's complex with multiple interconnected functions. However, I can provide a simplified example to illustrate the core problem.

I'm working with an assignment matrix, which is a binary matrix indicating the assignment of tasks to nodes after an original assignment already exist.Here's an example of an original assignment matrix for four tasks:

originalAssignmentMatrix = [
    0   1   0   0;
    0   1   0   0;
    0   1   0   0;
    0   1   0   0 ];

Each row represents a task, and each column represents a node. A '1' indicates that the task is assigned to that node. The constraint is that each task must be assigned to exactly one node, meaning the sum across each row should be 1.

The issue arises with the assignment matrix, which is derived from an optimization variable. The assignment matrix sometimes violates this constraint, assigning a task to multiple nodes or no nodes at all. For example, I get an error for a task assigned to multiple nodes:

original_node: 2, assignment_node: 1 2 3 4

But the function expecting this matrix requires exactly one node per task for its calculations.

I've tried implementing constraints to ensure that each task is assigned to only one node, but I'm still encountering issues with the dimension size and receiving errors related to this.

Could you please provide guidance on how to enforce this constraint properly within the optimization problem so that the updated assignment matrix always adheres to this one-node-per-task rule?

[Matt J]

But the function expecting this matrix requires exactly one node per task for its calculations.

Modify that function, so that if the requirement is not satisfied, the function bails out with an appropriate value.

[Maria]

Thank you for your suggestion to modify the functions. I'd like to clarify that all my functions crucially depend on the 'assignmentMatrix' being a binary variable matrix. Each function performs comparisons and calculations based on this matrix.

My main issue is ensuring that the 'assignmentMatrix' only takes one value (either 0 or 1) in each position at any given time. Specifically, I need each task (row in the matrix) to be assigned to exactly one node (column in the matrix) .

I need to ensure that during the optimization, the matrix respects this binary (0 or 1) and unique assignment constraint.

Thank you for your time and assistance.

[Matt J]

My main issue is ensuring that the 'assignmentMatrix' only takes one value (either 0 or 1) in each position at any given time. Specifically, I need each task (row in the matrix) to be assigned to exactly one node (column in the matrix) .

Yes, you told us that, but I'm telling you you need to change that. Wrap your functions, if need be, with an if statement or an outer function that tests the 1 node-per-task constraint. If it is not satisfied, bail out of the routine with a value of inf.

[Torsten]

My main issue is ensuring that the 'assignmentMatrix' only takes one value (either 0 or 1) in each position at any given time. Specifically, I need each task (row in the matrix) to be assigned to exactly one node (column in the matrix) .

If I understand you correctly, you start with a feasible assignment matrix, define its entries as integers bounded by 0 and 1 and impose the constraint that all the rows sum to 1, but you still get infeasible assignment matrices during the solution process ?

[Matt J]

but you still get infeasible assignment matrices during the solution process ?

That's not surprising. With most of the solvers, linear equality constraints (except for bounds) are not satisfied at all iterations.

[Torsten]

Even for discrete variables and discrete constraints ? I hoped it might not be the case then ...

[Maria]

@Matt J @Torsten I've encountered difficulties while trying to solve my optimization problem initially with problem-based optimization techniques. After restructuring all my functions to accommodate problem-based optimization without success, I decided to transition to a solver-based approach using the Genetic Algorithm (GA).

I managed to solve the problem for a single user with four tasks. However, when I increased the number of users, I couldn't find any feasible solution using GA. Below is a brief outline of the code that works for one user and my attempt to scale it up for multiple users.

When I expanded the code to handle multiple users, I ensured that my fitness function and constraints were modified accordingly. Despite these changes, the GA doesn't seem to find a solution.

• For a single user, the GA finds a solution quickly.
• For multiple users, GA runs without finding a feasible solution.

numSubtasks = 4;
numNodes = 4; 
numGenes = numSubtasks * numNodes * num_users; 

% Lower and upper bounds for the representation
lb = zeros(1, numGenes);
ub = ones(1, numGenes);

function fitness = myFitnessFunction(chromosome)
    % Reshape chromosome into a matrix to represent task assignments
     assignmentMatrix = reshape(chromosome, [numSubtasks, numNodes, num_users]);
    
    % Calculate offloading time and satisfaction
    Offloading_time_subtask = calculateOffloadingTime(x_UAV, y_UAV, z_UAV,x_positions,y_positions,x_haps,y_haps,z_haps,num_vehicles,numUAVs, Task_assignment, assignmentMatrix, all_subtasks,reordered_tasks,initial_data_sizes,dependency_matrix,transmission_time,P_tx,P_Haps,f_c, c, eta_LoS_Ls,numRBs,B_RB_aerial,Noise_aerial,B_RB_dl,Noise_dl,G_u_linear,G_h_linear,h_LoS,kB,Ts,min_value,max_value,Fmax,coverageRadius,a,b,eta_NLoS_Ls); % Add the rest of your parameters
    Satisfaction_variable = computeSR(num_vehicles, numUAVs, Offloading_time_subtask, QoS_values);
    [E_totale] = Calculate_Total_Energy_Consumption(x_UAV, y_UAV, z_UAV,x_positions,y_positions,x_haps,y_haps,z_haps,num_vehicles,numUAVs, Task_assignment, assignmentMatrix, all_subtasks,reordered_tasks,initial_data_sizes,dependency_matrix,transmission_time,P_tx,P_Haps,f_c, c, eta_LoS_Ls,numRBs,B_RB_aerial,Noise_aerial,B_RB_dl,Noise_dl,G_u_linear,G_h_linear,h_LoS,kB,Ts,min_value,max_value,Fmax,coverageRadius,a,b,eta_NLoS_Ls,total_time);
    % Calculate objectives
    objective1 = MySatisfactionRate(Satisfaction_variable, reordered_tasks);
    objective2 = Compute_Remaining_Energy(E_max, E_HAPS, E_totale);
    
    % Calculate the fitness
    fitness = w1 * objective1 + w2 * objective2;
end

    function [cn, ceq] = nonlcon(chromosome)
    % Reshape chromosome into a matrix to represent task assignments
      assignmentMatrix = reshape(chromosome, [numSubtasks, numNodes, num_users]);
    
    % Calculate the maximum offloading time
    Offloading_time_subtask = calculateOffloadingTime(x_UAV, y_UAV, z_UAV,x_positions,y_positions,x_haps,y_haps,z_haps,num_vehicles,numUAVs, Task_assignment, assignmentMatrix, all_subtasks,reordered_tasks,initial_data_sizes,dependency_matrix,transmission_time,P_tx,P_Haps,f_c, c, eta_LoS_Ls,numRBs,B_RB_aerial,Noise_aerial,B_RB_dl,Noise_dl,G_u_linear,G_h_linear,h_LoS,kB,Ts,min_value,max_value,Fmax,coverageRadius,a,b,eta_NLoS_Ls); % Add the rest of your parameters
    maxOffloadingTime = max(Offloading_time_subtask(:));
    [E_totale] = Calculate_Total_Energy_Consumption(x_UAV, y_UAV, z_UAV,x_positions,y_positions,x_haps,y_haps,z_haps,num_vehicles,numUAVs, Task_assignment, assignmentMatrix, all_subtasks,reordered_tasks,initial_data_sizes,dependency_matrix,transmission_time,P_tx,P_Haps,f_c, c, eta_LoS_Ls,numRBs,B_RB_aerial,Noise_aerial,B_RB_dl,Noise_dl,G_u_linear,G_h_linear,h_LoS,kB,Ts,min_value,max_value,Fmax,coverageRadius,a,b,eta_NLoS_Ls,total_time);

    % Nonlinear inequality constraints (c <= 0)
    c1 = maxOffloadingTime - QoS_values; % Assuming QoS_values is a scalar
    c2 =  E_totale - E_max_totale; 

    c1 = c1(:);
    c2 = c2(:);
    % Combine all inequality constraints into one vector
    cn = [c1; c2];
    % Nonlinear equality constraints (ceq == 0)
    ceq = sum(assignmentMatrix, 2) - 1;
    cn = real(cn);
    ceq = real(ceq);
end

% Create an initial population that adheres to the constraint that each subtask is assigned to one node

initialPopulation = zeros(100, numGenes);
for i = 1:100
    chromosome = zeros(1, numGenes);
    for v = 1:num_vehicles
        for j = 1:numSubtasks
            node = randi(numNodes);
            chromosome((v-1)*numSubtasks*numNodes + (j-1)*numNodes + node) = 1;
        end
    end
    initialPopulation(i, :) = chromosome;
end

% GA options
options = optimoptions('ga', ...
    'PopulationType', 'doubleVector', ...
    'PopulationSize', 100, ...
    'InitialPopulationMatrix', initialPopulation, ...
    'MaxGenerations', 100, ...
    'CrossoverFraction', 0.7, ...
    'EliteCount', 5, ...
    'FunctionTolerance', 1e-8, ...
    'MutationFcn', {@mutationuniform, 0.05}, ...
    'CrossoverFcn', @crossoverscattered, ...
    'NonlinearConstraintAlgorithm', 'penalty', ...
    'Display', 'iter');

[bestChromosome, bestFitness, exitflag, output] = ga(@myFitnessFunction, numGenes, [], [], [], [], lb, ub, @nonlcon, options);

% Check the results
if exitflag > 0
    bestAssignmentMatrix = reshape(bestChromosome, [numSubtasks, numNodes]);
    disp('Best Assignment Matrix:');
    disp(bestAssignmentMatrix);
    disp(['Best Fitness Value: ', num2str(bestFitness)]);
else
    disp('No feasible solution found.');
end
end

I am looking for recommendations on faster solver alternatives that can handle the increased complexity efficiently. Would you suggest any specific solver or MATLAB function that is known for faster performance on similar optimization problems?

[Matt J]

Your ceq is in fact a linear constraint, and should be implemented using the Aeq,beq input arguments. The problems you describe might diminish if you do so.

[Torsten]

[bestChromosome, bestFitness, exitflag, output] = ga(@myFitnessFunction, numGenes, [], [], [], [], lb, ub, @nonlcon, options);

It's strange that you don't call "ga" with an intcon array since your assignmentMatrix variables are integers.

[Matt J]

It's strange that you don't call "ga" with an intcon array since your assignmentMatrix variables are integers.

ga does not allow intcon to be used when equality constraints are present.

[Torsten]

So implementing the equality constraints for the elements of "assignmentMatrix" in Aeq and beq as you suggested then allows using the intcon array for them in the call to "ga" ?

[Maria]

@Matt J @Torsten Following up your suggestions, I have attempted to use linear equality constraints (Aeq and Beq) to maintain a binary matrix in my genetic algorithm. Despite this, I still encounter issues with the assignment matrix not remaining binary when 'PopulationType' is set to 'doubleVector'. It seems that the algorithm still provides non-binary solutions, which are not feasible for my problem setup.

for i = 1:numSubtasks
    Aeq(i, (i-1)*numNodes + (1:numNodes)) = 1;
end
beq = ones(numSubtasks, 1);

when I use 'bitString', GA ignores the nonlinear constraints entirely, as per the documentation: 'ga does not enforce nonlinear constraints to be satisfied when the PopulationType option is set to 'bitString' or 'custom'.'

I've tried to enforce binary constraints by rounding values in a custom mutation function, but I'm still struggling with the algorithm respecting my constraints.

[Torsten]

The variable positions in the big vector of unknowns where the variables of the assignmentMatrix are located have to be reported to "ga" in the array "intcon" (2nd last input array in the call to "ga").

Further at the positions where the variables for the assignmentMatrix are located, the vectors lb and ub for the lower and upper bounds on the variables have to be set to 0 and 1, respectively.

[Maria]

@Torsten I have attached all the relevant functions to my original post. The reason I'm sharing these is that I've been unable to resolve the problem on my own despite several attempts.

I'm not entirely sure where the issue in my code lies, which is why I included all the function files.

All functions are in calculateOffloadingTime_TEST, and MatlabData contains all inputs before Genetic Algorithm.

I truly appreciate your time and any insights you might offer to help solve this issue.

[Torsten]

Sorry, but I won't dive into your code to search for technical errors and/or errors in terms of the problem background.

The above changes (use of "intcon" and defining "lb" and "ub" appropriately) should be easy to implement and are necessary to work with assignmentMatrix as a binary matrix. If the code does not work as expected thereafter, please tell us the error message or an explicit description of the problem you encounter.

[Maria]

Thank you for your guidance regarding the use of "intcon" and defining "lb" and "ub". I've implemented these changes as you suggested. To clarify, the reason I provided the full code was in response to @Matt J advice, as he was unsure where the issue might originate.

Regarding the error with the results: after implementing the changes with "intcon", I didn't encounter a technical error in the traditional sense. However, the outcome was not as expected. Instead of receiving a fitness function value, the result was a penalty. This leads me to believe there might be a conceptual or implementation issue with how the optimization is set up or executed.

I understand the limitations in diving into the full code.Thank you very much.

[Torsten]

Is it really necessary to use "ga" to solve your problem ? I remember from your former questions that it was possible to use "intlinprog" for a solution. Is it impossible to handle your inequality constraint(s) differently ?

[Maria]

Thank you for your continued guidance. Initially, I did attempt to use "intlinprog" for solving the problem. However, I encountered challenges in handling the inequality constraints effectively within that framework.

Given these difficulties, I decided to explore the use of a genetic algorithm ("ga") as an alternative approach, hoping it might offer a more flexible way to address the constraints of my problem. Unfortunately, this switch also hasn't yielded the results I was hoping for.

I am open to revisiting the "intlinprog" approach if there are ways to better handle the inequality constraints.

[Torsten]

There are some unmotivated lines of code outside functions in your m-file "calculateOffloadingTime_Test.m".

required_cycles = randi([min_value, max_value], num_vehicles, N);

completion_time = t_completion_dep;

uplink_time_up  = Queue_times + New_uplink_time;

completion_time_up = t_completion_dep_updated  + t_completion_indep_updated;

Offloading_time_subtask = Downlink_time + completion_time;

Total_energy_consumption = squeeze(sum(sum(Energy_Total_UAV, 1, 'omitnan'), 3, 'omitnan'));
% Total energy consumed by every UAV
E_totale = sum(Total_energy_consumption) + Total_HAPS_energy_consumption ;

are not part of functions and appear somewhere in between. Could you make the necessary changes so that the code is correct and can be executed ?

[Maria]

@Torsten Thank you for your feedback on the "calculateOffloadingTime_Test.m" file. To clarify, the main function offloadingTimeTest is the primary focus of the script, and all subsequent functions are indeed related to it and necessary for its operation.

The lines you referred to are intended to display results and do not require encapsulation within a function. However, I realize now that I mistakenly repeated these lines, which may have caused confusion. They are not essential for the main function's execution and were included inadvertently.

I already remove the redundant lines to clear up any misunderstandings and ensure the script is more streamlined and focused on the main function. I appreciate your attention to detail and your assistance in refining the code.

[Matt J]

So implementing the equality constraints for the elements of "assignmentMatrix" in Aeq and beq as you suggested then allows using the intcon array for them in the call to "ga" ?

In recent Matlab, yes. In older versions, no equality constraints are supported, even linear ones, when intcon is used. The posting did not specify the Matlab release we are talking about, so I don't know what would be applicable here.

[Maria]

@Matt J I should have mentioned earlier – I am using MATLAB R2023a .

Given that I'm working with a recent version, it seems I can utilize equality constraints even when specifying integer constraints in my optimization problem.

[Matt J]

OK, well regardless, Torsten is right that you should formulate this with intlinprog if you can and, judging by the code output in your first comment, it looks like it can be. ga may make it easy for you to express your constraints with flexibility and comfort, but as you've seen, ga is a much less efficient and reliable solver than intlinprog, when the latter applies.

[Maria]

I have indeed tried various modifications with intlinprog to address my problem. However, I've consistently encountered a significant issue: the algorithm does not seem to complete its execution even after a considerable amount of time. It appears to be stuck in a loop, or at least behaving like it, which has prevented me from obtaining any results.

This persistent issue with intlinprog was one of the reasons I explored using ga, despite its relative inefficiency. I hoped that the flexibility in expressing constraints with ga might offer a different avenue to find a solution. Unfortunately, as you've seen, this approach also has its drawbacks.

[Torsten]

If you include your optimization model and we are able to understand the essence of it without too much effort and you explain where you see problems using "intlinprog", we might be able to comment.

See it as if you make a power point presentation of your work (I guess this point will soon be reached also for you). The audience doesn't want to be bored by details, but only wants to digest the essence of the model and the problems you encounter.

[Maria]

i want to inform you that my problem was solved by GA.However, the solutions I'm getting are not optimal, and I suspect the issue may lie in the way I have defined my fitness function.

The goal of my fitness function is to maximize the 'satisfaction variable' while ensuring that the 'offloading time' for tasks does not exceed a certain QoS threshold. However, the current implementation seems to be producing suboptimal solutions.

Here's a simplified version of my fitness function:

function fitness = myFitnessFunction(x)
     %reshape
    assignmentMatrix = reshape(x, [numSubtasks, numNodes, num_vehicles]);
    assignmentMatrix = permute(assignmentMatrix, [2, 1, 3]);
     % Initialize satisfaction sum
      Satisfaction_variable = zeros(num_vehicles, 1);
    % Loop through each vehicle
      [Offloading_time_subtask,E_totale] = calculateOffloadingTime(...); 
      maxOffloadingTimes = zeros(1, num_vehicles); 
% Loop through each vehicle to find the maximum offloading time
for v = 1:num_vehicles
    % Extract the matrix for the current vehicle
    vehicleMatrix = Offloading_time_subtask(:, :, v);
    % Find the maximum offloading time for this vehicle
    maxOffloadingTimes(v) = max(vehicleMatrix(:)); 
    if maxOffloadingTimes(v) <= QoS_values(v)
        Satisfaction_variable(v) = 1;
    else
        Satisfaction_variable(v) = 0;
    end
       totalSatisfaction = sum (Satisfaction_variable,"all") /sum(Tasks,"all");    
end
     fitness = totalSatisfaction;
 end

I would greatly appreciate any suggestions on how to improve my fitness function to get more optimal results.

[Matt J]

If you are trying to maximize totalSatisfaction, you would need to have,

fitness = -totalSatisfaction;

[Maria]

I've already done it, but a slight change occurred, so I thought I'd modify the fitness function.

[Matt J]

I would recommend an alternative objective function. It is only an approximation of the original, but it is more continuous and therefore, I predict, easier to optimize.

function fitness = myFitnessFunction(x)
     %reshape
    assignmentMatrix = reshape(x, [numSubtasks, numNodes, num_vehicles]);
    assignmentMatrix = permute(assignmentMatrix, [2, 1, 3]);

    % Loop through each vehicle
      [Offloading_time_subtask,E_totale] = calculateOffloadingTime(...); 
          
      maxOffloadingTimes=max(Offloading_time_subtask,[],[1,2]);
      
      fitness= sum(  max( QoS_values(:) - maxOffloadingTimes(:), 0)   );

 end

[Maria]

@Matt J Thank you for your suggestions. I've implemented the genetic algorithm with a penalty-based fitness function, and I'm observing some unexpected behavior. The output is showing a 'Best' value that seems to represent the penalty rather than the fitness.

I'm wondering if this behavior is due to the constraint handling within my fitness function. Should I explicitly define this constraint in a separate nonlinear constraint function, even though it's already incorporated as a

condition within the fitness function?

[Matt J]

The output is showing a 'Best' value that seems to represent the penalty rather than the fitness.

If the optimal fitness is zero, that would make sense!

[Maria]

@Matt J Thank you for your insights. I understand that the 'Best' value in the output could be related to the penalty rather than the fitness itself. However, my intention is to maximize the satisfaction rate across all vehicles, which I expect to be a value between 0 and 1. This rate should ideally approach 1 if the QoS constraints are satisfied for all vehicles.

Given this objective, I am a bit puzzled by the results showing a 'Best' penalty value instead of a fitness rate. I would anticipate the final output to be a satisfaction rate that reflects the proportion of vehicles for which the QoS constraints are met, rather than a penalty value.

[Matt J]

Well, you could write your own OutputFcn or PlotFcn to suit the display to your liking.

[Torsten]

Or you can compute it after you got the results from "ga".

[Maria]

@Matt J @Torsten the value of the fitness function remains the same even when I use your suggestions, I don't understand why it can't explore more solutions to give best result.

[Torsten]

I don't know how "ga" works - so I can't give advice here.

Does the solution returned satisfy the constraints ? Is it improved in comparison to your initial guess (if you supplied any) ?

[Maria]

@Torsten it was a little bit improved, but still not suboptimal as the GA solutions :(

[Torsten]

I meant the solutions you got in general. Does the solution returned satisfy the constraints ? Is it improved in comparison to your initial guess (if you supplied any) ?

Do you start ga with a feasible solution ? Or is it not possible in ga to supply initial values for the solution vector ?

[Maria]

@Torsten yes,I have implemented the Genetic Algorithm with an initial population that already represents a good solution to my problem. However, despite this, the GA does not seem to improve upon this initial solution. My expectation was that GA would explore and find better solutions, starting from this initial state. Could there be a reason why the algorithm isn't effectively exploring or optimizing beyond the initial population? Is it possible that my fitness function or constraints are limiting the exploration of the solution space?

[Matt J]

I, for one, do not understand what the "Log Absolute Change" plot is plotting. It would be easier to understand if we could just see the Best Fitness value plotted from one generation to the next.

[Maria]

@Matt J i've used this

https://www.mathworks.com/help/gads/creating-a-custom-plot-function.html

[Matt J]

Then I don't know why you think the fitness function remains the same. The plot shows improvement at every step.

[Maria]

@Matt J yeah i know but I’ve noticed that the fitness function is returning values greater than 1, which doesn’t align with the expected range for a satisfaction rate.

[Matt J]

But we changed your objective function. It no longer has that property.

[Torsten]

@Matt J

I don't see why the fitness value returned by

fitness= sum(  max( QoS_values(:) - maxOffloadingTimes(:), 0)   );

is normalized between 0 and 1.

The totalSatisfaction value was, I think.

[Matt J]

But, you could write a PlotFcn that plots both the original fitness function and my version together, so you can see how well they correlate...

[Maria]

@Matt J @Torsten Hello!

after extensive testing and parameter tuning with GA, the results were consistently not good. In search of better solutions, I shifted to problem-based optimization. I used ILP approach, i decided to start with an initial assignment that had previously shown promising results. However, I've been surprised to find that the solutions from ILP are inferior to this initial assignment, raising concerns about the efficacy of both GA and ILP for my problem.

numSubtasks = 4;
numNodes = 4; 

% Binary association matrix A where ak,n = 1 means subtask k is offloaded to node n
A = optimvar('A', numSubtasks, numNodes,num_vehicles, 'Type', 'integer', 'LowerBound', 0, 'UpperBound', 1);
% Satisfaction variable (binary)
satisfaction = optimvar('satisfaction', 1,num_vehicles, 'Type', 'integer', 'LowerBound', 0, 'UpperBound', 1);

% Constraint: Each subtask is offloaded to exactly one node
% Use indexed variables for constraints

initialAssignment = My_initial_assignment;

% Loop variables
maxIterations = 100; % Maximum number of iterations
tolerance = 1e-03 ; % Tolerance for the stopping criterion

for iter = 1:maxIterations

[Offloading_time_subtask,Total_energy_consumption,E_ex] = calculateOffloadingTime(N,..initialAssignment,...)

  % Define a new optimization problem
    prob = optimproblem('ObjectiveSense', 'maximize');
    prob.Objective = sum(satisfaction);

% Constraint: Each subtask is offloaded to exactly one node

for v = 1:num_vehicles
    for k = 1:numSubtasks
        % sum over the third dimension (nodes) for a specific vehicle v and subtask k
         prob.Constraints.(['OneNodeForSubtask' num2str(k) 'Vehicle' num2str(v)]) = sum(A(k, :, v), 'all') == 1;
    end
end
for v = 1:num_vehicles
    vehicleMatrix = Offloading_time_subtask(:, :, v);
maxOffloadingTime = max(vehicleMatrix(:)); 
prob.Constraints.(['SatisfactionVehicle' num2str(v)]) = satisfaction(v) == (maxOffloadingTime <= QoS_values(v));
end
 % Solve the optimization problem
 show(prob);
    [sol, fval, exitflag, output] = solve(prob);
    newAssignment = reshape([sol.A], size(initialAssignment));
 % Check for convergence
    if norm(newAssignment - initialAssignment, 'fro') < tolerance
        break;
    end
    
    % Update the assignment for the next iteration
    initialAssignment = newAssignment;
end

end

[Matt J]

Does the cost function decrease at all?

[Maria]

yes, it was less than other non-optimized solutions

[Matt J]

Then, if the cost function has improved, it cannot be correct to say " the solutions from ILP are inferior to this initial assignment".

[Maria]

it didn't improve, i start to know the problem, i'm trying to know the association then i calculate the offloading time, but for an optimization method the offloading time can be precalculated or approximated without knowing the exact assignment.

[Matt J]

I'll ask again, did the cost function decrease? If so, it improved.

[Maria]

The cost function here is just the satisfaction rate, yes it decrease

[Matt J]

So, when you say it didn't improve, you're talking about something else besides the minimization.

[Maria]

I'm talking about the result just for the satisfaction rate it didn't improve compared with other solutions, I thought that with optimization I will get more satisfied tasks but I get less.

[Matt J]

Two remarks,

(1) You are not using my alternative objective function. I recommended that function because it is continuous and might be easier to optimize.

(2) Your call to solve() does not specify an initialAssignment as an initial point. Therefore, the optimization does not know what it is supposed to try to improve upon.