Linear assignment with additional constraints

Question

In a standard linear assignment problem, I can use the Hungarian Algorithm to achieve O(n^3). What if an additional constraint is added? Example:

A "regular" LAP with 4 agents has constraint matrix

and result vector b = [1 1 1 1].

The Hungarian Algorithm will solve such problems as expected. But what if another constraint is added, such that the constraint matrix is

with results vector b = [1 1 1 1 0] ??

That is, apart from minimizing a cost function under the standard linear sum constraints, I must also consider a constraint like

This sum produces the last row in the appended matrix above.

Apparently, the resulting constraints matrix is no longer totally unimodular. Of course, standard MILP will solve this, but it is NP hard. My question is: Is there an Hungarian-like alogorithm which will solve this LAP in polynomial time?

Where does this constraint-matrix come from? It does not look like an LP for an assignment-problem of 4x4 to me. — sascha
– sascha, Commented Oct 23, 2017 at 15:03
No it's not. A LP in standard-form for an assignment-problem of size n has n*2 constraints and n^2 variables. Yours does not (if we interpret this constraint matrix as LP-formulation). So it's hard to work with your formulas. And my hunch says: no... there is no poly-solution. — sascha
– sascha, Commented Oct 23, 2017 at 15:38

Tryer · Accepted Answer · 2017-10-23 17:04:59Z

2

In general, a network flow problem with side constraints is NP-Hard. For instance, a shortest path problem with non-negative edge costs, is polynomially solvable. You could use, Dijkstra's shortest path algorithm, for instance. (The assignment problem is a special case of a network flow problem.)

However, if you add a single constraint that stipulates that the number of edges used should be less than some constant, the ensuing constrained shortest path problem is NP-Hard.

So, it is very unlikely that your problem has a polynomial algorithm.

edited Oct 23, 2017 at 17:04

answered Oct 23, 2017 at 16:58

Tryer

4,1981 gold badge35 silver badges71 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

tw-S Over a year ago

Thanks, sad news, but very helpful!

Collectives™ on Stack Overflow

Linear assignment with additional constraints

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related