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 ...
how do we solve problems with the graphical method
in the two variable case what are three notable f
what type of inequality is a surplus variable usee
Written for
Combinatorial Optimization
All documents for this subject (1)
Seller
Follow
aob
Content preview
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
The benefits of buying summaries with Stuvia:
Guaranteed quality through customer reviews
Stuvia customers have reviewed more than 700,000 summaries. This how you know that you are buying the best documents.
Quick and easy check-out
You can quickly pay through credit card or Stuvia-credit for the summaries. There is no membership needed.
Focus on what matters
Your fellow students write the study notes themselves, which is why the documents are always reliable and up-to-date. This ensures you quickly get to the core!
Frequently asked questions
What do I get when I buy this document?
You get a PDF, available immediately after your purchase. The purchased document is accessible anytime, anywhere and indefinitely through your profile.
Satisfaction guarantee: how does it work?
Our satisfaction guarantee ensures that you always find a study document that suits you well. You fill out a form, and our customer service team takes care of the rest.
Who am I buying these notes from?
Stuvia is a marketplace, so you are not buying this document from us, but from seller aob. Stuvia facilitates payment to the seller.
Will I be stuck with a subscription?
No, you only buy these notes for $8.99. You're not tied to anything after your purchase.
