Parametrized IPs

IP_Param stands for Parametrized Integer Program, a mathematical program in the following form:

$\begin{split}\min_y c^Ty + (Cx)^T y \\ \text{s.t.} \quad By \le b \\ \quad \quad y \ge 0 \\ \quad \quad y_i \in \mathbb{Z} \quad \forall i \in I\end{split}$

Where $$y$$ are the decision variables for the program, $$x$$ are parameters, and $$I$$ is the set of indices of integer variables. ZERO supports Integer Programs with linear constraints and bi-linear objectives (linear in $$y$$). You can find the API information in MathOpt::IP_Param. This class is an inheritor of MathOpt::MP_Param, and we use the same notation of the abstract.

Modeling the problem

Following the previous example on parametrized Quadratic Programs, consider the following parametrized Integer Program:

\begin{align}\begin{aligned}\max_{y_1, y_2} y_1 + 2y_2 - 2y_1x_1 -3y_2x_2\\\text{s.t.} \quad 3y_1+4y_2 &\le 5\\\quad \quad y_1, y_2 &\in \{0,1\}\end{aligned}\end{align}

This is a Knapsack Problem in $$y$$, with an objective function parametrized in the $$x$$ variables. We assume the matrix C is a matrix with:

• A number of rows corresponding to the number of $$y$$ variables

• A number of columns corresponding to the number of $$x$$ parameters

#include "zero.h"
//The linear objectives in y
arma::vec                _c(2);
//The matrix of interaction coefficients among parameters and variables
arma::mat                _C = arma::zeros(2, 2);
//The constraint matrix
arma::mat                _A = arma::zeros(1, 2);

//The list of indexes of variable that are integer
arma::vec _integers(_c.size());

//All variables are integer here
for (unsigned int i = 0; i < _c.size(); ++i)
_integers.at(i) = i;

//Invert the sign since we have a maximization
_C(0, 0) = 2;
_C(1, 1) = 3;
_c(0) = -1;
_c(1) = -2;

//Knapsack Constraint
_A(0, 0) = 3;
_A(0, 1) = 4;

arma::vec _b = arma::vec{5};

//Convert to sparse objects
arma::sp_mat      _C2  = arma::sp_mat{_C};
arma::sp_mat      _A2  = arma::sp_mat{_A};

VariableBounds    bnds = {{0, 1}, {0, 1}};
//Gurobi Environment
GRBEnv      test;
MathOpt::IP_Param ipParam(_C2, _A2, _b, _c, _integers, bnds, &test);


Computing solutions

With $$(x_1, x_2) = (-1, 0.5)$$, we can provide the value of $$f$$ and solve it through Gurobi

// Enter the value of x in an arma::vec
arma::vec x(2);
x(0) = -1;
x(1) = 0.5;

// Uses Gurobi to solve the model, returns a unique_ptr to GRBModel
auto FixedModel = ipParam.solveFixed(x,true);