Question

Agree/Disagree and Why?

Integer linear programs involve a class of problems that are modeled as linear programs with the additional requirement that one or more variables must be integer. If all variables must be integer, we have an all-integer linear program. As some, but not all, variables must be integer of a mixed-integer linear program. The cost of the added modeling flexibility provided by integer programming is that problems involving integer variables are often much more difficult to solve. (Anderson)

As discussed Bradley, Hax, and Magnati, “The linear-programming models that have been discussed thus far all have been continuous, in the sense that decision variables are allowed to be fractional. Often this is a realistic assumption. At other times, however, fractional solutions are not realistic, and we must consider the optimization problem. This problem is called the (linear) integer-programming problem. It is said to be a mixed integer program when some, but not all, variables are restricted to be integer, and is called a pure integer program when all decision variables must be integers. If the constraints are of a network nature, then an integer solution can be obtained by ignoring the integrality restrictions and solving the resulting linear program. In general, though, variables will be fractional in the linear-programming solution, and further measures must be taken to determine the integer-programming solution.”

If we drop the phrase “and integer” from the last line of this model, we have the familiar two variable linear program. The linear program that results from dropping the integer requirements is called the LP relaxation of the integer linear program. When analyzing the LP Relaxation model, it is possible use a graphical solution just as accomplished with the familiar two variable linear program. In many cases, a non-integer solution can be rounded to obtain an acceptable integer solution. It should be recognized however that rounding may not always be a good strategy. When the decision variables take on small values that have a major impact on the value of the objective function, an optimal integer solution is needed. Rounding to an integer solution is a trial-and-error approach. Another aspect of integer linear program is a result of the need to use 0-1 variables. In many applications, 0-1 variables provide selections or choices if the value of the variable equal to 1 corresponds to activities undertaken, and equal to 0 if the corresponding activity is not undertaken. (Anderson) In this application of integer linear programming, the story involving the wisdom of King Solomon comes to mind. In the story, two women came to him with one baby with each woman claiming that she was the mother of the baby. King Solomon, without knowing which woman was truly the mother of the baby, asked for a sword. Because neither one of the women would confess that she was not the mother, he ordered the baby to be cut in half and give each of the women half of the baby. The real mother who truly loved the child requested that King Solomon give the baby to the other woman so the child would not be injured. The other woman who was not the real mother said go ahead and cut the baby in half, whereupon, in his wisdom inspired by God, King Solomon realized the first woman was the true mother. In a simple example maintaining the constraint of 0 or 1, representing a whole baby or half of a baby, King Solomon was able to determine the true identity of the baby’s mother.

Integer linear program can be applied to many real-world situations such as distribution system design for shipping, business center location problems for optimum customer service, product design and market share optimization, and determining number of weapon systems for the DoD (Anderson)

Answer 1

Optimization can be said as a way of life.We all are having finite sources and had to make maximum out of it hence in order to use time efficiently and increase productivity everything uses optimization.Integer linear programs can start with a very simple problem but can get very complex.Such as sharing a bar of chocolate between siblings is a simple Linear programming,On the other hand, devising inventory and warehousing strategy for an e-tailer is a tidious and complex job .It is just that we dont think mathematically. Linear programming can be said as the simplest ways to reach optimization. It helps in resolving few very complex optimization problems by making a few simplifying assumptions. Linear programming is a simple technique where complex relationships are being presented through linear functions and then find the optimum points. Applications of linear programming are everywhere around us. Ones applies linear programming at both personal and professional levels,for instance we use linear programming when we are driving from home to work and want to take the shortest route. Or when you have a project delivery you make strategies to make your teamwork efficiently for on-time delivery. In linear programming, real life problems are being formulated into a mathematical model like in the above example of king and the fight for baby.LP just involves an objective function, linear inequalities with subject to constraints.