"OR" constraints lsqlin

3 次查看（过去 30 天）
Jacob Tracy
Jacob Tracy 2018-8-15
评论： Walter Roberson 2018-8-16
Hello all, I'm using lsqlin to solve a graph (node-link) model, where the decision variables are the quantities in the links. I am using lsqlin() to minimize difference between the simulated flow balance in each node and a constant value generated from a function. Only problem I'm having is that I want to model the idea that the amount leaving a node is equal to the supply to that node, minus the demand; or zero otherwise (see attached screenshot). Basically, if there is less supply than demand, the nodes are still emitting outputs and if I say that:
Outflow=∑(inputs) -Demand
and
Outflow >= 0
I get an infeasible problem. However, I'm not sure how to formulate this in a way of saying the outflows will be the inputs minus demand OR zero if inputs are less than or equal to demand. Any ideas of tricks within the equality and inequality matrices? I'd like to keep using lsqlin rather than something like fmincon due to the speed of the solver but any ideas on what to do if I'm SOL with lsqlin are appreciated!
  2 个评论
Matt J
Matt J 2018-8-15
编辑：Matt J 2018-8-15
Is the "difference between the simulated flow balance in each node and a constant value" the same as
| ∑(inputs)-Outflow-Demand |
If not, what is the objective function, exactly?
Jacob Tracy
Jacob Tracy 2018-8-15
Good question, that is essentially the point. The graph is made up of an edge table generated with this network package from MIT: http://strategic.mit.edu/downloads.php?page=matlab_networks.
Each row represents a node and each column represents a link. A [1,-1, or 0] in position [i,j] means that link j leaves, enters, or does not touch node i, respectively. The attached picture is probably the best representation I can find to show this.
From a function, I have the demand at each node, so the lsqlin will make this edge table the C matrix, and d will be a vector of demands the same length as the number of nodes. So basically the system is trying to meet demand at every node subject to a few constraints. I have issues when the supply from my source nodes isn't enough to meet the whole system demand, then the lsqlin will distribute the shortfall in demand evenly across the system.
I would rather give the system the rule that flow will not leave a node until it's own demand as filled, and outgoing flow will be zero if there is a shortfall. This will help me see the distribution of failure more accurately. However I can't think of a way to do this with the way the A,b, Aeq, beq matrices used in lsqlin.

请先登录，再进行评论。

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

采纳的回答

Walter Roberson
Walter Roberson 2018-8-16
None of the Mathworks optimization algorithms are able to handle OR constraints, other than as general nonlinear constraints.
The efficient way to handle such constraints is to run the model multiple times, each time with a different combination of linear constraints, systematically switching between the ordinary linear constraints and possibility of the alternative constraint. Then at the end, examine all of the results and take the best version.
Any optimization routine that permitted OR constraints would have to do the same thing as I just outlined. However, I suspect it might be theoretically possible that some of the algorithms that already break the range into subregions and solve simpler problems within each subregion, might be able to detect that some of the OR constraints do not have any influence on a particular subregion they are examining and so possibly an algorithm could be written that sometimes was able to do better.
  2 个评论
Jacob Tracy
Jacob Tracy 2018-8-16
Can you expound upon that second point a little? It seems like a good way around the rigidity of my current issue but I am having trouble seeing how I could really put together the results of models with the different constraints.
Walter Roberson
Walter Roberson 2018-8-16
You can choose the version with the lowest resnorm (lsqlin) or fval (fmincon, ga). Your function submitted to fmincon or ga should be returning the sum of squares of the residues, so the results should be directly comparable with resnorm .

请先登录，再进行评论。

更多回答（1 个）

Matt J
Matt J 2018-8-15
编辑：Matt J 2018-8-15
You could try using ga() instead with the constraints
max( ∑(inputs) -Demand -Outflow , -Outflow) = 0
This is equivalent to
Outflow = max( ∑(inputs) -Demand , 0)
which I think is what you want.
  2 个评论
Jacob Tracy
Jacob Tracy 2018-8-16
That constraint certainly worked, only problem is now the solver takes magnitudes more time whether or not I use fmincon or ga, which is crazy to me since it's not a computationally expensive constraint. I am wondering if I am entering my objective function into ga in an inneficient manner:
A = evalin('base','A');
B = evalin('base','B');
y = zeros(1,1);
for i = 1:size(A,1)
y = y+ sum(sum(x.*A(i,:))-B(i));
end
Where A is the size of the number of nodes and B is a vector with each corresponding demand. Thoughts?
Matt J
Matt J 2018-8-16
编辑：Matt J 2018-8-16
No, that's very inefficient. First, do not use evalin to pass A and B to your objective. Use anonymous or nested functions to pass fixed parameters.
Secondly, get rid of the for-loop. Compute the objective value in one line,
y=norm(A*x-B);
Thirdly, use ga, not fmincon. Your constraints are not differentiable.
Fourthly, it might help in terms of speed and reliability to include certain judicious x in your initial population, which are likely to be near the global solution. For example, you could include the solution of the relaxed linear problem
Outflow >= ∑(inputs) -Demand
Outflow >= 0
which is easily obtained with lsqlin.

请先登录，再进行评论。

类别

在 Help Center 和 File Exchange 中查找有关 Linear Least Squares 的更多信息

标签

产品

Community Treasure Hunt

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

Start Hunting!

Translated by