"OR" constraints lsqlin

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!

[Matt J]

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]

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.

Answer 1

[Walter Roberson]

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.

[Jacob Tracy]

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]

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 .

Answer 2

[Matt J]

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.

[Jacob Tracy]

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]

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.