Mutually Exclusive Alteratives

A group of decision variables in which only one is allowed to be true are mutually exclusive alternatives. This restriction can be written as $$ x_n,\dots,x_m \le 1 $$ where $x_n,\dots,x_m$ are the mutually exclusive alternatives.

Contingent Variables

If a variable requires another variable to be 1 in order to take the value 1, it is a contingent variable. This restriction can be written as $$ x_1 \le x_2 $$ where $x_1$ is contingent on $x_2$.

Either-Or Constraints

Sometimes we would like to require one of two constraints in a LP problem to hold, but not necessarily both. Using an auxiliary binary variable, this can be formulated as $$ \begin{aligned} 2x_1 + 3x_2 &\le 4 + My \\ 5x_1 + 2x_2 &\le 5 + M(y-1) \end{aligned} $$ where $M$ is a sufficiently large number, $y$ is a binary variable and $2x_1 + 3x_2 \le 4$ and $5x_1 + 2x_2 \le 5$ are the two restrictions of which one should always be true.

K out of N Constraints

A more general case of the either-or constraints would be a situation where K out of N constraints should be required to hold. In this case we introduce a binary variable for each constraint and add an extra constraint on their sum. That is $$ \begin{aligned} a_{11} x_1 + \dots + a_{n1} x_n &\le d_1 + M y_1 \\ & \vdots \\ a_{n1} x_1 + \dots + a_{nm} x_n &\le d_n + M y_n \\ \sum_{i=1}^{N} y_i &= N - K \end{aligned} $$ where $y_1 ,\dots, y_n$ are the auxiliary binary variables and $M$ is a sufficiently large number.

N Possible Values

From time to time it is desireable to allow a linear combination of the decision variables to take on values from a given set. This can be accomplished by assigning an auxiliary binary variable for each option in the set and then require their sum to be 1. $$ \begin{aligned} a_1 x_1 + \dots + a_n x_n &= d_1 y_1 + \dots + d_m y_m \\ \sum_{i=1}^{m} y_i &= 1 \end{aligned} $$

Fixed-Charge Problem

The start of an activity might require a fixed charge or setup fee. We can now model this using an auxiliary binary variable. Assume the activity $x_j$ requires a startup cost of $s_j$, $c_j$ is the original coefficient of $x_j$ in the objective function and $M$ is a sufficiently large number. The startup fee can be introduced by changing the objective function to include $s_j y_j$, so that $$ Z = c_j x_j + s_j y_j + \cdots$$

To make sure $y_j = 0$ must imply $x_j = 0$ we also introduce the restriction $$ x_j \le M y_j $$

Notice that $y_j$ will never be 1 unless $x_j$ is greater than 0 because $x_j = 0$ would allow us to select $y_j = 0$ which in turn gives us a better value for the objective function.

Binary Representation of Integer Variables

If a problem mostly consists of binary variables and only a few integer variables, it might be more efficient to solve the problem if the integer variables can be represented using binary variables. This requires a pair of bounds on the original variable.

Say $0 \le x_j \le 7$. We introduce three new (binary) variables $y_1$, $y_2$ and $y_3$, and perform the substitution $$ \begin{aligned} x_j &= 2^0 y_1 + 2^1 y_2 + 2^2 y_3 \\ &= y_1 + 2 y_2 + 4 y_3 \end{aligned} $$ We have now replaced $x_j$ by three binary variables.

Example: Relaxed BIP problem

Given the problem $$ \begin{aligned} \text{maximize} \quad Z = &3 x_1 + 4 x_2\\ \text{subject to} \quad &3 x_1 + 6 x_2 \le 8 \\ &3 x_1 + 3 x_2 \le 6 \\ &x_1, x_2 \quad binary \end{aligned} $$ the LP relaxation would be $$ \begin{aligned} \text{maximize} \quad Z = &3 x_1 + 4 x_2\\ \text{subject to} \quad &3 x_1 + 6 x_2 \le 8 \\ &3 x_1 + 3 x_2 \le 6 \\ &0 \le x_1, x_2 \le 1 \end{aligned} $$

For BIP problems

Repeat the following three steps until no nodes are left in the set. The incumbent at the end, if any, is the optimal solution to the problem.

IP Problems

The same steps can be used to calculate the solutions for a general IP problem as well, but with some minor differences.

Multiple Solutions

The above method only finds one optimal solution. If all optimal solutions are to be found, some adjustments should be made:

• We should keep a set of incumbents instead of a single incumbent
• A solution is added to the incumbents if it is equally good as the ones there already.
• If a solution better than the ones in the incumbent set is found, the set is replaced by a set consisting of the better solution.

Fixed-Time Incrementing

Using this method, the clock always increases a given amount each iteration. In short:

1. Advance the time by a small (fixed) amount.
2. Determine what events occur and calculate the new state.

Be sure to pick a sufficiently small interval!

Next-Event Incrementing

Jump from one event to the next directly.

1. Determine the next event and advance the time accordingly.
2. Calculate the new state.

Congruential Methods

This is the most popular method for generating random numbers. All start out with one or more seeds, that is random numbers, and generates a sequence of (apparently) random numbers. As all the numbers in the sequence can be calculated from the seed(s), the numbers are not truly random, but pseudo-random.

The next number in the sequence is given by a recurrence relation, where the initial numbers are the seed(s). Different versions are in use:

Multiplicative Congruential Method

$x_{n+1} = ax_n \bmod m$

Additive Congruential Method

$x_{n+1} = (x_n + x_{n-1}) \bmod m$

Mixed Congruential Method

$x_{n+1} = (ax_n + b) \bmod m$

where $a, b < m$ and other choices for $x_{n-1}$ are also possible.

Notice that the constants in the formulas must be chosen with care to ensure all possible numbers appear in the sequence. Also remember that the cycle length of the sequence is $m$ or less, depending on the numbers.

This method obviously generates random integers. A random number, $r_c$, from a continuous uniform distribution can be aquired from a random integer $r_d$ using this formula: $$r_c = \frac{r_d + \frac{1}{2}}m$$

In order for this to be a valid approximation, $m$ has to be sufficiently large (which is more often than not the case for computer based generators).

Inverse Transformation Method

We would often like to transform a uniform source of random numbers into a different distribution. The required transform is the inverse cumulative distribution for the desired distribution, that is $$X = F^{-1}(R)$$ where $R$ is the uniformly distributed stochastic variable, $X$ is output with the desired distribution and $F^{-1}(R)$ is the inverse cumulative distribution of $X$.

Acceptance-Rejection Method

We can also transform a uniformly distributed input into any other distribution by discarding numbers.

Using this method, we generate a random number $x$ (from a uniform distribution) and use this value with a probability $f(x)$ where $f(x)$ is the desired distribution. Repeat the process until a number is accepted.

This generates more numbers, but is still faster and easier to handle for some distributions.