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 Example MILO1

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 (see Sec. 6.1 (Linear Optimization)) 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.put_var_type or one of its bulk analogues:

                    for j in 0..numvar {
                        task.put_var_type(j, Variabletype::TYPE_INT)?;

Next, the example demonstrates how to set various useful parameters of the mixed-integer optimizer. See Sec. 13.4 (The Optimizer for Mixed-Integer Problems) for details.

                    task.put_dou_param(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.
extern crate mosek;

use mosek::{Task,Boundkey,Objsense,Streamtype,Solsta,Prosta,Soltype,Variabletype,Dparam};

fn main() -> Result<(),String> {
    let numcon : i32 = 2;
    let numvar : i32 = 2;

    let infinity = 0.0; // only for symbolic purposes, value never used

    let bkc = vec![Boundkey::UP, Boundkey::LO];
    let blc = vec![ -infinity,         -4.0 ];
    let buc = vec![ 250.0,             infinity ];

    let bkx = vec![ Boundkey::LO, Boundkey::LO  ];
    let blx = vec![ 0.0,               0.0 ];
    let bux = vec![ infinity,          infinity ];

    let c   = vec![1.0, 0.64];

    let asub = vec![0,   1,
                    0,    1];
    let aval = vec![50.0, 3.0, 31.0, -2.0];

    let ptrb : Vec<usize> = vec![ 0, 2 ];
    let ptre : Vec<usize> = vec![ 2, 4 ];

    /* Create the optimization task. */
    Task::new().expect("Failed to create task")
            &mut |msg| print!("{}",msg),
            |task| task.with_itg_sol_callback(
                &mut |xx| { println!("Found a new solution = {:?}",xx); false },
                |task| {
                    /* Append 'numcon' empty constraints.
                    The constraints will initially have no bounds. */

                    /* Append 'numvar' variables.
                    The variables will initially be fixed at zero (x=0). */

                    for ((((j,cj),bk),bl),bu) in (0..numvar).zip(c.iter()).zip(bkx.iter()).zip(blx.iter()).zip(bux.iter()) {
                        /* Set the linear term c_j in the objective.*/
                        task.put_c_j(j, *cj)?;
                        /* Set the bounds on variable j.
                           blx[j] <= x_j <= bux[j] */
                        task.put_var_bound(j, *bk, *bl, *bu)?;
                        /* Input column j of A */
                        task.put_a_col(j,                     /* Variable (column) index.*/
                                       &asub[ptrb[j as usize]..ptre[j as usize]],               /* Row index of non-zeros in column j.*/
                                       &aval[ptrb[j as usize]..ptre[j as usize]])?;              /* Non-zero Values of column j. */
                    // Set the bounds on constraints.
                    // for i=1, ...,numcon : blc[i] <= constraint i <= buc[i] 
                    for (((i,bk),bl),bu) in (0..numcon).zip(bkc.iter()).zip(blc.iter()).zip(buc.iter()) {
                        task.put_con_bound(i, *bk, *bl, *bu)?;

                    /* Specify integer variables. */
                    for j in 0..numvar {
                        task.put_var_type(j, Variabletype::TYPE_INT)?;
                    /* Set max solution time */
                    task.put_dou_param(Dparam::MIO_MAX_TIME, 60.0)?;

                    /* A maximization problem */
                    /* Solve the problem */

                    let _trm = task.optimize()?;

                    // Print a summary containing information
                    //   about the solution for debugging purposes

                    let mut xx = vec![0.0; numvar as usize];
                    task.get_xx(Soltype::ITG, xx.as_mut_slice())?;

                    /* Get status information about the solution */

                    match task.get_sol_sta(Soltype::ITG)? {
                        Solsta::INTEGER_OPTIMAL => {
                            println!("Optimal solution");
                            for (j,xj) in (0..numvar).zip(xx.iter()) {
                                println!("x[{}]: {}", j,xj);
                        Solsta::PRIM_FEAS => {
                            println!("Feasible solution");
                            for (j,xj) in (0..numvar).zip(xx.iter()) {
                                println!("x[{}]: {}", j,xj);
                        Solsta::UNKNOWN => {
                          match task.get_pro_sta(Soltype::ITG)? {
                              Prosta::PRIM_INFEAS_OR_UNBOUNDED => {
                                  println!("Problem status Infeasible or unbounded");
                              Prosta::PRIM_INFEAS => {
                                  println!("Problem status Infeasible.");
                              Prosta::UNKNOWN => {
                                  println!("Problem status unknown.");
                              _ => {
                                  println!("Other problem status.");
                        _ => {
                            println!("Other solution status");

6.8.2 Specifying an initial solution

It is a common strategy to provide a starting feasible point (if one is known in advance) to the mixed-integer solver. This can in many cases reduce solution time.

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.put_xx, Task.put_xx_slice or similar .

Listing 6.14 Implementation of problem (6.28) specifying an initial solution. Click here to download.
    task.put_xx_slice(Soltype::ITG, 0, 3, &[1.0,1.0,0.0])?;

    // Request constructing the solution from integer variable values
    task.put_int_param(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.
    let constr = task.get_int_inf(mosek::Iinfitem::MIO_CONSTRUCT_SOLUTION)?;
    let constr_val = task.get_dou_inf(mosek::Dinfitem::MIO_CONSTRUCT_SOLUTION_OBJ)?;
    println!("Construct solution utilization: {}", constr);
    println!("Construct solution objective: {}",  constr_val);

6.8.3 Example MICO1

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 Rust 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.
fn main() -> Result<(),String> {
    /* Create the optimization task. */
    let mut task = match Task::new() {
        Some(t) => t,
        None => return Err("Failed to create task".to_string()),
    let infinity = 0.0; // for symbolic use, value is irrelevant

    task.put_stream_callback(Streamtype::LOG, |msg| print!("{}",msg))?;

    task.put_var_bound_slice_const(0, 6, Boundkey::FR, -infinity, infinity)?;

    // Integrality constraints
                           vec![Variabletype::TYPE_INT, Variabletype::TYPE_INT].as_slice())?;

    // Set up the three auxiliary linear constraints
    task.put_con_bound_slice(0, 3, 
                             vec![Boundkey::FX, Boundkey::FX, Boundkey::FX].as_slice(),
                             vec![-3.8, 1.0, 0.0].as_slice(),
                             vec![-3.8, 1.0, 0.0].as_slice())?;

    // Objective
    task.put_c_j(0, 1.0)?;

    // Conic part of the problem
    for i in 0..6 {
        task.put_afe_f_entry(i as i64, i as i32, 1.0)?;
        let domidx = task.append_quadratic_cone_domain(3)?;
        let domidx = task.append_primal_exp_cone_domain()?;
    // Optimize the task
    let _trm = task.optimize()?;

    let mut xx = vec![0.0; 2];
    task.get_xx_slice(Soltype::ITG, 1, 3, xx.as_mut_slice())?;
    println!("x = {}  y = {}",xx[0],xx[1]);

Error and solution status handling were omitted for readability.