# TIØ4120: Introduction to Operations Research

# Integer programming

We need some new concepts:

- Integer variable
- Variable that can only take on integer values
- Binary variable
- Variable that can only take on the values 0 or 1, which can often be interpreted as true/false or yes/no.

## Integer Programming (IP)

An *integer (linear) programming problem* (IP problem) is a LP problem in which there exists at least one decision variable constrained to integer values.

If all the decision variables in a LP problem are required to be integers, the problem is a *pure integer programming problem*. If not, the problem would be a *mixed integer programming problem* (MIP problem).

*Notice*: Even though IP problems might seem simpler to solve than the usual (continuous) LP problems, they are often harder as we can no longer assume that the optimal solution will be a corner point feasable solution, thus the simplex method is no longer applicable.

## Binary Integer Programming (BIP)

A problem consisting of only binary variables is considered a *binary integer programming problem* (BIP problem).

A decision variable in a BIP is often named "descision" for short.

### 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

### 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

## Other Uses of Binary Variables

Binary variables are not only useful in BIP problems, but can also be used in other LP problem. When binary desicion variables are introduced to handle special constraints, the extra variables are *auxiliary binary variables*.

### 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

### 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

### 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.

### 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

To make sure

Notice that

### 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

## Relaxing IP problems

Some problems are too hard to solve exact, but it might still be possible to say something about the solution without actually calculating it. This can be done by relaxing the problem - removing appropriate constraints.

One way to relax an IP problem is to remove the integer constraint. The relaxed problem, the *LP relaxation* of the original problem, has a couple of interesting properties, which obviously follow from the fact that the relaxed problem has fewer rules than the original:

- If the relaxed problem has no solutions, nor does the original problem.
- The optimal value for the objective function in the relaxed problem is an upper bound for the objective function in the original problem.

Do also notice that any all-integer solution to a LP relaxed problem, is an optimal solution to the original problem, as it also satisfies the (removed) integer constraints.

### Example: Relaxed BIP problem

Given the problem

## The Branch-and-Bound Technique

As mentioned earlier, the simplex algorithm cannot be applied to IP problems. The branch-and-bound tecknique is an alternative approach where we create a tree (by branching) and eliminate entire subtrees using their bounds.

Throughout the algorithm, we will keep track of the best solution so far, the *incumbent*. The value of the objective function for this incumbent will be refered to as

We will also keep track of the current set of nodes. The first node is the original problem.

### 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.

#### Step 1: Calculate Bounds

For all nodes without a bound, we calculate the bound. This often done using the LP relaxation.

#### Step 2: Fathoming

We now want to get rid of as many nodes as possible. This is done by discarding, or *fathoming* the nodes we can assure do not contain a better solution than the one we have already got.

Loop through the nodes and discard all nodes where one of the following apply:
- Best bound is worse than the current

In case the last should apply, the solution is also the new incumbent (best solution so far).

#### Step 3: Branch

Select the last node considered which was not fathomed. We now want to find the first free variable,

Add the nodes to the set of nodes.

### 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.

# Simulation

Some problems are too hard or complex to be solved using analytical methods, in which cases it might be useful to *simulate* the problem. This approach is often used when considering stochastic systems.

Keep in mind that analytical methods are superior to simulation when applicable because - they provide insight into the underlying structure of the system and the cause-and-effect relations - requires less time and are more often more accurate

We will only consider discrete-event simulations in which changes appear instantaneously as continuous simulations tend to be very complex.

A simulation model can often be defined by

- State representation
- The way the state of the system is represented and what states are legal
- Possible events
- What events can happen and when
- Simulated clock
- Records the time
- Event generation method
- Generates events at appropriate points in time
- State transition function
- Returns the new state given the previous state and an event

*WARNING:* A common mistake when doing simulation is to choose way too small sample sizes as a result of lacking statistical analysis!

## Time Advance Methods

We can manage the time in two ways when doing simulation.

Remember that a warm-up period is required if we want to study values for the system in a steady-state condition.

### Fixed-Time Incrementing

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

- Advance the time by a small (fixed) amount.
- 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.

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

## Random Number Generation

For the simulation to be valid, we must use valid random numbers. Many ways of determining whether a sequence of numbers is suffeiciently random has been developed. In short: The probability of the next number in the sequence taking on a given value should be the same for all values.

In the context of simulation it is also assumed that the values are uniformly distributed, that is there is an equal chance for any number.

### 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

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

This method obviously generates random *integers*. A random number, *continuous* uniform distribution can be aquired from a random integer

In order for this to be a valid approximation,

### 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

### 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

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