<p>I can't remember the analytic way to do this!</p>

<p>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.</p>

<p>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!</p>

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

CC BY-SA 3.0
2011-09-09T07:51:12.370Z
Sorry, could you say that again without using genetic-programming language?  What's a "population"?  What's a "fitting function"?
Jeffε
CC BY-SA 3.0
2011-09-03T22:01:41.430Z
2011-09-03T22:01:41.430Z
eduardo pons
<p>Say we have a polyhedron in standard form:</p>

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

<p>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).</p>

<p>Also, are there any known results regarding the complexity of this problem?</p>

<h3>Addendum: Restricting the types of cuts:</h3>

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

<p>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.</p>

<p><strong>Note:</strong> After a few days of little progress, I posted this question at <a href="https://mathoverflow.net/questions/74779/finding-a-hyperplane-that-splits-a-convex-polytope-evenly">MathOverflow</a> too. </p>

CC BY-SA 3.0
2011-09-08T18:38:18.063Z
Shouldn't one be able to prove this is an NP-hard problem?
Peter Shor 
CC BY-SA 3.0
2011-09-08T18:47:07.970Z
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.
Amelio Vazquez-Reina
CC BY-SA 3.0
2011-09-08T19:21:50.570Z
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.
Opt
CC BY-SA 3.0
2011-09-08T19:55:09.577Z
Never mind. One would also have to be able to count the number of vertices added by the cutting plane.
Opt
<ds.algorithms><linear-programming><linear-algebra>
Finding a cutting plane that splits a polyhedron evenly
Amelio Vazquez-Reina
# Finding a cutting plane that splits a polyhedron evenly

(Asked by: username_0 on 2011-09-02)

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](https://mathoverflow.net/questions/74779/finding-a-hyperplane-that-splits-a-convex-polytope-evenly) too.

**Tags:** ds.algorithms, linear-programming, linear-algebra
> **Comments:**
> **username_1**: Shouldn't one be able to prove this is an NP-hard problem?  
> **username_0**: 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.  
> **username_2**: 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.  
> **username_2**: Never mind. One would also have to be able to count the number of vertices added by the cutting plane.  

---

## 1 answers

### Answer by username_3 on 2011-09-03. Score: -2

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!

> **Comments:**
> **username_4**: Sorry, could you say that again without using genetic-programming language?  What's a "population"?  What's a "fitting function"?  

---

