Introduction

Loading...

From the course by University of California San Diego

Advanced Algorithms and Complexity

310 ratings

University of California San Diego

Advanced Algorithms and Complexity

310 ratings

Course 5 of 6 in the Specialization Data Structures and Algorithms

You've learned the basic algorithms now and are ready to step into the area of more complex problems and algorithms to solve them. Advanced algorithms build upon basic ones and use new ideas. We will start with networks flows which are used in more typical applications such as optimal matchings, finding disjoint paths and flight scheduling as well as more surprising ones like image segmentation in computer vision. We then proceed to linear programming with applications in optimizing budget allocation, portfolio optimization, finding the cheapest diet satisfying all requirements and many others. Next we discuss inherently hard problems for which no exact good solutions are known (and not likely to be found) and how to solve them in practice. We finish with a soft introduction to streaming algorithms that are heavily used in Big Data processing. Such algorithms are usually designed to be able to process huge datasets without being able even to store a dataset.

From the lesson

Linear Programming

Linear programming is a very powerful algorithmic tool. Essentially, a linear programming problem asks you to optimize a linear function of real variables constrained by some system of linear inequalities. This is an extremely versatile framework that immediately generalizes flow problems, but can also be used to discuss a wide variety of other problems from optimizing production procedures to finding the cheapest way to attain a healthy diet. Surprisingly, this very general framework admits efficient algorithms. In this unit, we will discuss some of the importance of linear programming problems along with some of the tools used to solve them.

Introduction5:09

Linear Programming8:40

Linear Algebra: Method of Substitution5:36

Linear Algebra: Gaussian Elimination10:32

Meet the Instructors

Alexander S. Kulikov
Visiting Professor
Department of Computer Science and Engineering
Michael Levin
Lecturer
Computer Science
Daniel M Kane
Assistant Professor
Department of Computer Science and Engineering / Department of Mathematics
Neil Rhodes
Adjunct Faculty
Computer Science and Engineering

Hello, everybody,

welcome back to our course on advanced algorithms and complexity.

Today we're starting a new unit,

we're starting to talk about linear programming problems.

And in particular today we're going to give just a simple example of the sort of

problem that we will be trying to solve during this unit.

So imagine that you're running a widget factory and

you'd like to optimize your production procedures in order to save money.

Now these widgets, you can make them using some combination of machines and workers.

Now you have only 100 machines in stock, so you can't use more than that.

But you can hire an unlimited number of workers.

However, each machine that you're trying to use requires

two workers in order to operate it.

Additional workers can be building things on their own,

but machines they are using require two workers on them.

Now in addition to this,

each machine that you use makes a total of 600 widgets a day.

And each worker that's not currently involved in operating a machine makes

200 widgets a day.

Finally, the total demand for widgets is only 100,000 widgets a day.

So if you make any more than this,

they just won't sell, and that's no good for anybody.

So writing these constraints down in a reasonable way,

if we let W be the number of workers that we have.

And M the number of machines, we have a bunch of constraints.

The number of workers should be non-negative,

the number of machines should be between 0 and 100.

The number of workers needs to be at least twice the number of machines.

And then finally, 100,000 is at least 200 times the number of unoccupied workers.

That's W minus 2M, plus 600 times the number of the machines.

And so these constraints sort of constrain which allowable combinations we can have.

Now we can try and graph these constraints.

So here we've got a plane of possible values of M and

W that satisfy these constraints.

Now if we're just starting where M and W both need to be non negative,

we have this quadrant as the allowable values.

But when we require that M needs to be at least 100,

we're reduced to being in this strip here.

When we look at our constraint based on the total demand,

we find that M + W is at most 500.

And so we're now constrained to this region.

And we add the final constraint that the workers need to be at least

twice the number of machines.

We finally come to this diagram of possible configurations

of machines and workers that we can use.

What's next?

Profit, well suppose that profits are determined as follows.

Each widget that you make earns you a $1 but

each worker that you're hiring costs you $100 a day.

So the total profit that you get, then, in terms of dollars per day.

Well it's number of widgets, 200 workers minus twice machines,

plus 600 times number of machines, minus the total salaries you paid to workers,

100 times the number of workers.

So that's 100 times the number of workers plus 200 times the number of machines.

And if we want to plot that on our graph we can do it as follows.

So these lines that I've drawn are lines of equal profit.

There's a line with $30,000 a day, and then $40,000 a day, and

then $50,000 a day.

And sort of as you go from left to right, or

from bottom to top, you make more profit.

So what we're trying to do now is we're trying to say well,

what can we do to get the most profit?

And it turns out, the best you can do is at this point here.

Note that it's a corner of the allowable region,

it's where we have 100 machines and 400 workers.

And the total profit is $60,000 a day.

Now it's clear from this diagram that this is the best that you can do.

But if you actually want to prove it, there's a clever way you can do that.

So two of the constraints that we have,

one of them is that the number of machines is at most 100.

And another is that 200 times the number of machines plus 200 times

the number of workers is at most 100,000.

Now if we take 100 times the first constraint and add it to a half times

the second constraint, what you find is that 200 times the number of machines

plus 100 times the number of workers has to be at most 60,000.

And that says the profit that we make has to be at most 60,000.

And so this is a very convenient way to prove that the 60,000

that we could attain is actually the best we can do.

So in summary, what we did is we solved

this problem where we maximized this function, 200M + 100W.

Subject to the following list of five constraints.

And because the thing we're trying to maximize is a linear function, and

the constraints we have are linear inequalities,

this makes this an example of the type of problem we're going to be looking at.

That is, a linear program.

So come back next lecture and we'll sort of formally define this problem and

get us started on our investigation.

Explore our Catalog

Join for free and get personalized recommendations, updates and offers.

Coursera provides universal access to the world’s best education, partnering with top universities and organizations to offer courses online.

© 2019 Coursera Inc. All rights reserved.

Download on the App Store

Get it on Google Play