PROBLEM STATEMENT:1. You may use lp_solve program - a free-ware. You can download it from the followingweb site: http://lpsolve.sourceforge.net/5.5/2. If you want to use some other lp solver that is fine.3. Solve the following problem and write a report: a. What tool you are using (eg. lp_solve) ? b. features of the tool you are using (as for as lp program solving is concerned). c. The number of nodes for the following program should be at least 10. d. The number of edges should be at least 20. e. Assign some capacity to eache edge. f. Assign a unit cost for capacity. g. assign unit profit.* A telecommunications company sets up routes through its network to servecertain source-destination (S-D) pairs of traffic. We want to assign bandwidth toeach route, under the following conditions:• The routes are fixed and known in advance, each route goes through aknown set of links. (These sets can possibly overlap, as the routes mayshare links.)• Each link has a known available capacity, which cannot be exceeded by theroutes that use the link, in the sense that the sum of the route bandwidths onthe link cannot be more than the link capacity.• Assigning bandwidth to a route has a cost. This cost is proportional to thebandwidth assigned. The cost of unit bandwidth is known for each route(may be different for different routes).• Each route generates a profit, due to the traffic it carries. The profit of eachroute is proportional to the bandwidth assigned to the route. The profitgenerated by unit bandwidth is known for each route (may be different fordifferent routes). Under the above conditions, the company wants to decide how much bandwidth toassign to each route. The goal is that the ratio of the total profit vs. the total costismaximized. In other words, they want to maximize the yield of the bandwidthinvestment in the sense that it brings the highest profit percentage. Formulate thisoptimization problem as a linear programTOOL USEDThe tool used to solve a linear program is “LP_SOLVE”, lp_solve is a Mixed Integer Linear Programming (MILP) solver. The solution to linear programming problem is based on Simplex method or by using Branch and bound method.Basically, lp_solve is a library, a set of routines, called the API that can be called from almost any programming language to solve MILP problems. There are several ways to pass the data to the library:- Via the API- Via input files- Via an IDEThis problem is solved in IDE environment. The maximization function in the given problem is in the form of a fraction. The fraction is then brought to a linear form and the obtained equations is fed to lp_solve. Here is a list of some key features of lp_solve:- Mixed Integer Linear Programming (MILP) solver- Basically no limit on model size- It is free and with sources.- Supports Integer variables, Semi-continuous variables and Special OrderedSets.- Can read model from MPS, LP or user written format.- Models can be built in-memory without the use of files.- Has a powerful API interface.- Easy callable from other programming languages.- Advanced pricing using Devex and Steepest Edge for both primal and dual simplexes.- Provides different scaling methods to make the model more numerical stable.- Has presolve capabilities to tighten constraints/make the model smaller and faster to solve.- Has a base crashing routine to determine a starting point.- Allows restart after making changes to the model. Solve continues from the last found solution.- Possible to select desired combinations of primal and dual phases 1 and 2.- Possible to set several solver parameters like tolerances.- Alternative (and faster) inverse/re-factorisation libraries are provided.- Alternative model readers and writers possible via the XLI implementation.- Has the possibility to convert one model format to another format- Provides post-optimal sensitivity analysis. FEATURES OF TOOL USED IN THE PROJECT.The transformed fraction form of maximization function is directly fed in to lp_solve with the prescribed IDE 5.5.2.0 format. The inequality functions are stated. Now, it’s time to watch out for result, the result can be seen under result tab of the IDE GUI.Since the unit profit should be taken for each of the link and arbitrary capacity, the network is as
View Full Document
Unlocking...