Hi Thilo!

I suspect you need rather more information about your function.  Consider the following example on 2n vertices.  Take a 2xn grid: pick a subset S of the bottom row.

Now, define f(T)=0 if T is the union of the vertices in the top row together with S, and 1 otherwise.  Clearly these vertices form a connected subgraph. Then even knowing that this is the definition of the function, if you don't know S, you have to test all 2^n subsets of the bottom row in order to minimize the function.

Hi Thilo, 

I understand that you are making a formulation of a generality. If you are searching for an algorithm to do that kind of job for you, then there's a wide range of procedures that can obtain your goal with the conditions that you are presenting.

The procedures that can help you, could be:

Exacts methods(Slow in big problems, high quality solutions), like Branch&Bound, Branch&Cut, etc... which uses the simplex or the interior point method to solve your objective fuction and assign values to the variables of your exact model. On the other hand, you have to formulate your model first. Maybe this book may provide some ideas of what you want to solve (you must relate the problems presented with yours).

BOOK : https://books.google.com.co/books/about/The_Vehicle_Routing_Problem.html?id=TeMgA5S74skC&redir_esc=y 

if you don't have time or don't need to know how to program an exact algorithm, don't worry, there's a set of solvers that make a very good job with your model, like CPLEX, Gurobi, linprog(Matlab), AMPL, GAMS, etc. 

Metaheristics/Heuristics(Fast, It does not guarantee the optimum), specific methods that you must develop with some specific strategies, like, genetic algorithms, tabu search, local search, grasp, dijkstra algorithm, and a tons of other algorithms that you may test (have fun).

At the end, the only thing that matter is what you really need (performace, best solutions, reduce memory usage, etc).

In my personal opinion, you can begin with AMPL (if the model is small).

AMPL : http://ampl.com/

Cheers,

Hi Prof. Calkin!

I did not define the function f(G) because it does not have a close form. That is evaluating f(G) requires to solve a elliptic PDE. However, the function f(G) has some good properties: For example, if we select a set of 1's of a similar size (Size in terms of quantity of 1's) and close (Close in terms of distance) to the optimal set of 1's then the function f(G) is relatively small. While if select a set of 1's more far away from the optimal solution, then f(G) becomes large. Furthermore, the set of 1's usually appears in such a way that the sum of the distances between all 1's is as small as possible. 

Dear Thilo.

Your definition of the function f is too general. You must specify additional conditions for that function.

If you do not pose any additional conditions on the function f, your problem is NP-complete in the decision variant. If you formulate it as an optimization problem, it may have all possible complexities going from PTAS to NPO-complete.

For instance, if you add the additional condition that each edge must have at least one vertex assigned the value 1, then you encode the MINIMUM VERTEX COVER problem, which is APX-complete and has a very easy approximation algorithm with the approximation factor 2, i.e. in the worst case your solution will be 2-times larger than the optimum. If moreover you know that your graph G is planar, then there exists a PTAS, i.e. you can approximate the optimum with any ration larger than 0.

If you choose a different additional condition, for instance that for each vertex u with f(u)=0 there exists another vertex v with f(v)=1 for which (u,v) is an edge in the graph G, then you encode the MINIMUM DOMINATING SET problem, which is not in APX, but it is in logAPX, i.e. you can approximate the optimum within a logarithm of the vertex set cardinality |V|. However, if you know that your graph is planar, then there exists a PTAS also for this problem.

If you impose one more additional condition on the aforementioned dominating set problem, namely that no two vertices u and with with f(u)=f(v)=1 are joined by an edge in the graph G, then you encode the MINIMUM INDEPENDENT DOMINATING SET problem, which is NPOPB-complete. This class contains solutions that are recognizable in polynomial time, whose costs are also computable in polynomial time. (The PB in the title stands for “polynomially bounded”.) However, computing even a valid solution is NP-complete.

If you impose yet another condition on your function f, namely that each vertex u with f(u)=0 is adjacent to at most one edge in the graph G, then you encode the MAXIMUM MATCHING problem, for which there exists a well-known deterministic polynomial-time algorithm. Hence, you can compute the optimum exactly in polynomial time, no approximation needed.

I hope this helps.

As I understand it, your problem is a combinatorial optimization problem, but a rather "nasty" one in which you do not have a closed form for the objective function.  If you are able to quickly compute a lower bound on the cost that the function will have when any subset of the variables is fixed, then you may be able to solve the problem exactly via branch-and-bound.  Otherwise, I guess you will have to use a metaheuristic method, such as local search, simulated annealing, tabu search or genetic algorithms.

Thilo,

Is the structure of the planar graph also known?  Is it, for example, a nice triangulation (say bounded aspect ratio?) of a nice domain? If you look at the dual of the domain, so that vertices become faces and vice versa, can you say anything more about the solution set (now a set of faces): does it become, for example, almost convex?  Such features might be very helpful.

Neil

Prof. Calkin,

The structure of the planar graph is know. Meaning that each face has exactly 3 vertices, so that the dual domain (faces become vertices) is 3-connected. Hence, by Steinitz's theorem the graph can be represented as the graph of a convex polyhedron. However, I'm not sure how this is helping in solving the problem.  

Thilo

A couple of other quick thoughts.

1.  You could view your function as a set function, which depends only on the set of vertices selected.  If you could prove that the function has some nice property, such as submodularity, then you might be able to make progress without using the graph at all.

2. If you could show that your function can be well-approximated with a polynomial, then you could convert your problem into a polynomial optimisation problem.  Then you could use a software package for polynomial optimisation, such as GloptiPoly. (Note that x_i is binary if and only if x_i = x_i^2.)

Thilo,

One heuristic you might try, given that you have the "sum of squares of distances is small" phenomenon, is to start by looking at all vertices at distance

To optimize a function on a planar graph, maybe you should to use the spanning trees of this planar graph.

In my opinion, you should to use heuristic optimization methods, such as simulated annealing, tabu search, genetic algorithm, ant colony... I have coded their algorithms on VBA Excel in my PhD course term.

maybe use by prim algorithm