Combinatorial optimization 100% sure
Based on upper and lower bounds, when do we explore a sub branch? - answer-When the lower bound
is less than the upper bound (maximisation)
Can you solve a dual problem with the two phase simplex? - answer-Yes you can
Define branch and bound - answer-An enumerative procedure for solving combinatorial optimisation
problems to optimality (aka finding an exact solution)
Describe the cutting plane method - answer-Adding extra linear constraints (called cutting planes) to cut
off parts of the feasbile region that we know cannot contain any integer solutions
Does branch and bound provide us with a guarantee for solution values? - answer-Yes
For a maximisation problem, what is the initial LB value? - answer-negative infinity
For a minimisation problem, what is the initial UB value? - answer-positive infinity
Frequently, what does a stronger formulation look like? - answer-One where there are more individual
constraints rather than multiplying by a constant to reduce the number of constraints
Given two IPs with the same feasible region, how can we compare their strength? - answer-By analysing
their LP relaxation regions
How can a basic feasible system be used to obtain a feasible solution? - answer-Every non basic is zero
and each basic is their RHS value
How can we deal with infeasible problems? - answer-Modify the formulation by relaxing or removing
some of the constraints
, How can we determine the change in cost in network simplex? - answer-Multiply the cij (reduced cost)
value by the arc cost
How can we estimate the value of node in B&B that we have discounted due to penalties? - answer-The
UB value of the parent node - the penalty value
How can we know if a problem is unbounded? - answer-If the entire pivot column is negative
How do we avoid cycling in the simplex method? - answer-always choose the smallest index when there
are ties
How do we deal with minimisation problems? - answer-We maximise -z!
How do we deal with unrestricted variables? - answer-We replace it by a difference of two new >= 0
variables representing the positive and negative difference (positive component - negative component)
How do we determine the value for M with disjunctive constraints? - answer-Maximise the modelled
equations and then take the maximum of the difference between the inequalities constants
How do we know if a problem in the dual simplex method is infeasible? - answer-If all elements in the
pivot row are >= 0
How do we solve problems with the graphical method? - answer-Moving the objective line without
changing its slope, the solution being the final point of contact with the solution region
how do you calculate the B&B guarantee for maximisation? - answer-alpha = LB/UB, where the best
solution so far is greater than or equal to alpha*true optimal
how do you calculate the B&B guarantee for minimisation? - answer-beta = UB/LB, where the best
solution so far is less than or equal to beta*true optimal
How does the first phase of two phase simplex generate a BFS - answer-by introducing artificial variables
Based on upper and lower bounds, when do we explore a sub branch? - answer-When the lower bound
is less than the upper bound (maximisation)
Can you solve a dual problem with the two phase simplex? - answer-Yes you can
Define branch and bound - answer-An enumerative procedure for solving combinatorial optimisation
problems to optimality (aka finding an exact solution)
Describe the cutting plane method - answer-Adding extra linear constraints (called cutting planes) to cut
off parts of the feasbile region that we know cannot contain any integer solutions
Does branch and bound provide us with a guarantee for solution values? - answer-Yes
For a maximisation problem, what is the initial LB value? - answer-negative infinity
For a minimisation problem, what is the initial UB value? - answer-positive infinity
Frequently, what does a stronger formulation look like? - answer-One where there are more individual
constraints rather than multiplying by a constant to reduce the number of constraints
Given two IPs with the same feasible region, how can we compare their strength? - answer-By analysing
their LP relaxation regions
How can a basic feasible system be used to obtain a feasible solution? - answer-Every non basic is zero
and each basic is their RHS value
How can we deal with infeasible problems? - answer-Modify the formulation by relaxing or removing
some of the constraints
, How can we determine the change in cost in network simplex? - answer-Multiply the cij (reduced cost)
value by the arc cost
How can we estimate the value of node in B&B that we have discounted due to penalties? - answer-The
UB value of the parent node - the penalty value
How can we know if a problem is unbounded? - answer-If the entire pivot column is negative
How do we avoid cycling in the simplex method? - answer-always choose the smallest index when there
are ties
How do we deal with minimisation problems? - answer-We maximise -z!
How do we deal with unrestricted variables? - answer-We replace it by a difference of two new >= 0
variables representing the positive and negative difference (positive component - negative component)
How do we determine the value for M with disjunctive constraints? - answer-Maximise the modelled
equations and then take the maximum of the difference between the inequalities constants
How do we know if a problem in the dual simplex method is infeasible? - answer-If all elements in the
pivot row are >= 0
How do we solve problems with the graphical method? - answer-Moving the objective line without
changing its slope, the solution being the final point of contact with the solution region
how do you calculate the B&B guarantee for maximisation? - answer-alpha = LB/UB, where the best
solution so far is greater than or equal to alpha*true optimal
how do you calculate the B&B guarantee for minimisation? - answer-beta = UB/LB, where the best
solution so far is less than or equal to beta*true optimal
How does the first phase of two phase simplex generate a BFS - answer-by introducing artificial variables
