6.5 Integer Optimization

An optimization problem where one or more of the variables are constrained to integer values is called a (mixed) integer optimization problem. MOSEK supports integer variables in combination with linear and conic quadratic problems. See the previous tutorials for an introduction to how to model these types of problems.

6.5.1 Example MILO1

We use the example

(1)\[\begin{split}\begin{array}{lccl} \mbox{maximize} & x_0 + 0.64 x_1 & & \\ \mbox{subject to} & 50 x_0 + 31 x_1 & \leq & 250, \\ & 3 x_0 - 2 x_1 & \geq & -4, \\ & x_0, x_1 \geq 0 & & \mbox{and integer} \end{array}\end{split}\]

to demonstrate how to set up and solve a problem with integer variables. It has the structure of a linear optimization problem (see Section 6.1) except for integrality constraints on the variables. Therefore, only the specification of the integer constraints requires something new compared to the linear optimization problem discussed previously.

First, the integrality constraints are imposed using the function Task.putvartype:

            task.putvartypelist([0, 1],
                                [mosek.variabletype.type_int,
                                 mosek.variabletype.type_int])

Next, the example demonstrates how to set various useful parameters of the mixed-integer optimizer. See Section 14 for details.

            # Set max solution time 
            task.putdouparam(mosek.dparam.mio_max_time, 60.0);

The complete source for the example is listed Listing 6.6. Please note that when Task.getsolutionslice is called, the integer solution is requested by using soltype.itg. No dual solution is defined for integer optimization problems.

Listing 6.6 Source code implementing problem (1). Click here to download.
import sys
import mosek

# Since the actual value of Infinity is ignores, we define it solely
# for symbolic purposes:
inf = 0.0

# Define a stream printer to grab output from MOSEK
def streamprinter(text):
    sys.stdout.write(text)
    sys.stdout.flush()


def main():
    # Make a MOSEK environment
    with mosek.Env() as env:
        # Attach a printer to the environment
        env.set_Stream(mosek.streamtype.log, streamprinter)

        # Create a task
        with env.Task(0, 0) as task:
            # Attach a printer to the task
            task.set_Stream(mosek.streamtype.log, streamprinter)

            bkc = [mosek.boundkey.up, mosek.boundkey.lo]
            blc = [-inf, -4.0]
            buc = [250.0, inf]

            bkx = [mosek.boundkey.lo, mosek.boundkey.lo]
            blx = [0.0, 0.0]
            bux = [inf, inf]

            c = [1.0, 0.64]

            asub = [[0, 1], [0, 1]]
            aval = [[50.0, 3.0], [31.0, -2.0]]

            numvar = len(bkx)
            numcon = len(bkc)

            # Append 'numcon' empty constraints.
            # The constraints will initially have no bounds.
            task.appendcons(numcon)

            #Append 'numvar' variables.
            # The variables will initially be fixed at zero (x=0).
            task.appendvars(numvar)

            for j in range(numvar):
                # Set the linear term c_j in the objective.
                task.putcj(j, c[j])
                # Set the bounds on variable j
                # blx[j] <= x_j <= bux[j]
                task.putvarbound(j, bkx[j], blx[j], bux[j])
                # Input column j of A
                task.putacol(j,                  # Variable (column) index.
                             # Row index of non-zeros in column j.
                             asub[j],
                             aval[j])            # Non-zero Values of column j.

            task.putconboundlist(range(numcon), bkc, blc, buc)

            # Input the objective sense (minimize/maximize)
            task.putobjsense(mosek.objsense.maximize)

            # Define variables to be integers
            task.putvartypelist([0, 1],
                                [mosek.variabletype.type_int,
                                 mosek.variabletype.type_int])

            # Set max solution time 
            task.putdouparam(mosek.dparam.mio_max_time, 60.0);


            # Optimize the task
            task.optimize()

            # Print a summary containing information
            # about the solution for debugging purposes
            task.solutionsummary(mosek.streamtype.msg)

            prosta = task.getprosta(mosek.soltype.itg)
            solsta = task.getsolsta(mosek.soltype.itg)

            # Output a solution
            xx = [0.] * numvar
            task.getxx(mosek.soltype.itg, xx)

            if solsta in [mosek.solsta.integer_optimal, mosek.solsta.near_integer_optimal]:
                print("Optimal solution: %s" % xx)
            elif solsta == mosek.solsta.dual_infeas_cer:
                print("Primal or dual infeasibility.\n")
            elif solsta == mosek.solsta.prim_infeas_cer:
                print("Primal or dual infeasibility.\n")
            elif solsta == mosek.solsta.near_dual_infeas_cer:
                print("Primal or dual infeasibility.\n")
            elif solsta == mosek.solsta.near_prim_infeas_cer:
                print("Primal or dual infeasibility.\n")
            elif mosek.solsta.unknown:
                if prosta == mosek.prosta.prim_infeas_or_unbounded:
                    print("Problem status Infeasible or unbounded.\n")
                elif prosta == mosek.prosta.prim_infeas:
                    print("Problem status Infeasible.\n")
                elif prosta == mosek.prosta.unkown:
                    print("Problem status unkown.\n")
                else:
                    print("Other problem status.\n")
            else:
                print("Other solution status")

# call the main function
try:
    main()
except mosek.Exception as msg:
    #print "ERROR: %s" % str(code)
    if msg is not None:
        print("\t%s" % msg)
        sys.exit(1)
except:
    import traceback
    traceback.print_exc()
    sys.exit(1)

6.5.2 Specifying an initial solution

Solution time of can often be reduced by providing an initial solution for the solver. It is not necessary to specify the whole solution. By setting the iparam.mio_construct_sol parameter to onoffkey.on and inputting values for the integer variables only, MOSEK will be forced to compute the remaining continuous variable values. If the specified integer solution is infeasible or incomplete, MOSEK will simply ignore it.

We concentrate on a simple example below.

(2)\[\begin{split}\begin{array} {ll} \mbox{maximize} & 7 x_0 + 10 x_1 + x_2 + 5 x_3 \\ \mbox{subject to} & x_0 + x_1 + x_2 + x_3 \leq 2.5\\ & x_0,x_1,x_2 \in \integral \\ & x_0,x_1,x_2,x_3 \geq 0 \end{array}\end{split}\]

Solution values can be set using Task.putxxslice and related methods.

Listing 6.7 Implementation of problem (2) specifying an initial solution. Click here to download.
            # Construct an initial feasible solution from the
            #     values of the integer valuse specified
            task.putintparam(mosek.iparam.mio_construct_sol,
                             mosek.onoffkey.on)

            # Assign values 0,2,0 to integer variables. Important to
            # assign a value to all integer constrained variables.
            task.putxxslice(mosek.soltype.itg, 0, 3, [0.0, 2.0, 0.0])

The complete code is not very different from the first example and is available for download as mioinitsol.py. For more details about this process see Section 14.