Say we have a polyhedron in standard form:

\begin{equation*} \begin{array}{rl} \mathbf{A}\mathbf{x} = \mathbf{b} \\\\ \mathbf{x} \ge 0 \end{array} \end{equation*}

Are there any known methods for finding a hyperplane $\mathbf{d} \mathbf{x} +d_0= 0$ that splits the polyhedron in a way that the number of vertices on each side of the hyperplane is approximately the same? (i.e. an algorithm that minimizes the absolute difference of vertex cardinalities on the two sides of the split).

Also, are there any known results regarding the complexity of this problem?

Addendum: Restricting the types of cuts:

Here is a variation of the original problem with the hope that it is easier to solve than the original one:

Is there a way to efficiently compute or estimate for which coordinate $i$ a hyperplane of the form $d_ix_i + d_0 = 0$ would yield the lowest absolute difference of vertex cardinalities on both sides of the split? By efficient I mean anything more efficient than the exhaustive enumeration of vertex cardinalities for all possible such splits.

Note: After a few days of little progress, I posted this question at MathOverflow too.

  • $\begingroup$ Shouldn't one be able to prove this is an NP-hard problem? $\endgroup$ Commented Sep 8, 2011 at 18:38
  • $\begingroup$ Thanks @Peter. A proof would be great. That said, I presume the problem is hard, and I think I am more interested in heuristics or approximation algorithms. The motivation behind the idea of restricting the types of cuts was in part to see if there are easier variations of the general problem for which we already know a solution or an approximation algorithm. $\endgroup$ Commented Sep 8, 2011 at 18:47
  • $\begingroup$ How about something along these lines (not sure if it works) - We know counting the number of maximum bipartite matchings is #P-hard. We also know that a linear program to find a maximum bipartite matching is totally unimodular and thus any corner point/basic feasible solution is integral. For a maximum bipartite matching problem, find the value of the matching. Construct a linear program with the constraint that any solution has to have the optimal value. Then every corner point is a matching. Being able to repeatedly divide evenly means you should be able to count the number of matchings. $\endgroup$
    – Opt
    Commented Sep 8, 2011 at 19:21
  • $\begingroup$ Never mind. One would also have to be able to count the number of vertices added by the cutting plane. $\endgroup$
    – Opt
    Commented Sep 8, 2011 at 19:55

1 Answer 1


I can't remember the analytic way to do this!

But this a classical problem for Genetic Programming! If you are familiar with it you can use a normalized vectors in the center of the polyhedron that describes the cutting plane.

So your population is a set of [x,y,z,...] normalized vectors and as fitting function you use the difference between the 2 split volumes!

So, if the difference tends to zero more "fit" is your vector/plane!

  • $\begingroup$ Sorry, could you say that again without using genetic-programming language? What's a "population"? What's a "fitting function"? $\endgroup$
    – Jeffε
    Commented Sep 9, 2011 at 7:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.