Gurobi linear programming
Part 2. Computational
For each one of the following problems, submit your code as a .ipynb file. You will receive credit
only if your code runs with no error, generates the requested output, and produces the correct
Copyright By PowCoder代写 加微信 powcoder
solution to a test instance. Your code should in each case read in an LP contained in a file named
1p.mps and solve it either as a pure IP, as in (5), or, using the list of integer variables in a file
named integer _variables.txt, solve it as a MIP (in which case you will receive extra credit).
Consider 0-1 integer (linear) programs of the form
max{c”x : Ax < b,x € {0, 1177
where A is an m x n matrix, and b is nonnegative; all parameters are integers.
1. Implement an LP-based branch-and-bound algorithm to solve (5). Use depth-first search (re-
cursive function) to traverse the search tree. and branch on a (fractional) variable that is closest
to 0 or 1. To solve the LP relaxation problems call the GUROBI solver. At every node of
the tree, your code should output (1) node number, (2) LP relaxation solution, (3) lower and
upper bounds, and (4) the processing result, i.e., branching, pruning by infeasibility, pruning by
optimality, or pruning by bound. At the end of the process, the optimal solution (and value) to
the integer program as well as the total number of processed nodes should be reported. Your
submission name should be BB_lastName_firstNameInitial, e.g., BB Hosseinian M.ipynb.
Implement a cutting plane algorithm to solve (5) with only Gomory cuts. The algorithm starts
by solving the LP relaxation of the original problem; at each iteration, it derives one Gomory cut
based on the optimal Simplex tableau, appends it to the formulation, and resolves the resultant
LP. The process continues until an integer solution is obtained. To solve the LPs call the
GUROBI solver. At each iteration, your code should output the LP relaxation solution and the
corresponding optimal value as well as the generated Gomory cut. At the end of the process,
the optimal solution (and value) to the integer program as well as the total number of cuts
applied should be reported. Your submission name should be CP 1astName firstNameInitial
e.g., CP Hosseinian M.ipynb.
Traveling Salesman Problem (TSP)
is is perhaps the most notorious problem in Operations Research because
is so easy to explain, and so tempting to try and solve. A salesman must
it each of n cities exactly once and then return to his starting point. The
ne taken to travel from city i to city j is Gij. Find the order in which he
ould make his tour so as to finish as quickly as possible.
This problem arises in a multitude of forms: a truck driver has a list of
ents he must visit on a given day, or a machine must place modules on
inted circuit boards, or a stacker crane must pick up and depose crates.
w we formulate it as a BIP.
•finition of the variables.
= 1 if the salesman goes directly from town i to town j, and zij = 0
herwise. (ty is not defined for i = 1,. ..,n.)
efinition of the constraints.
e leaves town i exactlv once:
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com