15.053 Lecture Notes - Lecture 3: Regin, Master Of Medicine, Linear Programming
Document Summary
Input: a set of variables x , , x and a set of linear inequalities and equalities, and a subset of variables that is required to be integer. Feasible solution: a solution x" that satis es all of the inequalities and equalities as well as the integrality requirements. Example: maximize constraint 1: 5x + 8y 24 constraint 2: x, y 0 and integer. Rule of thumb: integer programming can model any of the variable and constraints that you really want to put into a linear program, but can"t. More dif cult to model and can be much more dif cult to solve. Some very large integer programs can be solves. Mixed integer linear programs, meaning that x 0 and integer for some or all j. Pure integer programs, meaning that x 0 for every j. Binary integer programs, meaning that x = {0, 1} for every j. You have n items to choose from to put into your knapsack.
