Linear and Integer Programming

Linear programming is a mathematical method used to find the maximum or minimum value of a linear objective function, subject to a set of linear inequality or equality constraints. It can be used to optimize the allocation of limited resources and is commonly used in business and economics.

Integer programming is a variant of linear programming where the variables are required to be integers rather than continuous values. This makes integer programming more difficult to solve than linear programming, as it is not always possible to find integer solutions for certain problems. However, integer programming is useful for modeling problems where only integer values are allowed, such as the number of items that can be produced or the number of employees that can be hired.

Both linear programming and integer programming can be solved using a variety of algorithms, including the simplex algorithm and branch and bound.

Linear programming

We left out one very important polynomial time technique last week as it deserves a class of its own. That is linear programming, the process of representing a problem using a certain form and then using a standard approach (usually a solver) to tackle it.

Linear programming involves optimizing a linear objective function subject to a set of linear inequality or equality constraints. It can be used to solve problems such as finding the minimum cost to produce a certain number of products or finding the maximum profit given certain constraints.

Integer programming is a variation of linear programming where some or all of the variables must be integers. This can be used to solve problems such as finding the minimum number of coins to give as change or scheduling problems where resources must be assigned in whole units.

Both linear and integer programming can be solved using algorithms such as the simplex algorithm or the branch and bound method. These algorithms are efficient and widely used in practice to solve a wide variety of optimization problems.

This technique is one of the earlier forms of combinatorial optimisation and involves minimising (or maximising) a linear function, subject to a number of linear constraints.

Integer programming is a generalization of linear programming in which some or all of the variables must be integers. This is often used to model problems where the values of the variables have to be whole numbers, such as in the case of counting problems. The algorithms used to solve integer programming problems are similar to those used for linear programming, but they are generally slower and more complex.

The notion of a linear function, means that the function must draw straight lines (or planes/hyperplanes) when drawn on a graph. This is always the case as long as we do not multiply our variables by one another (or by themselves)

Linear programming is a powerful tool and is used in a wide range of applications including resource allocation, scheduling and manufacturing. It is also a basis for integer programming, which involves finding an optimal solution using only integer values, rather than continuous values. Integer programming is useful in situations where the variables must be integers, such as when the variables represent discrete quantities.

A simple example

Maximise            3x + 4y - z

Subject to            x + y                       <= 12

                                     z        >= 3

This problem is asking us to find the maximum value of the function 3x + 4y - z, while ensuring that the values of x and y do not exceed 12 when added together, and that the value of z is at least 3.

To solve this problem, we can use a linear programming solver, which will find the optimal solution for us. In this case, the optimal solution would be the values of x, y, and z that give us the maximum value of 3x + 4y - z while still satisfying the constraints.

The function to be maximised (or minimised) is called the objective function and we want to find the largest (or smallest) value for it which satisfies all the constraints.

Linear programming problems are typically solved using the simplex algorithm, which is a polynomial time algorithm for finding the optimal solution. Integer programming is a variant of linear programming where the variables are required to take on integer values. This can be more difficult to solve as it requires more computation, but there are specialised algorithms for solving integer programming problems efficiently.

A little geometry and the simplex algorithm

The solution to a linear programming problem is always at one of the vertices of the feasible region, which is the region defined by all the constraints. This is because if we are at any other point within the region, we can always move to a vertex which would increase the value of the objective function.

The simplex algorithm is a method for finding the optimal vertex of the feasible region, which is either the vertex with the maximum value of the objective function (in the case of maximization) or the vertex with the minimum value of the objective function (in the case of minimization). The algorithm works by starting at a vertex and moving to a neighbouring vertex that improves the value of the objective function, until it reaches an optimal vertex.

The advantage of representing a problem using linear functions + constraints is that the optimum (maximum or minimum) solution is always

at a corner (or vertex) of the feasible region - that is, the region which satisfies all the constraints. This is because the objective function is linear and so its graph will always be a straight line.

●     On the surface of the shape formed by the constraints (called the ‘feasible region’)

This means that we only need to check the values at the vertices, which will be a polynomial number of them. The simplex algorithm does this.

Note that the feasible region will always be a convex shape, as the constraints are themselves linear.

