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