Scribd Logo
Upload

Welcome to Scribd!

  • 91 views

    Integer Programming Short Questions

    Uploaded by

    Shabeeh
    An integer programming problem involves optimizing an objective function subject to constraints where some or all of the variables must take on integer values. There are two main types: all integer programming where all variables must be integers, and mixed integer programming where some variables can be continuous while others must be integers. Specialized algorithms are needed to solve integer programs exactly because the feasible region is nonconvex and optimal LP solutions may not satisfy integrality requirements.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd

    Integer Programming Short Questions

    Uploaded by

    Shabeeh
    91 views3 pages
    An integer programming problem involves optimizing an objective function subject to constraints where some or all of the variables must take on integer values. There are two main types: all integer programming where all variables must be integers, and mixed integer programming where some variables can be continuous while others must be integers. Specialized algorithms are needed to solve integer programs exactly because the feasible region is nonconvex and optimal LP solutions may not satisfy integrality requirements.

    Original Title

    INTEGER PROGRAMMING-2

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    An integer programming problem involves optimizing an objective function subject to constraints where some or all of the variables must take on integer values. There are two main types: all integer programming where all variables must be integers, and mixed integer programming where some variables can be continuous while others must be integers. Specialized algorithms are needed to solve integer programs exactly because the feasible region is nonconvex and optimal LP solutions may not satisfy integrality requirements.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    91 views3 pages

    Integer Programming Short Questions

    Uploaded by

    Shabeeh
    An integer programming problem involves optimizing an objective function subject to constraints where some or all of the variables must take on integer values. There are two main types: all integer programming where all variables must be integers, and mixed integer programming where some variables can be continuous while others must be integers. Specialized algorithms are needed to solve integer programs exactly because the feasible region is nonconvex and optimal LP solutions may not satisfy integrality requirements.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    of 3

    INTEGER PROGRAMMING

    Short Questions

    1. What is an integer programming problem?


    2. How do we classify IP problems based on the type of integer variables?
    3. What is an all integer programming problem?
    4. What is a mixed integer programming problem?
    5. What is the difference between the LP and IP feasible regions for the same set of
    constraints?
    6. Why do we need special algorithms to solve IPs?
    7. Why can’t we round off LP optimum solutions to get optimum solutions to IP problems?
    8. What is a fixed charge problem?
    9. Consider a binary IP with negative coefficients in the objective function. How will you
    convert it to the standard form with positive coefficients?
    10. What is implicit enumeration?
    11. How many possible solutions does a binary IP with n variables have?
    12. Is the additive algorithm a worst case complete enumeration algorithm?
    13. What is backtracking in the additive algorithm? When do you backtrack? What is the
    implication of the backtracking?
    14. Is the additive algorithm a better implementation of the branch and bound algorithm for
    binary variables? Why or why not?
    15. Explain how the Gomory cut is derived in an all integer IP?
    16. What is the principle behind the Gomory cut?
    17. What is the principle behind the branch and bound algorithm for IP?
    18. What are the three ways to fathom a node in the branch and bound algorithm?
    19. At every stage of the branch and bound algorithm, we add constraints. Does this
    increase the size of the LP solved?
    20. What is the difference between the constraints added in a cutting plane algorithm and
    the branch and bound algorithm?
    21. How can we tighten the bounds in the branch and bound algorithm?
    22. Write the equation of the fundamental cut?
    23. Explain how the all integer dual cut is written?
    24. Derive the MILP cut?
    25. How does the Benders’ partitioning algorithm work?

    Questions

    1. Solve the following binary ILP problem?


    Maximize 7X1 + 5X2 + 3X3
    Subject to X1 + 2X2 + 3X3 ≤ 5
    5X1 +3 X2 + 3X3 ≤ 10
    Xj = 0, 1
    2. Solve the following binary ILP problem?
    Minimize 3X1 + 4X2 + 6X3 + 5X4
    Subject to 2X1 - X2 + X3 + 3X4 ≥ 5
    -X1 + 3X2 - X3 + 2X4 ≥ 6
    Xj = 0, 1

    3. Solve the following ILP problem using the Gomory cutting plane algorithm?
    Maximize 7X1 + 2X2 + 5X3
    Subject to 2X1 + X2 + X3 ≤ 9
    X1 + 2 X2 + 4X3 ≤ 16
    Xj ≥ 0 and integer

    4. Solve the following ILP problem using the Gomory cutting plane algorithm?
    Minimize 3X1 + 4X2
    Subject to 2X1 - X2 ≥ 5
    -X1 + 3X2 ≥ 6
    Xj ≥ 0 and integer

    5. Solve the following ILP problem using the branch and bound algorithm?
    Maximize 7X1 + 2X2 + 5X3
    Subject to 2X1 + X2 + X3 ≤ 9
    X1 + 2 X2 + 4X3 ≤ 16
    Xj ≥ 0 and integer

    6. Solve the following ILP problem using the branch and bound algorithm?
    Minimize 3X1 + 4X2
    Subject to 2X1 - X2 ≥ 5
    -X1 + 3X2 ≥ 6
    Xj ≥ 0 and integer

    7. Solve the following ILP problem using the all integer dual algorithm?
    Minimize 3X1 + 4X2
    Subject to 2X1 - X2 ≥ 5
    -X1 + 3X2 ≥ 6
    Xj ≥ 0 and integer

    8. Solve the following ILP problem using all integer primal algorithm?
    Maximize 7X1 + 2X2 + 5X3
    Subject to 2X1 + X2 + X3 ≤ 9
    X1 + 2 X2 + 4X3 ≤ 16
    Xj ≥ 0 and integer

    9. Solve the following ILP problem using the Gomory cutting plane algorithm?
    Maximize 2X1 + 3X2
    Subject to -X1 + 2X2 ≤ 6
    2X1 - X2 ≤ 7
    Xj ≥ 0 and integer
    10. Solve the following ILP problem using the branch and bound algorithm?
    Maximize 2X1 + 3X2
    Subject to -X1 + 2X2 ≤ 6
    2X1 - X2 ≤ 7
    Xj ≥ 0 and integer

    11. Solve the following ILP problem using the all integer primal algorithm?
    Maximize 2X1 + 3X2
    Subject to -X1 + 2X2 ≤ 6
    2X1 - X2 ≤ 7
    Xj ≥ 0 and integer

    12. Solve the following MILP problem using the cutting plane algorithm?
    Minimize 3X1 + 4X2
    Subject to 2X1 - X2 ≥ 5
    -X1 + 3X2 ≥ 6
    X1 ≥ 0 and integer; X2 ≥ 0

    13. Solve the following MILP problem using the branch and bound algorithm?
    Minimize 3X1 + 4X2
    Subject to 2X1 - X2 ≥ 5
    -X1 + 3X2 ≥ 6
    X1 ≥ 0 and integer; X2 ≥ 0

    14. Solve the following MILP problem using the Benders partitioning algorithm?
    Minimize 3X1 + 4X2
    Subject to 2X1 - X2 ≥ 5
    -X1 + 3X2 ≥ 6
    X1 ≥ 0 and integer; X2 ≥ 0

    15. Solve the following MILP problem using the cutting plane algorithm?
    Maximize 2X1 + 3X2
    Subject to -X1 + 2X2 ≤ 6
    2X1 - X2 ≤ 7
    X2 ≥ 0 and integer; X1 ≥ 0

    16. Solve the following MILP problem using the branch and bound algorithm?
    Maximize 2X1 + 3X2
    Subject to -X1 + 2X2 ≤ 6
    2X1 - X2 ≤ 7
    X2 ≥ 0 and integer; X1 ≥ 0

    17. Solve the following MILP problem using the Benders partitioning algorithm?
    Maximize 2X1 + 3X2
    Subject to -X1 + 2X2 ≤ 6
    2X1 - X2 ≤ 7
    X2 ≥ 0 and integer; X1 ≥ 0

    You might also like