An optimization problem worthy of our attention

• Stephen Tashi
In summary, the problem is to find a matrix M' that has minimum cost and contains the same information as the matrix M.
Stephen Tashi
Perhaps forum members can advance science by solving this optimization problem from The Protein Engineer http://proteneer.com/blog/?p=1557

My statement of it:

Let M be a N x N symmetric matrix such that N is divisible by 3, all the diagonal entries are 0 and each other entry is either 0 or 1. We think of the matrix entry M[j] as representing whether an object i interacts with another object j. Imagine M partitioned into 3x3 submatrices ("tiles"). The "cost" of M is defined as the number of tiles that have at least one non-zero entry. ( I don't undestand the practical reason why the cost is defined that way.)

The information in M can be arranged differently by changing the order in which the objects are listed. (i.e. let s be a permutation of the numbers 1,2,...n and define a new matrix M' to have entries M'[j] = M[s(i)][s(j)] ) Find an algorithm with determines a matrix M' that has minimum cost and contains the same information as the matrix M.

Basically, the problem seems to be how do you partition the vertex set of a graph into 3-element sets such that the number of edges within all the partitioning subsets is minimized.

My first thought was, the obvious brute force strategy, where you just compute the cost for each permutation. Since there are a lot of permutations, that's computationally expensive. You can do a little better if you only compute one for each partition, but I think there are still a lot of partitions of a big set into 3-element sets.

A somewhat related problem is this. Say there are n vertices where n is divisible by 3 and let k = n/3. You could then ask whether the graph is k-partite. That would correspond to a cost of zero. My thought was that maybe graph theorists have thought about ways to determine whether a graph is k-partite and that maybe that would help with this problem.

Let's do a special case. Say we have a graph with 6 vertices. Then k = 2 and the question is whether the graph is bipartite, which would correspond exactly to the question of whether you can apply the permutations to the matrix to get a cost of zero. The answer is if and only if there are no odd cycles. It's clear that a bipartite graph can't have odd cycles, but the converse is a little more difficult to prove. As it happens, I was wanting to review that very result and the proof. It's not very hard, and I think it's constructive, so there should be an algorithm.

Anyway, maybe you could consider this problem as an extension of the question of whether something is k-partite. Like, is it k-partite after you remove one edge, two edges, etc. If you had algorithms for that, it might give you algorithms to minimize that cost. Just a thought.

Well, of course, there's a big difference here that I forgot about, which is that the size of the partitioning sets has to be 3, but I still wonder if something like that might help.

1. What is an optimization problem?

An optimization problem is a mathematical or computational problem that involves finding the best solution from all possible solutions. It is usually defined by a set of constraints and an objective function that needs to be maximized or minimized.

2. Why are optimization problems important?

Optimization problems have a wide range of applications in various fields such as engineering, economics, computer science, and more. They help us make better decisions by finding the most efficient and optimal solutions to complex problems.

3. How is an optimization problem solved?

There are different methods for solving optimization problems, such as mathematical programming, heuristic algorithms, and metaheuristics. The choice of method depends on the problem's complexity, size, and available resources.

4. What makes an optimization problem worthy of attention?

An optimization problem is worthy of attention if it has a significant impact on real-life situations, has a large number of possible solutions, or if finding the optimal solution is challenging and requires innovative approaches.

5. What are the challenges in solving optimization problems?

Some of the challenges in solving optimization problems include dealing with a large number of variables and constraints, finding the global optimum instead of a local one, and designing efficient algorithms that can handle complex and dynamic problems.

Replies
1
Views
2K
Replies
6
Views
2K
Replies
4
Views
2K
Replies
6
Views
2K
Replies
31
Views
3K
Replies
7
Views
2K
Replies
8
Views
2K
Replies
25
Views
3K
Replies
21
Views
2K
Replies
1
Views
1K