A variant of this technique is integer programming, which is the same as linear programming but with the added constraint that the variables must be integers. This can be much harder to solve and there is no general polynomial time solution.

●     Can be found at one of the corners

○     of the feasible region (this is always the case because linear functions can only ever draw straight lines).

○     This means that we only have to check the vertices of the feasible region in order to find the optimum solution. This is the idea behind the simplex algorithm, which solves linear programming problems by iteratively moving from one vertex of the feasible region to another, always improving the value of the objective function.

●     Reachable by a simple ‘hill climbing’ or ‘iterative improvement’ technique

The simplex algorithm is an example of an iterative improvement algorithm that is used to solve linear programming problems. It works by starting at a corner of the feasible region and iteratively improving the solution until it reaches an optimal one. It does this by finding the next corner that results in a better solution and repeating the process until no further improvement is possible. The algorithm terminates when it reaches a corner that is a local maximum or minimum, which is also the global maximum or minimum for the objective function within the feasible region.

○     Start at a corner and keep moving to a neighbouring corner with better objective value

This is the basis of the simplex algorithm, which is a popular method for solving linear programming problems. The algorithm starts at a corner of the feasible region and iteratively moves to a nearby corner that improves the objective function. This process is repeated until the optimal solution is reached.

Simplex algorithm

The simplex algorithm is of some theoretical interest as it can be used to solve linear programming problems in polynomial time, which was a major breakthrough when it was first developed. It is also widely used in practice, as it is relatively easy to implement and can solve large problems efficiently.

Linear programming has many practical applications, including finding the optimal allocation of resources, such as time and money, in business and logistics problems. It is also used in economics, engineering and many other fields.

Integer programming is a generalization of linear programming, where some or all of the variables are restricted to be integers. These problems are generally more difficult to solve than linear programming problems, as the feasible region is no longer a continuous space but rather a set of discrete points. However, integer programming can still be solved in polynomial time using specialized algorithms.

●     It has been shown to run in exponential time in the worst case whilst still being very efficient in practice.

●     It is also used in integer programming, which is a generalization of linear programming where the variables are required to be integers rather than continuous. This can be useful for problems that require discrete solutions, such as scheduling or resource allocation.

●     ● Linear programming and integer programming are widely used in various fields such as economics, computer science, and operations research. They have many applications, including optimization of production and transportation, portfolio optimization in finance, and optimization of supply chain management.

●     ● There are many different algorithms and solvers available for linear and integer programming, including the simplex algorithm, interior-point methods, branch and bound, and cutting plane methods. In practice, it is often best to use a solver rather than implementing the algorithm yourself as they are highly optimized and can handle large scale problems efficiently.

●     There are polynomial time alternatives, called interior point methods (which cross the middle of the feasible region rather than the edges) but these often perform less efficiently than the simplex method in practice.

Linear programming is just one type of optimization problem, another important one is integer programming, which is similar to linear programming but requires the variables to be integers rather than real numbers. Like linear programming, integer programming can be used to represent and solve a wide range of optimization problems, including scheduling, resource allocation, and network design problems. The branch of mathematics that deals with the optimization of integer variables is called integer programming, and it is an important area of research in operations research and computer science.

●     It is an iterative improvement technique which guarantees to find the optimum solution

It works by starting at a corner of the feasible region and moving to a neighbouring corner which has a better objective value. This process is repeated until no such move is possible, at which point the algorithm has reached the optimal solution.

○     Because of the linear constraints, it never gets ‘stuck’ in suboptimality.

It is quite easy to implement and is widely available in libraries and software packages.

Here is a simple implementation of the simplex algorithm in Python:

