Find minimum consecutives in an optimvar

Question

Julian 2023-8-4

0
链接

此问题的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/2004612-find-minimum-consecutives-in-an-optimvar

编辑： Julian 2023-9-11

采纳的回答： Julian

I try to "find" the minimum consecutives 0 or 1 in an integer optimvar.

Following a "normal logical" array, I would search for it as follows:

A = [0 0 0 1 1 0 0 1 0 1 1 1 0 0 0].';

% Find the position of the 1s

index = find(A);

% Calculate the difference between the zeros and find the indexes at wich a new block starts.

% A new Block starts at the first "index" and where the difference is bigger than 1

iStart = find([1; diff(index) >1]);

% The end of the block is always the index before the start of a new block

iEnd = [iStart(2:end)-1; size(index,1)];

% Calculate the length of the Blocks

onLength = iEnd-iStart+1;

offLength = ([index(iStart); length(A)+1] - [0; index(iEnd(1:end))] -1);

And I wanted to use this to "find" / define the minimum of a optimvar. But unfortunately this does not work, which is why I set the maximum like this:

% Define variables

prob = optimproblem;

n_max_off = 3;

N = 90;

ds_on = optimvar('ds_on', N, 'LowerBound',0, 'UpperBound', 1, 'Type','integer');

prob.Constraints.ds_max_off = optimconstr(N-n_max_off);

% The sum of the maximum +1 must be more the 1

% For more than the maximum, at least one element must be true.

for i = 1:N-n_max_off-1

prob.Constraints.ds_max_off(i) = sum(ds_on(i:i+n_max_off+1)) >= 1;

end

% Compressed code without loop

index = (0:n_max_off) + (1:N-n_max_off).';

prob.Constraints.ds_max_off(1:N-n_max_off) = sum(ds_on(index(1:N-n_max_off,:)),2) >= 1;

But to define the minimum I do not know how I can do it.

In other words:

I want to define a minimum and maximum length of zeros and ones which are my boundary conditions / constraints.

The maximum is not a problem, but to define the minimum length is my problem. So minimum and maximum length are my constraints.

My objective is someting different I left for readability.

1 个评论
显示 -1更早的评论隐藏 -1更早的评论

Julian 2023-9-4

I have found and already implemented a way to formulate the minimum number of a runtime linearly.

From the paper: "A computationally efficient mixed-integer linear formulation for the thermal unit commitment problem"

DOI: 10.1109/TPWRS.2006.876672

I plan to post the solution in the near future.

请先登录，再进行评论。

请先登录，再回答此问题。

Answer 1

Julian 2023-9-7

0
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/2004612-find-minimum-consecutives-in-an-optimvar#answer_1304251

编辑：Julian 2023-9-11

The best solution is to formulate the minimum number of consecutives with a linear approach like in the paper: "A computationally efficient mixed-integer linear formulation for the thermal unit commitment problem" DOI: 10.1109/TPWRS.2006.876672

At first define the variable:

% Define variables

prob = optimproblem;

n_min_off = 4;

n_max_off = 10;

n_min_on = 2;

n_max_on = 3;

N = 90;

I use two optimvars:

ds_on = optimvar('ds_on', N, 'LowerBound',0, 'UpperBound', 1, 'Type','integer');

ds_start = optimvar('ds_start', N, 'LowerBound',0, 'UpperBound', 1, 'Type','integer');

The maximum of the consecutives is like I implemented it in the question:

% Compressed code without loop

index = (0:n_max_off) + (1:N-n_max_off).';

prob.Constraints.ds_max_off = sum(ds_on(index(1:N-n_max_off,:)),2) >= 1;

% the same for maximum on

%...

I search for the start but in the end I musst not forget to give "ds_start" a little weight in my minimization function:

prob.Constraints.ds_start = diff(ds_on) <= ds_start(2:end);

Afterwards I say, after "ds_start" is 1, the following "ds_on"s musst be on too:

for i = 2:N-n_min_on+1:

prob.Constraints.min_off(i) = ds_start(i) * n_min_on - sum(ds_on(i:i+n_min_on-1)) <= 0;

end

% of faster:

index = (1:n_min_on) + (1:N-n_min_on).';

prob.Constraints.min_on = ds_start(2:N-n_min_on+1) * n_min_on - sum(ds_on(index),2) <=0;

And it's very siilar for "min_off":

for i = n_min_off+1:N

prob.Constraints.min_off(i) = ds_start(i) * n_min_on + sum(ds_on(i-n_min_on:i-1)) <= n_min_on;

end

% or faster:

index = (0:n_min_off-1) + (1:N-n_min_off).';

prob.Constraints.min_off = ds_start(1:N-n_min_off) * n_min_off + sum(ds_on(index),2) <= n_min_off;

With this calculation I'm able to define a minimum on and off time for a appliance in an optimization.

I am also able to make it multidemensional if I have more appliances of this kind.

With this workaround it is also possible to have different kinds of "on" values.

0 个评论
显示 -2更早的评论隐藏 -2更早的评论

请先登录，再进行评论。

Answer 2

Matt J 2023-8-4

1
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/2004612-find-minimum-consecutives-in-an-optimvar#answer_1283307

编辑：Matt J 2023-8-4

It's going to be a nonlinear integer objective function, which means the solver it's going to choose is ga. You should save yourself the hassle and just implement the optimization with ga() directly.

15 个评论
显示 13更早的评论隐藏 13更早的评论

Torsten 2023-8-17

编辑：Torsten 2023-8-17

在 MATLAB Online 中打开

Example:

