Prev Next Top TakeHome

Take Home Integer Programming Problem

Original Problem
Solve the problem
     maximize     x1 +   x2 +   x3         w.r.t x in Z+^3
     subject to   x1 + 2*x2        <= 5
                         x2 + 2*x3 <= 5
                2*x1 +          x3 <= 5
You must show your work for this problem; i.e., prove that your solution is optimal. If you solve it using the Neos Clp server, you must include one of your input files and a discussion of what was different between the input files.

Hint
I found it useful to use Bounds Records in my MPS input file. My original problem, with no branching, did not give integer results. Neither did just constraining one of the variables give integer results. Thus I had to constrain two of the variables and this made it necessary to check four cases (not counting the three cases I checked that gave non-integer results).

Solution

Relaxed Problem
The relaxed problem is
     maximize     x1 +   x2 +   x3         w.r.t x in R+^3
     subject to   x1 + 2*x2        <= 5
                         x2 + 2*x3 <= 5
                2*x1 +          x3 <= 5

Case 1
This corresponds to solving the relaxed problem:
     Bounds      x1 >= 0, x2 >= 0, x3 >= 0
     Solution    x1 = 1.66.., x2 = 1.66.., x3 = 1.66..
     Objective   5
This is not a solution to the original problem because not all the components of  x are integers.

Case 2
This corresponds to solving the relaxed problem with the extra constraint  x1 >= 2.
     Bounds      x1 >= 2, x2 >= 0, x3 >= 0
     Solution    x1 = 2, x2 = 1.5, x3 = 1
     Objective   4.5
This is not a solution to the original problem because  x2 is not an integer.

Case 3
This corresponds to solving the relaxed problem with the extra constraints  x1 >= 2, x2 >= 2.
     Bounds      x1 >= 2, x2 >= 2, x3 >= 0
     Solution    (no feasible solution)
     Objective   minus infinity
There is no solution to this problem, hence there is not solution to the integer version of this problem.

Case 4
This corresponds to solving the relaxed problem with the extra constraints  x1 >= 2, x2 <= 1.
     Bounds      x1 >= 2, x2 <= 1, x3 >= 0
     Solution    x1 = 2, x2 = 1, x3 = 1
     Objective   4.
It follows that this is also the solution of the original problem with the extra constraints  x1 >= 2,  x2 <= 1.

Case 5
This corresponds to solving the relaxed problem with the extra constraints  x1 <= 1.
     Bounds      x1 <= 1, x2 >= 0, x3 >= 0
     Solution    x1 = 1, x2 = 2, x3 = 1.5
     Objective   4.5
This is not a solution to the original problem because  x3 is not an integer.

Case 6
This corresponds to solving the relaxed problem with the extra constraints  x1 <= 1, x3 >= 2.
     Bounds      x1 <= 1, x2 >= 0, x3 >= 2
     Solution    x1 = 1, x2 = 1, x3 = 2
     Objective   4
It follows that this is also the solution of the original problem with the extra constraints  x1 <= 1, x3 >= 2.

Case 7
This corresponds to solving the relaxed problem with the extra constraints  x1 <= 1, x3 <= 1.
     Bounds      x1 <= 1, x2 >= 0, x3 <= 1
     Solution    x1 = 1, x2 = 2, x3 = 1
     Objective   4
It follows that this is also the solution of the original problem with the extra constraints  x1 <= 1, x3 <= 1.

Summary
We divide the original problem into four possible cases:
Case Extra Constraint   Optimal Objective  Solution
3    x1 >= 2, x2 >= 2   minus infinity     (none)
4    x1 >= 2, x2 <= 1   4                  x1 = 2, x2 = 1, x3 = 1
6    x1 <= 1, x3 >= 2   4                  x1 = 1, x2 = 1, x3 = 2
7    x1 <= 1, x3 <= 1   4                  x1 = 1, x2 = 2, x3 = 1
Since this exhaust all the possible cases for the original problem, the following are all solutions to the original problem
     x = (2, 1, 1)
     x = (1, 1, 2)
     x = (1, 2, 1) 

MPS Input File
The following MPS input file corresponds to Case 7 where the bounds are
     x1 <= 1, x2 >= 0, x3 <= 1
*Op Name0---  Name1---  Value1------
*23 56789012  56789012  567890123456
NAME          UP x1 1, PL x2, UP x3 1
ROWS
 N  z
 L  r1
 L  r2
 L  r3
COLUMNS
*Op Name0---  Name1---  Value1------
    x1        z         1
    x1        r1        1
    x1        r2        0
    x1        r3        2
*
    x2        z         1
    x2        r1        2
    x2        r2        1
    x2        r3        0
*
    x3        z         1
    x3        r1        0
    x3        r2        2
    x3        r3        1
*
RHS
    rhs       r1        5
    rhs       r2        5
    rhs       r3        5
BOUNDS
 UP bnd       x1        1
 PL bnd       x2
 UP bnd       x3        1
ENDATA
Note that the other MPS input files are formed by just changing the bounds for the corresponding variables. In addition, the NAME record was changed to reflect the corresponding bounds.
Input File: TakeHome.omh