Does the third problem have {0,1} restriction of variables xij ?

If constriant on xij is only non-negative, i.e., xij >= 0, it is a case of classical LP (linear programming) problems. LP in general can be solved within polinomial time of problem size (with internal point methods).

Hello, Kita sensei!

I am happy to discuss this question with you. Despite we have collaborated closely, we have not many chances to discuss a common question together.

Problem (3) is essentially an integer problem. In this sense, it is normal to assume that xij are 0 or 1.  However, as you see in the case of the constraints  of problem (1),  all the extreme points of the polytope defined by this kind of linear inequalities have integer coordinates. Thus, the linear programming program gives solution to the integer problem.

The polytope defined by inequalities

             ∑ i=1N xij  = 1  ∀　i=1, ..., N

            ∑ j=1N xij  = 1  ∀　j=1, ... , N;

             xij  ≧ 0   　 ∀ i, j =1, ...,  N,

is called Birkhoff polytopte. This is the set of doubly stochastic matrices.  

(Sorry! In the original version of my question, there were some typos. In the case of classical assignment problem, M =N. )

Any  extreme point of this polytope is a permutation matrix, i.e. a matrix of the type

              P  =  (δ( i, σ(i)) )

where δ(i,j) is the Kronecker's delta (1 if i=j, 0 if not) and σ is a permutation of set of [N] = {1, 2, ... , N}. This is the famous Birkhoff=von Neumann theorem.

This  theorem can be generalized to the following form:

Theorem  Let

                 D = { X = (xij) ∈ RM+N |  X = ( xij ) ≧0,  ∑ i=1M xij = ai,  

                               ∑ j=1N xij = bi, xij = 0 ∀(i, j) ∈J },

where J is a subset of [M]×[N] and ai, bi are non-negative integers. Then any extreme point of D has all integer coordinates.  

(I do not know English paper that refers to this theorem. In Japanese, this is Lemma 2.6 (p.41) of Iwabori Chokei, Linear Inequalities and their Applications, Iwanami, 1977.)

 The constraints of problem (3) satisfies the conditions of the above theorem. So the LP problem  has the same solutions whose extreme solutions are solutions to the integer problem.

If we use the above theorem, problem (3) can be rewritten as the following problem as well:

                          maximize    ∑i=1M ∑j=1N  aij xij                (3)           

subjected to 

　　　　　　　　 ∑i=1N  xij  = 1     ∀ｊ;

  　　　　　　　　∑j=1Nxij  = 1　   ∀i;

                       xij ≧　0            ∀i, j.  and

                       xij  = 0  if (i, j) 　∉　E.

 Joachim Pimiskern,

welcome you to this question page. It is a great pleasure that you with RG score 188.77 paid interest to my question. Do you have any suggestions?

Dear Shiozawa sensei,

your original problem is picking an entry

from a matrix where each row and each

column is visited exactly once.

IMHO it's a Travelling Salesman problem

with 2N cities, N cities for each row,

N cities for each column. In turn, a

city of the row group has to be visited,

then one of the column group. The edge

weights correspond to the a_i_j.

Regards,

Joachim Pimiskern

Joachim Pimiskern,

thank you for your quick response. Your answers counts more than 2 thousand. I had only recently arrived at 2 hundred level.

My problem may seem similar to travelling salesman problem (TSP), but  not exactly. If it is equivalent to a TSP, it is NP-difficult. 

As I have discussed with Kita sensei, the constraint conditions of problem (3) is 

　　               ∑i=1N  xij  = 1     ∀ｊ;

  　　　　　　　∑j=1xij  = 1　   ∀i;

                    xij ≧　0            ∀i, j.

Then, if M = N, the set of all feasible point is the Birkhoff polytope and an extreme points of this set is a permutation of the set [N]. Expressed as  a bipartite graph, the graph covers all 2 N vertices but it is not connected. It does not form a closed cycle.  

Best regards,

Shiozawa

I do not know the answer but this is what i thought.

If you can build a deterministic algorithm to solve this problem in polynomial time then it belongs to Class P. If not, you can try to prove  that this problem is in NP-Complete.

(summarizing some theory)

1° Prove that this problem is in NP.

a) Define a structure to represent a solution from this problem.

b) Build a non deterministic turing machine (random algorithm) to generate a solution.

c) Build a deterministic algorithm to verify if the generated solution satisfies the problem.

2° Prove that this problem is NP-Complete

build a polynomial tranformation from [math] pi^* \in NP-C[/math] to your problem.

try to transform from SAT or TSP to this problem.

Also I guest this is a combinatorial problem, and looks like the Linear Ordering Problem (LOP).

I hope this helps in some way and find an anwer to your question.

Article The Linear Ordering Problem: Instances, Search Space Analysi...

Article ΠGarey Michael R. and Johnson David S.. Computers and intrac...

Isn't the original problem simply

bipartite matching, which can be

solved in P-Time with Ford-Fulkerson?

Regards,

Joachim

José Carlos Soto,

thank you for your introduction. I know or can guess the general path of proof  but I do not think that I can do it myself.

I have written that it is my problem, but I am not working on it. I want to know the answer and if it is known I want to use it as an illustration. 

The book you have cited, that of Garey and Johnson, brings me back memories when I tried to read. I tried on several occasions but it always remains beyond my reach.

Regards,

Shiozawa   

Indeed, if the problem formulation is correct then it can be converted into a simple minimum cost network flow problem, which is solved in polynomial time by a simple flow algorithm. The Hungarian algorithm was fun to work with - I remember doing it in a course of combinatorial optimization around 1986. Very simple, and rather elegant.

Dear Michael Patriksson,

Thank you for your post. What do you mean when you say "if the problem formulation is correct"? Do you think there is a flaw in my problem formulation?  

A necessary condition for your problem (3) to be feasible is that M = N. So it doesn't seem to be any different from the standard assignment problem.