How to get intlinprog to stop when the answer is good enough?

조회 수: 1 (최근 30일)
Jonathan
Jonathan 2020년 3월 28일
댓글: Alan Weiss 2020년 3월 31일
The code below finds an maximum independent set of the graph whose adjacency matrix is A. I would like to pass an option to intlinprog that says stop and return an answer if you get an objective value of -5 or less (meaning an independent set of size 5 or more has been found). This should be much more efficient than finding an independent set of maximum size.
If there is no option to pass to intlinprog that can accomplish my goal, then is there another approach that will?
n = 20;
A = rand(n, n) < 0.1;
A = A | A.';
[r, c] = find(A);
m = numel(r);
B = zeros(m, n);
for eI = 1 : m
B(eI, [r(eI), c(eI)]) = 1;
end
b = ones(m, 1);
c = -ones(n, 1);
% min cost.' * x subject to A * x <= b, x(i) is 0 or 1 for all i.
lb = zeros(n, 1);
ub = lb + 1;
intvars = 1 : n;
options = optimoptions('intlinprog','Display','off');
[x, fval, exitflag, output] = intlinprog(c, intvars, B, b, [], [], lb, ub, options);

채택된 답변

Alan Weiss
Alan Weiss 2020년 3월 29일
You can create an intlinprog output function to stop the optimizaiton when the objective function value goes below a set limit such as -5. Ensure that the phase is not 'rootlp' when you check the objective function value.
Alan Weiss
MATLAB mathematical toolbox documentation
  댓글 수: 2
Jonathan
Jonathan 2020년 3월 30일
Alan,
Thank you; this does what I was looking for.
Since you are part of the documentation team, I will share why I did not look at this option in the first place. The documentation for the OutputFcn option for intlinprog states the following.
"Specify one or more functions that an optimization function calls at events as 'savemilpsolutions', a function handle, or a cell array of function handles. For custom output functions, pass function handles.
  • 'savemilpsolutions' collects the integer-feasible points in the xIntSol matrix in your workspace, where each column is one integer feasible point.
For information on writing a custom output function, see intlinprog Output Function and Plot Function Syntax."
This suggested to me that the OutputFcn option was for storing feasible solutions and such, not for exiting early. I recommend updating the documentation to highlight the versatility of this option.
Kind regards,
Jonathan
Alan Weiss
Alan Weiss 2020년 3월 31일
Thank you for the suggestion. I will consider putting this in the next documentation release.
Alan Weiss
MATLAB mathematical toolbox documentation

댓글을 달려면 로그인하십시오.

추가 답변 (0개)

태그

제품


릴리스

R2019b

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by