4
$\begingroup$

I have $n$ objects $O_i$, each of them having $3$ values, $O_i = (A_i, B_i, C_i)$. I am trying to group them into $k$ groups $P_u$ such as $P_u =(A_u, B_u, C_u)$ such that

$$\text{minimize} \quad \sum_u^k M_k \left( a A_u + b B_u + c C_u \right)$$

for all $O_i \in P_u$, $A_i \leq A_u$, $B_i \leq B_u$, $C_i \leq C_u$. Here, $M_k$ is the numbers of objects $O_i$ in each category ($\sum M_k =n $). $a$, $b$ and $c$ are constants, as $A$, $B$ and $C$ do not have the same weight.

Can anyone link me to a theorem or some literature that would give me an idea of how to solve my problem?


I am not a mathematician or anything alike. I am an engineer with what I assume is a trivial optimization problem. Let me clarify what I'm trying to achieve.

I am a structural engineer and I have to design beam bearing plates, each bearing plates having $3$ dimensions (length, width and thickness). In a given building it is not uncommon to need $100$ or more bearing plates, each with their own dimensions. However for the sake of practicality we oversize some and group them so that at the end we only have a few different bearing plates ($k$ groups of plates, $k$ being a number chosen arbitrarily by the engineer and not a variable to optimize). We cannot undersize any plates.

I am trying to find a way to optimize the design of those groups so that the act of grouping the plates waste as little money as possible, so the values to be optimized are the dimensions of each group of plates.

Factors $a$, $b$ and $c$ comes into play because bumping up a plate thickness is more costly than bumping up its length or width.

I hope this clears up any misunderstanding, if not just let me know. Thanks all!


Fedja's possible clarification (I'm not sure if this is what OP had in mind)

There are $n$ triples $(A_i,B_i,C_i)$ of real numbers ($i=1,\dots,n$). We want to partition the index set $\{1,\dots,n\}$ into $k$ subsets $P_u$ so that the sum $$ \sum_u |P_u|[a\max_{i\in P_u}A_i+b\max_{i\in P_u}B_i+c\max_{i\in P_u}C_i] $$ is as small as possible, where $|P_u|$ is the cardinality of $P_u$.

What is an efficient algorithm for doing that?

I would also risk to assume that $a,b,c>0$ (which actually makes them redundant in the mathematical formulation of the problem: just replace $A_i$ by $aA_i$ and so on).

$\endgroup$
  • 1
    $\begingroup$ Is each $P_u$ a set of points $O_i$? If so, what does it mean that $A_i \le A_u$? What is this $A_u$? But if instead $P_u$ is a point with coordinates $(A_u,B_u,C_u)$, then in what sense is $P_u$ a group of objects, rather than just being an object? Are categories the same as groups, or some other means of organizing the objects? $\endgroup$ – Ben McKay Aug 18 '18 at 6:41
  • 3
    $\begingroup$ I tried to guess what was really meant. Sorry if I was wrong :-) $\endgroup$ – fedja Aug 18 '18 at 18:26
  • $\begingroup$ I edited my post to try and clarify what my problem is. Thanks for your help! $\endgroup$ – Antoine Carpentier Aug 18 '18 at 21:53
  • $\begingroup$ As your problem is currently phrased, letting k=n gives the minimal possible cost (for then A_i=A_u, etc.) You need some relation that says why making fewer groups is cheaper. I am not seeing that relation in this formulation. Gerhard "Need A Nontrivial Optimization Problem" Paseman, 2018.08.18. $\endgroup$ – Gerhard Paseman Aug 18 '18 at 21:54
  • 1
    $\begingroup$ If you are given k and can't change it, then you need to say that. Then I would start with a sectioning process. For simplicity I try one of the dimensions, but for your problem it may be more complicated. Heuristically, "line the books on the shelf from left to right, shortest to tallest, and find k similar groups". Search for k-means algorithms. Gerhard "Good Luck With Your Plates" Paseman, 2018.08.18. $\endgroup$ – Gerhard Paseman Aug 18 '18 at 22:10
1
$\begingroup$

I think what is wanted is a k-means algorithm or something similar for optimizing the cost. Let's look at it in terms of packing books.

I am able to order k boxes for packing my (long) shelf of n books. Many aspects of my order have low cost, but one aspect which I want to optimize is space-height. So when I pack books in a box, the books should all be about the same height; I can pad or adjust for depth and width cheaply, but I need to get the height optimally arranged for my order of boxes.

How do I organize the books? I arrange them in order from smallest to largest height, then I make divisions into k groups of equal numbers of books to start. Then I compute the cost of ordering k boxes for this grouping as a threshold. Then for each book which is the tallest or shortest in the group, I shift it from one stack to an adjoining stack, and recompute my cost function. If I lower the cost by moving the book, the book gets assigned to the new stack.

I iterate this (moving an end book from one stack to an adjacent stack) among the k stacks until I achieve a satisfactory optimum. This is not quite a k-means clustering algorithm, but it shows the basic idea.

For the stated problem, it might be useful to go one of two ways: have the cost function (aA+bB+cC) be the "height" of the book that is the value to do the k-means clustering, or (since the original algorithm worked on grouping n-dimensional data points into clusters) work on grouping the triples into clusters, and then applying the cost function and massage the clusters for improved solutions.

I do not claim that this is the best or most efficient algorithm for this problem. However, k-means clustering seems to be the natural approach (even though a local sup, not a mean or average, is wanted).

Gerhard "Applying Himself To Applied Math" Paseman, 2018.08.18.

$\endgroup$
  • $\begingroup$ Thanks for this detailed answer! The book analogy really helps me understand how to go about solving my problem. I will write a code doing just what you described and see what it gives me. $\endgroup$ – Antoine Carpentier Aug 19 '18 at 0:57
1
$\begingroup$

For if $n$ and $k$ are very small, so this actually doesn't stall out.

Let $x_{ij}$ be the number of copies of $O_i$ in group $j$. Of course we will only want each object to be in exactly one group. Define additional unknowns $\hat{A}_u$ $\hat{B}_u$ and $\hat{C}_u$ as well. These are $\frac{A_u}{max A_i}$, this way they are bounded between $0$ and $1$.

$$ A_i x_{ij} \leq \hat{A}_j (max A_i)\\ B_i x_{ij} \leq \hat{B}_j (max B_i)\\ C_i x_{ij} \leq \hat{C}_j (max C_i)\\ $$

If $x_{ij}=1$, then this accomplishes the $A_i \leq A_u$ type constraints and if $x_{ij}=0$, then it is vacuously true anyway.

There is also the constraint that

$$ \sum_j x_{ij} = 1 $$

The optimization is done over $x_{ij} \in \{ 0,1 \}$ and $\hat{A}_u$, $\hat{B}_u$ and $\hat{C}_u$ between $0$ and $1$.

The quantity to minimize is the quadratic function in the unknowns

$$ f = \sum_{i=1}^n \sum_{j=1}^k x_{ij} (a \hat{A}_j (max A_i) + b \hat{B}_j (max B_i) + c \hat{C}_j (max C_i) ) $$

You might want to weaken the $x_{ij}$ to be in $[0,1]$ instead. You could then use off the shelf quadratic programming tools.

$\endgroup$
  • $\begingroup$ Correct me if I'm wrong, but your approach requires the objects Oi to already be sorted out into the j groups, right? $\endgroup$ – Antoine Carpentier Aug 19 '18 at 4:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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