MATH 441 LP/ILP Applications and Project Ideas, Fall 2017

This page concerns some sample applications of LPs and ILPs that may give you project ideas.

We shall indicate problems that are NP-complete, meaning that an exact optimum solution is thought to be difficult to find in the general case. However, in many practical situations these problems may not be difficult to solve.

You will need to know what is meant by a graph and a bipartite graph. I will explain these concepts in class.

Below I will use: [CCZ] to refer to the "Integer Programming" by Conforti, Cornuejols, and Zambelli.

Linear Programming The following problems are standard applications of linear programming:
  • Resource/product problems (input/output problems) (the problem is in standard form, and typically all coefficients and constants are non-negative).
  • Matrix games, such as stone/paper/scissors, poker, etc. (See, e.g., Chvatal , Chapter 15, or Vanderbei, Chapter 11).
  • Curve fitting, finding the smallest sum of absolute values of the errors (e.g. Chapter~12 of Vanderbei).
  • Curve fitting, finding the smallest maximum absolute value of the errors.
  • Feasibility of baking cookies: baking requires n tasks, and some tasks require that other tasks occur a certain amount of time beforehand (e.g., "preheat oven" must occur 15 minutes before "put cookie sheet in oven"). Find the smallest feasible time for baking cookies.
  • Weighted Bipartite Matching (Also called "The Assignment Problem" when the number of left and right vertices are the same.) You are given a bipartite graph where each edge as a utility. You seek the matching whose sum of edge weights is maximum. This is really an ILP, where each edge has a variable that is 1 if it occurs in the matching and 0 otherwise. However, the simplex method (but not necessarily other methods) run on the corresponding LP always produces a solution to the ILP. This is due to "total unimodularity" of the matrix involved in the formulation of the LP (see Chapter 4 of [CCZ]).
    Basic Packing Type Problems Many standard problems related to "packing" can be found in Sections 2.1 to 2.4 of Conforti, Cornuejolis, and Zambelli.
  • These include the Knapsack Problem (see [CCZ], Section 2.1), Cutting Stock (see [CCZ], Section 2.3), Set Packing, Covering, and Partitioning (see [CCZ], Section 2.4).
  • Application (Packing): you can buy sheets of wrapping paper of fixed width, each sheet has its own length and own price; you must wrap various gifts. For simplicity, each gift requires a certain length of wrapping paper (and the wrapping paper for each gift must be a cut to a certain length of paper: we don't allow fancier rectangular cuts). How much do we need to spend (assuming the wrapping papers are indistinguishable beyond their price and length)?
  • Application (Covering): You have n people, where each person has certain skills and demands a certain hourly wage. You want to choose a set of people whose sums of wages is a minimum, such that each skill is found in at least one person in the set.
  • Related application: The same setup as the previous problem, but some skills require more than one person (e.g., you need five people who are qualified to make espresso, two people qualified to take orders, etc.).
  • These problems are usually NP-complete (if stated in general enough terms).
    Graph Colouring You are given a graph, G=(V,E). Find the smallest number of colours needed to colour the vertices so that no two adjacenct vertices have the same colour (see pages 29-33 of this set of slides).
  • Variant: each edge in the graph has a cost. For a given number of colours, find the colouring such that minimizes the sum of the edge costs in the edges that have the same colour on its endpoints.
  • Applications: The vertices represent classes, and the edges represent the number of students taking both classes, the colours represent exam periods. You wish to minimize the sum of the number of exam conflicts.
  • Graph colouring is NP-complete; even determining whether or not a graph can be coloured with three colours is NP-complete.
  • Non-Linear Objectives There are some types of non-linear objective functions that can be written in linear terms, such as:
  • The maximum of linear functions: one introduces a new variable representing the maximum; similarly for the minimum of linear functions. This is done in game theory (see, e.g., Chvatal , Chapter 15, or Vanderbei, Chapter 11).
  • Progressive taxes: say you are taxed 0% on income below 15000, 10% on income between 15000-20000, and 95% on income over 20000. You can rewrite the single income as three different incomes, the first bounded by 15000, the second by 5000, and the third unbounded. If you earn 28000, you will presumably divided it 15000+5000+8000, but you could put all of your 28000 into the third type, taxed at 95%.
  • Project Ideas In addition to project ideas in: Prof. Anstee's Math 441 course last year and some examples discussed in class, here are some additional ideas:
  • You have to cut stock--say cut rolls of gift wrapping paper into certain sizes--for orders of gifts that come in over time. How much wrapping paper do you save by waiting for seven days to wrap gifts rather than wrapping orders day by day? This is a twist on the standard stock cutting problem.
  • Two companies have different types of resources needed to make products. How much do they gain by sharing resources? What types of policies regarding the sharing of resources give the highest gains?
  • One company pays certain wages to their employees based on their years of experience, and gains some utility based on the number of employees that have a certain amount of experience. A second company is about to open (with the same or similar utility function), and wants to lure some of the first companies employees away. What type of wages should it offer? Are there any strategies that are subtle?
  • Each spring farmers use resources to produce various food products (wheat, corn, etc.), based on last year's prices. In the fall people buy these products to make food dishes, each of which gives them certain amount of utility; the prices that people pay for each product is based on the marginal utility of the product to people (there are a number of possibly models). What happens over a few years, it the farmers' resources are at a fixed price? What happens if some resources change in price?
  • Meta Project Ideas For most simple applications of LP's or ILP's, there are a number of general things one can always consider. One is threshold phenomena: for example, if you are trying to schedule a fixed set of exams into exam slots with a minimum number of conflicts, then as the number of exam slots decreases, the number of conflicts may not change much until a certain number of exam slots--a threshold--at which point the number of conflicts increases greatly each time the number of slots decreases by one. Related questions can be asked relating to the sensitivity of certain model parameters (as in "sensitivity analysis" from Math 340).

    UBC Math Home| Joel Friedman Home| Course Materials