def simplex(c, A, b, basic_vars):

  """

  Solves the linear programming problem:

  maximize    c^T x

  subject to  Ax <= b

              x >= 0

  using the simplex algorithm.

  Args:

    c: coefficients of the objective function

    A: constraints matrix

    b: constraints vector

    basic_vars: indices of the basic variables

  Returns:

    A tuple (optimal_value, optimal_solution).

  """

  n = len(c)  # number of variables

  m = len(b)  # number of constraints

 

  # initialize the tableau

  tableau = [-c] + [list(row) for row in A]

  tableau.append(b)

  tableau = [[tableau[i][j] if j < n else 0 for j in range(n+m+1)]

             for i in range(m+1)]

  for i in range(m):

    tableau[i][n+i] = 1

  tableau[m][n+m] = 1

 

  while True:

    # find the entering variable (minimum positive ratio)

    min_ratio = float("inf")

    entering_var = None

    for j in range(n):

      if tableau[-1][j] > 0:

        min_ratio = min(min_ratio, tableau[-1][-1]/tableau[-1][j])

        entering_var = j

    if min_ratio == float("inf"):

      # optimal solution found

      return tableau[-1][-1], [tableau[i][-1] for i in range(m)]

 

    # find the leaving variable (minimum positive ratio)

    min_ratio = float("inf")

    leaving_var = None

    for i in range(m):

      if tableau[i][entering_var] > 0:

        min_ratio = min(min_ratio, tableau[i][-1]/tableau[i][entering_var])

        leaving_var = i

    if min_ratio == float("inf"):

      # unbounded solution

      return float("inf"), []

 

    # pivot

    pivot = tableau[leaving_var][entering_var]

    tableau[leaving_var] = [x/pivot for x in tableau[leaving_var]]

    for i in range(m+1):

      if i != leaving_var:

        multiple = tableau[i][entering_var]

        tableau[i] = [tableau[i][j] - multiple*tableau[leaving_var][j]

                      for j in range(n+m+1)]

 

○     We’ll investigate this much more later, with problems that don’t fit such a convenient shape.

This implementation of the simplex algorithm takes as input the coefficients of the objective function c, the constraints matrix A, the constraints vector b, and the indices of the basic variables basic_vars. It returns a tuple containing the optimal value and the optimal solution.

solution by finding a corner of the feasible region which gives an improved objective value and then updating the values of the variables to reflect this new corner. This process is repeated until no more improvement is possible.

To implement the simplex algorithm in Python, we can use the PuLP library. The following example shows how to use PuLP to solve the linear programming problem defined above:

# Import PuLP and create the problem object

import pulp

prob = pulp.LpProblem("Maximisation Problem", pulp.LpMaximize)

 

# Define the variables

x = pulp.LpVariable("x", lowBound=0)

y = pulp.LpVariable("y", lowBound=0)

z = pulp.LpVariable("z", lowBound=3)

 

# Define the objective function

prob += 3*x + 4*y - z

 

# Define the constraints

prob += x + y <= 12

 

# Solve the problem

status = prob.solve()

 

# Print the solution

print(f"Optimal solution: {pulp.value(prob.objective)}")

print(f"x = {x.varValue}")

print(f"y = {y.varValue}")

print(f"z = {z.varValue}")

This code will output the optimal solution, as well as the values of the variables at the optimal solution. Note that we have defined the variables x, y, and z with lower bounds of 0, 0, and 3 respectively, which corresponds to the inequality constraints in the problem definition.

Integer programming

Linear programming works excellently when we have a continuous objective function and constraints. It becomes less effective if any of the variables must take on certain values (e.g. must be integers or booleans)

In this case, we can use integer programming, which is similar to linear programming but with the added restriction that some or all of the variables must take on integer values. This makes the problem more difficult to solve as it is no longer possible to simply move from one corner of the feasible region to another, as the corners may not correspond to integer solutions. As a result, integer programming problems can be much harder to solve than their linear programming counterparts and may require more specialized algorithms and/or heuristics.

The difficulty with this is that it is much harder to find the optimal solution in this case, as we can no longer use the simplex algorithm. Instead, we must use integer programming techniques which involve solving a series of linear programming problems. These techniques are much slower in practice, although they still run in polynomial time.

●     The optimum is not necessarily at a corner

The optimum solution may not be a feasible solution, because it may not satisfy the integrality constraints

●     It cannot always be found by rounding the optimum corner up or down

This is where integer programming comes in. It is a variant of linear programming where we add the additional constraint that all variables must be integers. This is a much harder problem to solve and there is no guarantee that we can find the optimal solution in polynomial time, even though it is still in the class NP. In practice, integer programming solvers can be very effective but can sometimes take a long time to find a solution, especially for larger problems.

What does this mean?

 

We can represent instances of subset-sum as an integer programming problem

