# linear programing : maximize $\sum \limits_{i=1}^{n} C_i$ where $C_i$ is circumference of circle with center at $\{x_i,y_i\}$

given n points on $\mathbb{R^2}$ $\{(x_1,y_1),(x_2,y_2),\dots,(x_n,y_n)\}$

formulate a linear program to maximize the sum of the circumference of all circles so any two circles won't intersect (two tangent circles are allowed).

i successfully formulated the target function that i need to maximize $$\max \sum \limits_{i=1}^{n}2R_i\pi$$ where $R_i$ is the radius of circle $i$, but when i try to formulate the restrictions i get for any $1\le i \le n$ and any $1\le j\le n$ such that $j\not =i$ $$(x_i-x_j)^2+(y_i-y_j)^2 \ge (R_i+R_j)^2$$

its not longer linear . so its not a proper linear program . i guess there must be some kind of clever trick or alternative formulation that i fail to think of.

this is a home-work question so i would prefer a hint or a solution to a similar problem instead of full solution to this problem .

$(xi_−x_j)^2+(y_i−y_j)^2≥(R_i+R_j)^2$

You can actually just take the square root here:

$R_i+R_j \le \sqrt{(x_i−x_j)^2+(y_i−y_j)^2}$

• i think that all the variables need to be linear to each other . like $a_1x_1 = a_2x_2 +/- a_3x_3 +/- \dots +/- a_kx_k$ this way we can always express any one of them in linear form. just by negating from the both sides the needed variables – Boris Morozov Jun 25 '14 at 13:24
• The expression is linear in the $R_i$s which you are trying to optimize. The term on the RHS may look complicated, but in terms of radii it is just a constant like any other constant. You may as well call this $z_{ij}$ without losing any useful information. – Wonder Jun 25 '14 at 13:28
• thx i think i understand – Boris Morozov Jun 25 '14 at 13:30

Let

$d_{ij}= \sqrt{(x_i - x_j)^2 + (y_i-y_j)^2} \quad \forall i<j$

$R_i+R_j \leq d_{ij} \quad \forall i<j$

and thus a linear program. You should force

$R_i\geq0 \quad \forall i$,

but since your maximizing is redundant.