2
$\begingroup$

I would like to write some linear equations and inequations to state that the sum of all possive x - C is smaller than L.

As my math knowlegde is very limited I'm looking for some way to only sum up the x - C that are not negative. Is there maybe some trick to add additional binary dummy variables? Or is this just not possible and I have to formulate my problem as a non-linear problem.

Some background to clarify the problem:

I want to add a limitation to my simplex tableau to check if a bucket is too full. A bucket is limited by the constant L. Items can fall into mutiple neighbouring buckets, e.g. 40% in the fourth bucket, and 60% in the fifth. The only way to find out how much of an item is placed into the bucket is by substracting the location of each bucket and adding the total length of the item (summarised in C) from the absolute location of the beginning of the item x. x is a variable as its choice affects the optimisation. Checking that no bucket overflows is only a limitation, and the amount of buckets is known in advance.

The problem arises, as substracting C from x can result in negative values. If I now sum up all x - C I cannot check if it is smaller than L, as the negative values will allow more items to be placed in the bucket, as L allows.

EDIT:

Alternativly, it would be sufficient if I could check that x1 + its size is either smaller than another x2, or that x1 is langer than x2 + its size.

If I however write both constraints in my simplex tableau the problem has no solution, as the two notations contradict.

$\endgroup$
3
$\begingroup$

I believe that what you're looking for is simply this: $$\sum_{i:~x_i\geq C} (x_i - C) \leq L \quad\Longleftrightarrow\quad \sum_i \max\{ x_i - C, 0 \} \leq L$$ It is not difficult to express this in a linear program. Let $y\in\mathbb{R}^n$ be a new variable of the same size as $x$. Then this system of inequalities will give you what you want: $$ \sum_i y_i \leq L, \quad \begin{array}{c} y_i \geq 0 \\ y_i \geq x_i - C \\ \end{array} \quad i=1,2,\dots, n$$ It's not difficult to show that you can use $\sum_i y_i = L$ instead of $\sum_i y_i \leq L$ if you wish.

EDIT: Promoted from a (now deleted) comment below. It would be incorrect to think that $y_i$ is "equal" to $x_i-C$ or $\max\{x_i-C,0\}$. Yes, that will often be true, but it is not necessarily true. In particular, suppose that the original inequality is strictly satisfied; i.e. $$s+\sum_{i:~x_i\geq C} (x_i-C) = L$$ for some positive value of $s$. Then it is not difficult to see that $$y_i = \max\{x_i-C,0\} + s / n, \quad i=1,2,\dots, n$$ satisfies the system of inequalities I have offered. On the other hand, if $x$ is infeasible—that is, if $\sum_{i:~x_i\geq C} (x_i-C) > L$—then there is no value of $y$ that satisfies those inequalities.

In an intuitive sense, $y$ sits in between $x-C$ and the condition imposed upon it.

$\endgroup$
  • $\begingroup$ Great answer, thanks. I however had an error in my problem formulation, as I did not yet account for items x assigned to buckets after the current bucket. However, with your formula I can also define that constraint, as it follows the same logic. I'll post a second answer tomorrow showing how I hopefully solved my edited question, however your answer is the perfect answer for the question orginally asked. $\endgroup$ – Franz Kafka Jan 15 '15 at 17:37
0
$\begingroup$

To check that x1 and x2 are not overlapping I added two helper variables h1, h2 that can only be 0 or 1 and used a predefined Z that is larger than any two xs plus their Cs can ever be.

$$ \begin{array}{c} \quad x_1 - (x_2 + C_2) + h_1*Z \leq Z \\ x_1 - (x_2 + C_2) + h_1*Z \geq Z \end{array} \begin{array}{c} \quad x_2 - (x_1 + C_1) + h_2*Z \leq Z \\ x_2 - (x_1 + C_1) + h_2*Z \geq Z \end{array} \quad \begin{array}{c} h1 + h2 \leq 1 \\ h1 \leq1 \\ h1 \geq0 \\ h2 \leq1 \\ h2 \geq0 \end{array} \quad Z = Unreachably-Large $$

$\endgroup$

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.