n_max_on = 5;
n_min_off = 3;
N = 10;
prob = optimproblem;
ds_on = optimvar('ds_on', N, 'LowerBound',0, 'UpperBound', 1, 'Type','integer');
[c,~] = fcn2optimexpr(@nonlcon,ds_on,n_max_on,n_min_off);
prob.Constraints.ds_max_on_min_off = c <= 0;
prob.Objective = -sum(ds_on);
opts = optimoptions("ga",Display="none");
x0.ds_on = [1 1 1 1 1 0 0 0 1 1];
show(prob)
  OptimizationProblem : 

	Solve for:
       ds_on
	where:
       ds_on integer

	minimize :
       -ds_on(1) - ds_on(2) - ds_on(3) - ds_on(4) - ds_on(5) - ds_on(6) - ds_on(7) - ds_on(8) - ds_on(9) - ds_on(10)


	subject to ds_max_on_min_off:
       arg_LHS <= zeros(1, 2)

       where:

             [arg_LHS,~] = nonlcon(ds_on, 5, 3);

	variable bounds:
       0 <= ds_on(1)  <= 1
       0 <= ds_on(2)  <= 1
       0 <= ds_on(3)  <= 1
       0 <= ds_on(4)  <= 1
       0 <= ds_on(5)  <= 1
       0 <= ds_on(6)  <= 1
       0 <= ds_on(7)  <= 1
       0 <= ds_on(8)  <= 1
       0 <= ds_on(9)  <= 1
       0 <= ds_on(10) <= 1
[sol,fval,exitflag] = solve(prob,x0,Options=opts)
sol = struct with fields:
    ds_on: [10×1 double]
fval = -4
exitflag = 
    SolverConvergedSuccessfully
[c,~] = nonlcon(sol.ds_on,n_max_on,n_min_off)
c = 1×2
    -1     0
sol.ds_on.'
ans = 1×10
     0     0     0     1     1     1     1     0     0     0
function [c,ceq] = nonlcon(A,n_max_on,n_min_off)
  % Find the position of the 1s
  index = find(A);
  if isempty(index)
    c(1) = Inf;
    c(2) = Inf;
    ceq = [];
  else
    % Calculate the difference between the zeros and find the indexes at wich a new block starts.
    % A new Block starts at the first "index" and where the difference is bigger than 1
    iStart = find([1; diff(index) >1]);
    % The end of the block is always the index before the start of a new block
    iEnd = [iStart(2:end)-1; size(index,1)];
    % Calculate the length of the Blocks
    onLength = iEnd-iStart+1;
    offLength = ([index(iStart); length(A)+1] - [0; index(iEnd(1:end))] -1);
    c(1) = max(onLength) - n_max_on;
    c(2) = -min(offLength) + n_min_off;
    ceq = [];
  end
end

Julian 2023-8-28

编辑：Julian 2023-8-28

I would have a second approach to defining the minima, as I am dissatisfied with the calculation time so far. I was thinking of the binomial formula, so that my values automatically become zero when the derivative is zero, i.e. when the current and subsequent states have not changed.

The formula for minimum on is:

My thought is, if my value changes, the derivative is not equal to 0. Subsequently, the n next elements must all be equal to 0 or 1, and sum to 0 or n_min_on.

The values, which do not interest me, I remove as follows:

If my value does not change, my derivative is equal to 0 => The following elements do not matter.

If my value changes, my derivative is +1 or -1 and to filter out the unwanted, I add - or +1.

As code, I wrote it as follows:

dif = [0; diff(ds_on)];

index = (1:n_min_on) + (1:N-n_min_on).';

prob.Constraints.ds_min_on = optimconstr(N-n_min_on);

prob.Constraints.ds_min_on(2:N-n_min_on+1) = dif(2:N-n_min_on+1).*(dif(2:N-n_min_on+1)+1).*(n_min_on-sum(2*(ds_on(index)-0.5),2)) == 0;

The formulation is a cubic problem (ds_on^3). I thought that Matlab might prefer a cubic equation and calculate it faster, but unfortunately I get the error:

Problems with integer variables and nonlinear equality constraints are not supported.

Do you think it is also possible to convert this equation using "fcn2optimexpr" or it doesn't make sense, because Matlab is faster with the other option?

One speed advantage I thought might be that "ReuseEvaluation" is true

Or it would possibly have an advantage, but rather with a direct "if" query in "fcn2optimexpr" and thus only one query and "linear" function?

Julian 2023-8-28

编辑：Julian 2023-8-28

I changed it to <= instead of == and it is calculating. I hope it will calculate faster, but I have still the question what kind of "problem" is better for Matlab to calculate?

Torsten 2023-8-28

At least it's necessary to either remove integer variables or equality constraints from your code.

请先登录，再进行评论。

Find minimum consecutives in an optimvar

1 个评论
显示 -1更早的评论隐藏 -1更早的评论

采纳的回答

0 个评论
显示 -2更早的评论隐藏 -2更早的评论

更多回答（1 个）

15 个评论
显示 13更早的评论隐藏 13更早的评论

另请参阅

类别

标签

产品

版本

Community Treasure Hunt

Find minimum consecutives in an optimvar

1 个评论 显示 -1更早的评论隐藏 -1更早的评论

采纳的回答

0 个评论 显示 -2更早的评论隐藏 -2更早的评论

更多回答（1 个）

15 个评论 显示 13更早的评论隐藏 13更早的评论

另请参阅

类别

标签

产品

版本

Community Treasure Hunt

1 个评论
显示 -1更早的评论隐藏 -1更早的评论

0 个评论
显示 -2更早的评论隐藏 -2更早的评论

15 个评论
显示 13更早的评论隐藏 13更早的评论