Clever Geek Handbook

Maximize the sum of a number of constrained variables

I must have been banging my head on this issue for several hours; it is as follows (to rephrase to remove the silly history and context):

Given an interval that has N points, a point at each end, and a number of constraints, at least pairs of points can be and at least how far apart certain pairs of points should be, try to maximize the length of the interval. Points can overlap.

It seems to boil down to this:

There are N - 1 variables, each of which has length l (1..n-1)> = 0. There is a list of restrictions of this form:

l (i) + l (i + 1) + .... l (j) <= C, or l (i) + l (i + 1) + .... l (j)> = C,

and the task is to maximize l (1) + l (2) + .... l (n-1).

Feel free to ask about this on the Maths Stackexchange, as this is part of an exercise after the Algorithms lesson in Graph Search Algorithms; can you see how this can be converted to a graph problem? How else do you solve it?

Thank.

+3


source to share


2 answers


How to turn it into a graph problem: sort the numbers in ascending order. Take the smallest one, this will be the "root" (leftmost) starting point. Then take the next N items that satisfy your constraints, i.e. reachable from the starting point. These will be the children of the starting point and will be represented as a directional edge. For each child, repeat the above procedure until the glasses are finished. If in any iteration you cannot add new children, that means your constraints are preventing you from reaching the rightmost point of the interval ... you are kind of doing the first breadth-first search.



0


source


I came up with this after some thought

  • multiply all "at least" constraints by -1 to be in this form:

- (l (i) + l (i + 1) + ... l (j)) <= -C



  1. put all "at most" and negative "at least" constraints together to create a matrix.

  2. perform a form of "Gaussian elimination" on the matrix, noting how inequalities add

  3. go through the matrix and try to collect the amount. This step should be easy.

Cases without a valid solution and infinitely many solutions must be detected in a manner similar to normal matrices used to solve a system of linear equations.

What are your thoughts?

0


source






More articles:


All Articles