Is there a name for this type of integer programming?

Question

Let $x_i$ be a decision variable, and let $c_i$ be the coefficient for the decision variable $x_i$.

An integer programming problem is where the goal is to:

$\text{maximize} \quad \sum_i c_ix_i$

$\text{subject to} \quad A\vec{x} \leq \vec{b}$

$\text{subject to} \quad x_i \geq 0, \quad x_i \in \mathbb Z \quad \text{for all} \ i$

where $A$ is a constraint design matrix, $\vec{x}$ is a vector of decision variables, and $\vec{b}$ is a vector of bounds.

In an integer programming problem, $c_i$ takes a scalar value.

Let us consider a separate problem below:

$\text{maximize} \quad f( \sum_i {C_ix_i} )$

$\text{subject to} \quad A\vec{x} \leq \vec{b}$

$\text{subject to} \quad x_i \geq 0, \quad x_i \in \mathbb Z \quad \text{for all} \ i$

where $C_i$ is a $p \times p$ matrix, and $f$ is a function that converts the matrix into a scalar, such as $\det$.

Is there a name for this class of problems?

Answer 1

You have is a linear integer programming problem with a generalized objective function of the form: $$g(x) = f\big( \sum_i C_i x_i \big).$$

• If $f(X) = {\rm tr}(X)$, then $g(x)$ is an ordinary linear objective function, and your problem class is just standard linear integer programming.

• If $f(X) = \det(X)$, then $g(x)$ is a general nonlinear and nonconcave objective function (super hard), but you can easily transform it to a convex objective function by using $f(X) = \log\det(X)$ instead, which notably does not affect the set of optimal solutions. This transformation would make your problem within the class of conic integer programming, requiring one semidefinite variable and one power cone (see the MOSEK modeling cookbook on log-determinant for details).

Answer 2

Technically, the first problem you described is an integer linear program. The phrase integer program can be used for any constrained optimization problem involving integer variables (and mixed integer program can be used when some but not all variables are integer). People often shorten "integer linear program", "mixed integer linear program" or some other cases (e.g., "quadratic integer program") to just "integer program", but I do not believe that the phrase "integer program" automatically restricts either the constraints or the objective to linear or quadratic functions.