6.8 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, quadratic and quadratically constrtained and conic problems (except semidefinite). See the previous tutorials for an introduction to how to model these types of problems.

6.8.1 Basic linear example

We use the example

(6.27)\[\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 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 or one of its bulk analogues:

        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 Sec. 13.5 (The Mixed-Integer optimizer) 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.13. Please note that when we fetch the solution then the integer solution is requested by using soltype.itg. No dual solution is defined for integer optimization problems.

Listing 6.13 Source code implementing problem (6.27). 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():
    # Create a task
    with mosek.Task() 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()
        task.writedata("milo1.ptf")

        # 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 = task.getxx(mosek.soltype.itg)

        if solsta in [mosek.solsta.integer_optimal]:
            print("Optimal solution: %s" % xx)
        elif solsta == mosek.solsta.prim_feas:
            print("Feasible solution: %s" % xx)
        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.MosekException 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.8.2 Specifying an initial solution (hot-start)

It is a common strategy to provide a starting feasible point (if one is known in advance) to the mixed-integer solver. This is known as hot-start or warm-start. The feasible point may come from the user’s prior knowledge of the model, a heuristic, or a solution from a preceding solve if the problem was modified so that the solution remains feasible. Using hot-start allows the solver to skip worse solutions and potentially get closer to the optimum faster.

There are two modes for MOSEK to utilize an initial solution.

• A complete solution. MOSEK will first try to check if the current value of the primal variable solution is a feasible point. The solution can either come from a previous solver call or can be entered by the user, however the full solution with values for all variables (both integer and continuous) must be provided. This check is always performed and does not require any extra action from the user. The outcome of this process can be inspected via information items iinfitem.mio_initial_feasible_solution and dinfitem.mio_initial_feasible_solution_obj, and via the Initial feasible solution objective entry in the log.

• A partial integer solution. MOSEK can also try to construct a feasible solution by fixing integer variables to the values provided by the user (rounding if necessary) and optimizing over the remaining continuous variables. In this setup the user must provide initial values for all integer variables. This action is only performed if the parameter iparam.mio_construct_sol is switched on. The outcome of this process can be inspected via information items iinfitem.mio_construct_solution and dinfitem.mio_construct_solution_obj, and via the Construct solution objective entry in the log.

In the following example we focus on inputting a partial integer solution.

(6.28)\[\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.putxx, Task.putxxslice or similar . If the solution to be used as hot-start happens to come from a previous solve of the same model/task then it will be used by the solver automatically and does not have to be input explicitly through the API again.

Listing 6.14 Implementation of problem (6.28) specifying an initial solution. Click here to download.

        # Assign values to integer variables. 
        # (We only set a slice of xx)
        task.putxxslice(mosek.soltype.itg, 0, 3, [1.0, 1.0, 0.0])

        # Request constructing the solution from integer variable values
        task.putintparam(mosek.iparam.mio_construct_sol, mosek.onoffkey.on)

The log output from the optimizer will in this case indicate that the inputted values were used to construct an initial feasible solution:

Construct solution objective       : 1.950000000000e+01

The same information can be obtained from the API:

Listing 6.15 Retrieving information about usage of initial solution Click here to download.

            constr = task.getintinf(mosek.iinfitem.mio_construct_solution)
            constrVal = task.getdouinf(mosek.dinfitem.mio_construct_solution_obj)
            print("Construct solution utilization: {0}\nConstruct solution objective: {1:.3f}\n".format(constr, constrVal))

6.8.3 Basic conic example

Integer variables can also be used arbitrarily in conic problems (except semidefinite). We refer to the previous tutorials for how to set up a conic optimization problem. Here we present sample code that sets up a simple optimization problem:

(6.29)\[\begin{split}\begin{array}{ll} \mbox{minimize} & x^2+y^2 \\ \mbox{subject to} & x \geq e^y+3.8, \\ & x, y \ \mbox{integer}. \end{array}\end{split}\]

The canonical conic formulation of (6.29) suitable for Optimizer API for Python is

(6.30)\[\begin{split}\begin{array}{llr} \mbox{minimize} & t & \\ \mbox{subject to} & (t,x,y)\in\Q^3 & (t\geq\sqrt{x^2+y^2}) \\ & (x-3.8, 1, y) \in\EXP & (x-3.8\geq e^y) \\ & x, y \ \mbox{integer}, & \\ & t\in\real. \end{array}\end{split}\]

Listing 6.16 Implementation of problem (6.30). Click here to download.

with mosek.Task() as task:
    task.set_Stream(mosek.streamtype.log, streamprinter)

    task.appendvars(3)    # x, y, t
    x, y, t = 0, 1, 2
    task.putvarboundsliceconst(0, 3, mosek.boundkey.fr, -0.0, 0.0)
    
    # Integrality constraints
    task.putvartypelist([x,y], [mosek.variabletype.type_int]*2)

    # Set up the affine expression
    # x, x-3.8, y, t, 1.0
    task.appendafes(5)
    task.putafefentrylist([0, 1, 2, 3],
                          [x,x,y,t],
                          [1,1,1,1])
    task.putafegslice(0, 5, [0, -3.8, 0, 0, 1.0])

    # Add constraint (x-3.8, 1, y) \in \EXP
    task.appendacc(task.appendprimalexpconedomain(), [1, 4, 2], None)

    # Add constraint (t, x, y) \in \QUAD
    task.appendacc(task.appendquadraticconedomain(3), [3, 0, 2], None)

    # Objective
    task.putobjsense(mosek.objsense.minimize)
    task.putcj(t, 1)

    # Optimize the task
    task.optimize()
    task.solutionsummary(mosek.streamtype.msg)

    xx = task.getxxslice(mosek.soltype.itg, 0, 2)
    print(xx)

Error and solution status handling were omitted for readability.

6.8.4 Fixed problem and dual values

The dual solution is not defined for mixed-integer problems, but in some cases the user may want to obtain some dual information (shadow prices). One typical strategy is to compute shadow price information under the assumption that the combinatorial decisions (integer variable values) do not change, that is:

• solve the mixed-integer model (to some feasible solution, not necessarily optimal),

• fix all integer variables to their values in the solution,

• solve the fixed model as a continuous problem and extract the dual values.

Optimizer API for Python facilitates the construction of the fixed model with with Task.getfixedproblem.

As an example we consider a toy production planning model with two plants with maximum capacities 70, 80 units and a demand of 100 units:

(6.31)\[\begin{split}\begin{array}{ll} \mbox{minimize} & 10x_1 + 14x_2 + 500s_1 + 300s_2 \\ \mbox{subject to} & x_1+x_2\geq 100, \\ & 0 \leq x_1 \leq 70s_1, \\ & 0 \leq x_2 \leq 80s_2, \\ & s_1,s_2 \in \{0,1\}. \end{array}\end{split}\]

We begin by solving the mixed-integer problem and verifying that it has a feasible solution with \(s_1=s_2=1\) i.e. both plants active with production levels \((x_1,x_2)=(70,30)\). Then, assuming no modifications are made to the problem structure or numerical data, we can immediately construct and solve the fixed integer model and retrieve its solution as shown below.

Listing 6.17 Solving the fixed integer model for (6.31). Click here to download.

    # Constructing the continuous task with fixed variables
    with task.getfixedproblem() as fixTask:
        fixTask.set_Stream(mosek.streamtype.log, sys.stdout.write)

        fixTask.optimize()

        if fixTask.getprosta(mosek.soltype.bas) != mosek.prosta.prim_and_dual_feas:
            raise Exception("Unsuitable problem status, exiting")

        xfix = fixTask.getxxslice(mosek.soltype.bas, 0, 2)
        y = fixTask.getyslice(mosek.soltype.bas, 0, 3)

        print(f"xfix = {xfix[0]}, {xfix[1]}")
        print(f"demand dual = {y[0]}")
        print(f"production dual = {y[1]}, {y[2]}")

For instance, the shadow price for the first plant’s production constraint is \(-4\), corresponding to the fact that increasing the capacity of the first plant by 1 unit would allow shifting one production unit form plant 2 to plant 1, reducing the objective cost by \(14-10=4\).

Note that the solution of the mixed-integer problem will typically have small violations, which implies that the fixed model may be declared (borderline) infeasible. To avoid this effect, the fixing algorithm will by default introduce small perturbations of bounds in order to make the fixed problem strictly feasible. If needed this can be controlled by setting the parameter iparam.fixing_method in the original task prior to fixing.