This means that when we have variables that must take on certain values (e.g. must be integers or booleans), the optimal solution may not be at a corner of the feasible region and may not be found by simply rounding the optimal solution to the nearest corner. This makes finding the optimal solution more difficult and requires a different approach.

●     Represent the numbers in the set by a vector x, whereby x_i is the ith number in the set

The problem becomes finding the solution to a linear program that also satisfies the condition xi ∈ Z for all i

●     Create a boolean vector s, where s_i is 1 if number x_i is in the subset and 0 otherwise.

●     Convert the problem into a linear programming problem by replacing the ‘is in’ constraint with an inequality: si - xi >= 0

●     This will allow si to be 1 when xi is in the set and 0 otherwise.

●     Solve the linear programming problem using a solver.

●     If the optimum value of the objective function is not an integer, we can simply round it to the nearest integer.

●     If the optimum value is an integer but not all variables are 0 or 1, we can add additional constraints to force the variables to be 0 or 1. This will give us an integer solution to the problem.

●     If the problem is still not solved, we can try again with a modified objective function that penalizes non-integer solutions. This is called the branch and cut method.

 

●     Represent the target value by the constant t.

We can then create a set of linear constraints: ○ For every xi, we can have a constraint si = 1 if xi <= t, or si = 0 if xi > t ○ We can also add the constraint that the sum of s must equal k, since we want to select exactly k numbers. ● We can then use a linear programming solver to find the solution to this problem. However, the solution may not necessarily have integer values for the variables si. In this case, we can use techniques such as rounding or adding additional constraints to try to force the solution to be integer. This is known as integer programming.

Minimise

Subject to:  s  ∊ {0,1}, objective function nonnegative

If the minimum value of the objective function is 0, subset sum returns true

Integer programming

Integer programming is NP-Hard (in fact it is NP-Equivalent), whereas linear programming problems are solvable in polynomial time.

This means that integer programming problems are at least as hard as the hardest problems in NP, and it is unlikely that there exists a polynomial time algorithm for solving them. However, there are specialized algorithms and heuristics that can often find good solutions to integer programming problems in practice, even though they may not be guaranteed to find the optimal solution.

However, because integer programming is such a common business problem, there exist powerful solvers which can often solve substantial problems in practice. The technique is much more effective than brute force search even though it is exponential time.

There are several ways to solve integer programming problems, including branch and bound, cutting planes, and branch and cut.

Branch and bound is a method that involves dividing the search space into smaller subproblems and solving each one individually. This is done by fixing some of the variables to specific values and then solving the resulting problem as a linear program. The solutions from these subproblems are then compared, and the best one is chosen as the final solution.

Cutting planes involves adding additional constraints to the problem to eliminate infeasible solutions. These constraints are called cuts, and they are added iteratively until a feasible solution is found.

Branch and cut is a hybrid method that combines elements of both branch and bound and cutting planes. It involves both dividing the search space into smaller subproblems and adding additional constraints to eliminate infeasible solutions.

In general, integer programming solvers use a combination of these techniques to find the optimal solution to a problem. They also often use heuristics to guide the search and improve the efficiency of the algorithm.

●     The solvers commonly use a mixture of cutting plane techniques, branch and cut methods and heuristics to solve the problem (will elaborate in class)

●     In the worst case, this produces an exponential number of subproblems to solve

However, in practice, these solvers are able to solve many large problems in a reasonable time. In fact, integer programming is one of the most widely used combinatorial optimization techniques in the industry, particularly in the field of operations research. It is used to solve a wide range of problems, including resource allocation, scheduling, and design problems.

Solution techniques

So at this point we have the following items in our toolkit:

●     If our new problem is solvable in polynomial time

○     Divide and conquer

○     Greedy algorithm

○     Dynamic programming

○     Linear programming

○     Etc.

●     If it is NP-Complete (or NP-Equivalent)

○     Brute force search (very bad)

○     Transform it into an instance of Integer Programming and use a solver on it (might be better)

■     Because IP is NP-Equivalent, we can transform any NP-Equivalent problem into it!!!

Task

Use Excel to tackle this instance of the vertex cover problem:

●     To recap, the vertex cover problem involves finding the minimum sized set of nodes, such that every edge is incident on at least one node of the set.

●     Hint: use a binary vector to indicate whether a particular node is in the set or not.