A structural optimization problem

Question

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

Answer 1

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.

Answer 2

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.