约束单目标优化

Question

Introduction

I need to split an array filled with a certain type (let's take water buckets for example) with two values set (in this case weight and volume), while keeping the difference between the total of the weight to a minimum (preferred) and the difference between the total of the volumes less than 1000 (required). This doesn't need to be a full-fetched genetic algorithm or something similar, but it should be better than what I currently have...

Current Implementation

Due to not knowing how to do it better, I started by splitting the array in two same-length arrays (the array can be filled with an uneven number of items), replacing a possibly void spot with an item with both values being 0. The sides don't need to have the same amount of items, I just didn't knew how to handle it otherwise.

After having these distributed, I'm trying to optimize them like this:

func (main *Main) Optimize() {
    for {
        difference := main.Difference(WEIGHT)

        for i := 0; i < len(main.left); i++ {
            for j := 0; j < len(main.right); j++ {
                if main.DifferenceAfter(i, j, WEIGHT) < main.Difference(WEIGHT) {
                    main.left[i], main.right[j] = main.right[j], main.left[i]
                }
            }
        }

        if difference == main.Difference(WEIGHT) {
            break
        }
    }

    for main.Difference(CAPACITY) > 1000 {
        leftIndex := 0
        rightIndex := 0
        liters := 0
        weight := 100

        for i := 0; i < len(main.left); i++ {
            for j := 0; j < len(main.right); j++ {
                if main.DifferenceAfter(i, j, CAPACITY) < main.Difference(CAPACITY) {
                    newLiters := main.Difference(CAPACITY) - main.DifferenceAfter(i, j, CAPACITY)
                    newWeight := main.Difference(WEIGHT) - main.DifferenceAfter(i, j, WEIGHT)

                    if newLiters > liters && newWeight <= weight || newLiters == liters && newWeight < weight {
                        leftIndex = i
                        rightIndex = j
                        liters = newLiters
                        weight = newWeight
                    }
                }
            }
        }

        main.left[leftIndex], main.right[rightIndex] = main.right[rightIndex], main.left[leftIndex]
    }
}

Functions:

main.Difference(const) calculates the absolute difference between the two sides, the constant taken as an argument decides the value to calculate the difference for

main.DifferenceAfter(i, j, const) simulates a swap between the two buckets, i being the left one and j being the right one, and calculates the resulting absolute difference then, the constant again determines the value to check

Explanation:

Basically this starts by optimizing the weight, which is what the first for-loop does. On every iteration, it tries every possible combination of buckets that can be switched and if the difference after that is less than the current difference (resulting in better distribution) it switches them. If the weight doesn't change anymore, it breaks out of the for-loop. While not perfect, this works quite well, and I consider this acceptable for what I'm trying to accomplish.

Then it's supposed to optimize the distribution based on the volume, so the total difference is less than 1000. Here I tried to be more careful and search for the best combination in a run before switching it. Thus it searches for the bucket switch resulting in the biggest capacity change and is also supposed to search for a tradeoff between this, though I see the flaw that the first bucket combination tried will set the liters and weight variables, resulting in the next possible combinations being reduced by a big a amount.

Conclusion

I think I need to include some more math here, but I'm honestly stuck here and don't know how to continue here, so I'd like to get some help from you, basically that can help me here is welcome.

Answer 1

As previously said, your problem is actually a constrained optimisation problem with a constraint on your difference of volumes.

Mathematically, this would be minimise the difference of volumes under constraint that the difference of volumes is less than 1000. The simplest way to express it as a linear optimisation problem would be:

min weights . x
    subject to  volumes . x < 1000.0
                for all i, x[i] = +1 or -1

Where a . b is the vector dot product. Once this problem is solved, all indices where x = +1 correspond to your first array, all indices where x = -1 correspond to your second array.

Unfortunately, 0-1 integer programming is known to be NP-hard. The simplest way of solving it is to perform exhaustive brute force exploring of the space, but it requires testing all 2^n possible vectors x (where n is the length of your original weights and volumes vectors), which can quickly get out of hands. There is a lot of literature on this topic, with more efficient algorithms, but they are often highly specific to a particular set of problems and/or constraints. You can google "linear integer programming" to see what has been done on this topic.

I think the simplest might be to perform a heuristic-based brute force search, where you prune your search tree early when it would get you out of your volume constraint, and stay close to your constraint (as a general rule, the solution of linear optimisation problems are on the edge of the feasible space).

Here are a couple of articles you might want to read on this kind of optimisations:

• UCLA Linear integer programming
• MIT course on Integer programming
• Carleton course on Binary programming
• Articles on combinatorial optimisation & linear integer programming

If you are not familiar with optimisation articles or math in general, the wikipedia articles provides a good introduction, but most articles on this topic quickly show some (pseudo)code you can adapt right away.

If your n is large, I think at some point you will have to make a trade off between how optimal your solution is and how fast it can be computed. Your solution is probably suboptimal, but it is much faster than the exhaustive search. There might be a better trade off, depending on the exact configuration of your problem.