Integer Programming A. Describe IBM Cplex based on reviewing the website? B. Wha

Question

Integer Programming

A. Describe IBM Cplex based on reviewing the website?

B. What is a cutting plane for Integer programming?

C. What is branch and cut?

D. What is NP-hard in terms of integer programming?

E. Describe the lower bound for an integer programming problem not solved to the optimal solution?

F. What can be the results for solving an integer program if you give the computer a fixed amount of time (such as 1 hour)?

G. Solve this knapsack problem via branch and bound by hand.

min 2x1 + 3x2+6 x3 +11 x4

st: 3x1 + 5 x2+ 5 x3 + 6 x4 > 11

PLEASE HELP, AND GIVE A BRIEF EXPLANATION FOR EACH. THANKS

Explanation / Answer

D. What is NP-hard in terms of integer programming?

If a problem is NP-Hard it means that there exists a class of instances of that problem whose are NP-Hard. It is perfectly possible for other specific classes of instances to be solvable in polynomial time.

Consider for example the problem of finding a 3 correlation of a graph. It is a well-known NP-Hard problem. Now imagine that its instances are restricted to graphs that are, for example, trees. Clearly you can easily find a 3-coloration of a tree in polynomial time (indeed you can also find a 2-coloration).

Consider decision problems for a second. A method of proving the hardness of a decision problem PP is devising a polynomial (karp) reduction another problem QQ that is known to be NP-Hard. In this reduction you show that there exists a function f that maps each instance q of the problem Q to an instance of the problem PP such that: q is a yes instance for Qf(q)Qf(q) is a yes instance for P. This implies that solving f(q)f(q) must be "at least as difficult" as solving q itself.

Notice how it's not required for the image of f to be equal to the set of the instances of P . Therefore it's perfectly possibile for problem P restricted to some subset of instances to not be hard.

B. What is a cutting plane for Integer programming?

Consider a pure integer linear programming problem in which all parameters are integer. This can be accomplished by multipying the constraint by a suitable constant. Because of this assumption, also the objective function value and all the "slack" variables of the problem must have integer values.
We start by solving the LP-relaxation to get a lower bound for the minimum objective value.
We assume the final simplex tableau is given, the basic variables having columns with coefficient 1 in other rows. The solution can be read from this form: when
the nonbasic variables are 0, the basic varibles have the values on right hand side (RHS) The objective function row is of the same form, with its basic variable f.
If the LP-solution is fractional i.e. not integer, at least one of the RHS values is fractional. We proceed by appending to the model a constraint that cuts away a part of the feasible set so that no integer solutions are lost.

C. What is branch and cut?
and cut method is a very successful algorithm for solving a variety of integer programming problems, and it also can provide a guarantee of optimality. Many problems involve variables which are not continuous but instead have integer values, and they can be solved by branch-and cut method. This method are exact algorithm consisting of a combination of a cutting plane method and a branch-and-bound algorithm.

A. Describe IBM Cplex based on reviewing the website?

IBM ILOG CPLEX offers C, C++, Java, .NET, and Python libraries that solve linear
programming (LP) and related problems. Specifically, it solves linearly or quadratically constrained optimization problems where the objective to be optimized can be expressed as a linear function or a convex quadratic function.The variables in the model may be declared as continuous or further constrainedto take only integer values.

CPLEX comes in these forms to meet a wide range of users' needs:

The CPLEX Interactive Optimizer is an executable program that can read a
problem interactively or from files in certain standard formats, solve the
problem, and deliver the solution interactively or into text files. The program
consists of the file cplex.exe on Windows platforms or cplex on UNIX
platforms.

Concert Technology is a set of libraries offering an API that includes modeling
facilities to allow a programmer to embed CPLEX optimizers in C++, Java, or
.NET applications. The library is provided in these files: ilocplexXXX.lib,
concert.lib, and cplexXXX.jar, where XXX represents a version number. This
convention of specifying the version number in the name of the library makes it
possible for you to maintain more than one version, if necessary. The library is
also provided in these files on Microsoft Windows platforms: cplexXXX.dll and
concertXXX.dll The library is also provided in these files on UNIX platforms:
libilocplex.a, libconcert.a, and cplex.jar. In all those cases, Concert Technology makes use of the Callable Library (described next).

The CPLEX Callable Library is a C library that allows the programmer to embed
CPLEX optimizers in applications written in C, Visual Basic, Fortran or any other language that can call C functions. The library is provided as a DLL on Windows platforms and in a library (that is, with file extensions .a , .so , or .sl) on UNIX platforms.

What CPLEX do?
CPLEX is a tool for solving, first of all, linear optimization problems.
CPLEX can also handle certain problems in which the objective function is not
linear but quadratic. Such problems are known as quadratic programs or QPs.
Chapter 13, “Solving problems with a quadratic objective (QP),” on page 185,
covers those kinds of problems.
CPLEX is also a tool for solving mathematical programming problems in which
some or all of the variables must assume integer values in the solution. Such
problems are known as mixed integer programs or MIPs because they may
combine continuous and discrete (for example, integer) variables in the objective
function and constraints. MIPs with linear objectives are referred to as mixed integer
linear programs or MILPs, and MIPs with quadratic objective terms are referred to
as mixed integer quadratic programs or MIQPs. Likewise, MIPs that are also
quadratically constrained in the sense of QCP are known as mixed integer
quadratically constrained programs or MIQCPs.

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.