MATLAB Answers


Using intlinprog to Minimize Combinations

Jake Smith さんによって質問されました 2019 年 1 月 7 日
最新アクティビティ Alan Weiss
さんによって コメントされました 2019 年 1 月 7 日
I'm learning how to use intlinprog to solve a minimization problem. I have a series of paths that each connect two waypoints with distance values that need to be combined to minimize the overall distance of a route. 2 paths share a waypoint to make up a route. For example:
%distance for each path
p1 = 10;
p2 = 5;
p3 = 12;
p4 = 8;
%possible route combinations
routes = [p1 p2 0 0; p1 0 p3 0; p1 0 0 p4; 0 p2 p3 0; 0 p2 0 p4; 0 0 p3 p4];
%distance for each route
distance = sum(routes,2);
From the above, it can be seen that p2 & p4 would result in the minimum distance combination (5 + 8 is the smallest distance). I could use a brute force for loop to find the minimum distance, but it's not scalable for larger numbers of paths per route. In an attempt to use intlinprog to find the best combination of paths, I'm not understanding what inputs I should use. Referring to the guidlines here,, I infer that:
f = ones(1,4);
intcon = 4;
A = [];
b = [];
Aeq = routes;
Beq = distance;
intlinprog(f, intcon, A, b, Aeq, Beq)
I expect this:
ans = [0; 1; 0; 1];
But get this:
ans = [1; 1; 1; 1];
I'm sure I'm missing something key here, but I don't know what. How do I get the first ans above?
Thanks in advance!

  0 件のコメント

サインイン to comment.

1 件の回答

Alan Weiss
回答者: Alan Weiss
2019 年 1 月 7 日
編集済み: Alan Weiss
2019 年 1 月 7 日

Your problem formulation is incorrect in several respects. For example, your Aeq and beq arguments ensure that the solution must be ones(4,1) because they mean
p1*x(1) + p2*x(2) = distance(1)
p1*x(1) + p3*x(3) = distance(2)
p1*x(1) + p4*x(4) = distance(3)
p2*x(2) + p3*x(3) = distance(4)
p2*x(2) + p4*x(4) = distance(5)
p3*x(3) + p4*x(4) = distance(6)
Instead, I suggest that you use the problem-based approach. If your data for path lengths is given in a vector p, then you want a binary vector x with the same length as p and with exactly two nonzero entries. So your problem formulation could be the following:
p = [10,5,12,8]; % put your own vector here
x = optimvar('x',length(p),'Type','integer','LowerBound',0,'UpperBound',1); % binary variable
obj = dot(x,p);
prob = optimproblem('Objective',obj);
cons = sum(x) == 2;
prob.Constraints.cons = cons;
[sol,fval] = solve(prob) % this solution gives x(2) = x(4) = 1, as you want
Of course, for this problem you really just need to take the two smallest entries in the p vector. But I hope that my solution gives you an idea of how to formulate such problems.
Alan Weiss
MATLAB mathematical toolbox documentation

  2 件のコメント

Jake Smith 2019 年 1 月 7 日
Thanks for the reply. I'll look into making an optimization variable.
On the other hand, if I were to use intlinprog for this problem, how would I do it? I know it's overkill for this application, but I want to understand the inputs for future use.
Alan Weiss
2019 年 1 月 7 日
A direct translation of my previous solution:
p = [10,5,12,8]; % put your own vector here
L = length(p);
Aeq = ones(1,L);
beq = 2;
intcon = 1:L;
lb = zeros(L,1);
ub = ones(L,1);
[x,fval] = intlinprog(p,intcon,[],[],Aeq,beq,lb,ub)
As you see, the problem-based approach is much easier to understand (and debug).
Alan Weiss
MATLAB mathematical toolbox documentation

サインイン to comment.

Translated by