How to solve such a grouping optimization problem in Matlab?

The problem is like:

- I have n numbers, need to divide them into some groups. (There is upper/lower bound on group size)

- The objective is to minimize the average of maximum in each group.

Is there a solver in the Optimization Toolbox that can handle this kind of problem?

[Bruno Luong]

It depends. If the problem size is reasonable it is probably possible to do exhaustive search using integre partioning (integer composition).

Otherwise I can only see GA as possible empirical search.

Answer 1

[Shreshth]

Hello 成山 ,

I could understand that you are trying to divide n numbers in several groups and each groups having specified minimum and maximum.

To solve this problem using an optimization toolbox, you would typically look for a solver that can handle integer programming or mixed-integer programming, as the problem involves dividing items into groups which is a discrete process.

The problem you've described has the following characteristics:

• You have ‘n’ numbers that need to be grouped.
• Each group has a size limit (upper and lower bounds).
• The objective is to minimize the average of the maximum values of each group.

This problem can be formulated as a mixed-integer programming (MIP) problem because you have to make discrete decisions about which numbers go into which groups, and you also have continuous variables representing the maximum values of each group.

In MATLAB's Optimization Toolbox, the function that handles mixed-integer programming problems is ‘intlinprog’. However, this function is for linear programming problems, and your objective function (minimizing the average of maximums) is not linear due to the maximum function.

To solve this with ‘intlinprog’, you would need to linearize the problem. One way to do that is to introduce auxiliary variables and constraints to represent the maximum values in each group. The objective function can then be adjusted to minimize the sum of these auxiliary variables, which would be equivalent to minimizing their average.

Here is a high-level description of how you might set up the problem:

1. Define binary variables that determine whether a number is in a particular group.
2. Define auxiliary continuous variables that represent the maximum value in each group.
3. Add constraints to ensure that each number is in exactly one group.
4. Add constraints to link the binary variables with the auxiliary variables to correctly represent the maximum values in each group.
5. Add constraints to respect the upper and lower bounds on group sizes.
6. Define the objective function to minimize the sum of the auxiliary variables, which represent the maximum values in each group.

If the non-linearity of the maximum function or the complexity of the problem makes it unsuitable for ‘intlinprog’, you might consider using MATLAB's Global Optimization Toolbox, which includes solvers like ga (genetic algorithm) that can handle more complex, non-linear optimization problems.

To understand the process more u can refer to the below resource from MathWorks:

https://www.mathworks.com/help/optim/nonlinear-programming.html

Further for reference to a similar problem you can have a look at the below discussion at the MATLAB forum.

https://www.mathworks.com/matlabcentral/answers/490185-how-do-i-get-matlab-to-solve-the-following-mixed-integer-non-linear-optimization-problem

Thank you,

Shubham Shreshth.