Skip to content

Linear and Integer Programming Week 1

September 3, 2013

Coursera – Linear and Integer Programming starting Sept 2nd, 2013

Week one of this course provides visualizations of LP (linear programming) space and ILP (integer linear programming) space problems. First, the definition of Linear programming is: an optimization (maximum/minimum) of some objective linear function that must satisfy a collection of constraints. With a 2-dimensional representation of the “feasible region” (if it exists) which is defined by the constraints. Constraints can either be linear equalities or inequalities.

The visualization of the LP n-dimensional polyhedron demonstrated how the objective function can be moved inside the feasible region to the optimal solution(s). Setting the objective function to a particular location in the feasible region is called “level set” and the search process involves increasing the position while the function is still inside the feasible region. NOTE: The additional of contradictory constraints can turn a feasible region into an infeasible problem.

The next section covered the history of LP, and discussed it’s beginnings with the Fourier-Motzkin elimination method. The algorithms described in the history of LP were: Simplex (top 10 algorithms) and other Interior Point algorithms. The distinction between LP with real numbers (solvable in polynomial time) and ILP with integers only (solvable in exponential NP).

The last section was an explanation that was needed for one of the homework assignments: the Diet Problem (Stigler diet). I solved the problem using Excel, and it’s add-on “Solver” which was very easy to use. Another homework assignment testing your understanding and a pre-course knowledge test were also required.


From → Algorithms, General

Leave a Comment

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: