# Is there a name for this type of integer programming?

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?

• @mhdadk Thank you for the pointer.
– user10646
Commented Oct 30, 2022 at 0:36

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).