Reading...
Play button
Play button
Use LEFT and RIGHT arrow keys to navigate between flashcards;
Use UP and DOWN arrow keys to flip the card;
H to show hint;
A reads text to speech;
16 Cards in this Set
- Front
- Back
|
What are the three different kinds of integer programming models and how do they differ?
|
total, 0-1, and mixed.
|
|
|
Total Integer Model
|
all the decision variables are required to have integer solution values
|
|
|
0-1 Integer Model
|
all the decision variables have values of zero or one
|
|
|
Mixed Integer Model
|
some of the decision variables (but not all) are required to have integer solutions
|
|
|
What is a mutually exclusive constraint?
|
contingency that either one thing or another can be built, but not both. In order for the sum of x1 and x2 to be less then or equal to 1, either of the variables can have a value of 1, or both can equal 0.(x1+x2<=1
|
|
|
What is a multiple-choice constraint and how is it different from a mutually exclusive constraint?
|
If it is specificied that either one thing or the other MUST be built, but not both, the constraint would be an equation x1+x2=1. Solution would be either x1=1 or x2=1. Different from mutually exclusive in that in mutiple choice a facility must be chosen, in mutually exclusive an option doesnt have to be selected.
|
|
|
What is a conditional constraint?
|
when construction of one thing is dependent upon construction of another. Ex. a tennis center is dependent upon a pool being built, but doesnt mean tennis center will be built
|
|
|
Be able to explain how you formulate a conditional constraint.
|
ex. tennis center(x2) dependent on construction of pool(x1). x2<=x1.
x2 cant equal one unless pool equals one, if x1 equals 0 then x2 must equal 0. but, x1 can be = 1 and x2 = 0 |
|
|
What is a corequisite constraint and how is it different from a conditional constraint?
|
if one facility is constructed, the other facility WILL be constructed, and vice versa. x2=x1. x1 and x2 equal the same value, either 0 or 1. Diff from conditional constraint in the if one facility is constructed, the other MUST be built.
|
|
|
Rounding noninteger solutions up to the nearest integer value may result in what? What happens if you round down noninteger solutions values?
|
Rounding up can result in an infeasible solution. Rounding down ensures a feasible solution.
|
|
|
What is the traditional approach for solving integer programming problems? What is the major principle of this method?
|
branch and bound method. Major principle is that total sets of feasible solutions can be partitioned into smaller subsets of solutions. smaller subsets can then be evaluated systematically until best solution is found.
|
|
|
Who is credited with being the first individual to develop a systematic (algorithmic) approach for solving linear integer programming problems? What was this approach called?
|
Ralph Gomory, approach was called "cutting plane method"
|
|
|
Searching through all possible integer solutions is what type of approach? What is an example of this type of approach that conducts this search in an intelligent manner?
|
an enumerative approach. an example of an enumerative approach that conducts this search in an intelligent manner is branch and bound technique.
|
|
|
What are three popular applications of 0-1 integer programming? Be able to describe and model each type of problem.
|
Capital budgeting problem, fixed charge and facility location problem, and a set covering problem.
|
|
|
Capital Budgeting problem
|
project where store doesnt have enough space for both a computer deparment and clothing department.
x3+x4<=1 |
|
|
Fixed charge and facility location problem
|
project where company wants to know which of the six farms it should purchase. yi=0 if farm i is not selected, and 1 if farm i is selected. i=1,2,3,4,5,6
yi=0 or 1 |
