Partition of Set of Values into Subsets so that the ratio of the minimal and maximal value of the subset becomes minimal

Question

I am currently trying to solve the following Problems:

1. I have a given a set of values. I want to find a partition of the set into a fixed number of subsets, so that the maximum ratio between the minimal and maximal value in the subsets becomes minimal. In case this was confusing, a more mathematical description:

   Given $S=\{a_1,a_2,\ldots ,a_{n1}\}$ with $a_i\geq 0$, I want to find subsets $S_1,S_2,\ldots ,S_{n2}\subset S$ so that $S_1\cup S_2\cdots \cup S_{n2}=S$ that minimize $\max \limits _{1\leq i\leq n2}\dfrac{a^i_{max}}{a^i_{min}}$.

2. I want to find a partition into a minimal amount of subsets without a fixed number of subsets $n2$ for which $\max \limits _{1\leq i\leq n2}\dfrac{a^i_{max}}{a^i_{min}}\leq c$, for some constant $c\geq 1$.

Do these problem have a name that I can research? Any tips in general?
I am grateful for anything.

Answer 1

Here's a mixed integer linear programming formulation for the first problem. Let $b_i = \log a_i$. Let $L = \min_i b_i$ and $U = \max_i b_i$. Let binary decision variable $x_{i,j}$ indicate whether item $i$ is assigned to set $j$. The problem is to minimize $z$ subject to \begin{align} \sum_j x_{i,j} &= 1 &&\text{for all $i$} \tag1 \\ \sum_i x_{i,j} &\ge 1 &&\text{for all $j$} \tag2 \\ u_j &\ge b_i x_{i,j} + L (1-x_{i,j}) &&\text{for all $i$ and $j$} \tag3 \\ v_j &\le b_i x_{i,j} + U (1-x_{i,j}) &&\text{for all $i$ and $j$} \tag4 \\ z &\ge u_j - v_j &&\text{for all $j$} \tag5 \end{align} Constraint $(1)$ assigns each item to exactly one set. Constraint $(2)$ assigns at least one item to each set. Constraint $(3)$ enforces $u_j \ge \max_{i:x_{i,j} = 1} b_i$. Constraint $(4)$ enforces $v_j \le \min_{i:x_{i,j} = 1} b_i$. Constraint $(5)$ implements the minimax objective.

Answer 2

Suppose that $a_1\le a_2\le ...\le a_n$.

Introduce a directed graph $G=(V,E)$ where $V=\{v_1,...,v_{n+1}\}$, $e_{ij}\in E$ for all $i,j=1,...,n+1; i<j$, and $w_{ij}=a_{j-1}/a_{i}$. Here, vertex $v_i$ introduced for value $a_i$ and $w_{ij}$ is the ratio between the maximum and minimum values in the subset $S_{ij}= \{a_i,...,a_{j-1}\}$.

Then, the optimal partitioning of the values $a_i$'s is corresponds to a directed path between vertices $v_1$ and $v_{n+1}$, and you can introduce some approximation algorithms to solve the problems.

Moreover, you can introduce binary variables $x_{ij}$ to show the selection of the subset $S_{ij}= \{a_i,...,a_{j-1}\}$ as a partition or not, and solve the following ILP problems.

1)$min\ r:\ \ r\ge w_{ij}x_{ij},\ \ \sum_{i,j}x_{ij}=n2, \ \ \sum_{i,k} (x_{ij}-x_{jk})=0, \ \ \sum_j x_{1,j}=\sum_i x_{i,n+1}=1$

2)$min\ \sum_{i,j}x_{ij}:\ \ c\ge w_{ij}x_{ij},\ \ \sum_{i,k} (x_{ij}-x_{jk})=0, \ \ \sum_j x_{1,j}=\sum_i x_{i,n+1}=1$