# Constrained optimization topics

Given functions $f, p, c$, a matrix $X$, and vectors $C,D,E$.

I want to maximize the multivariable function $f(X)$, where $X$ is a $p \times q$ binary matrix ($X_{ij}$ is 0 or 1). So, $p\cdot q$ variables. The function $f(X)$ is given by $$f(X) = \sum_j \sum_i C_{ij} X_{ij} - \sum_j p(X,j),$$ where $C$ is a matrix of constants and $p$ is a penalty function (basically could be rewritten as a loose constraint as far as I can tell): $$p(X,j) = \max(0, \sum_i X_{ij} - D_j)^2,$$ where $D$ is a vector of constants.

As hard constraints we got that $X_{ij}$ is binary, and $$c_i(X) = \sum_j X_{ij} \leq E_i,$$ where $E$ is a vector of constants

I found linear programming is a topic that solves problems like this, and then found constrained optimization which would be more or less what I want, although I don't know how to write max() into inequalities. I suppose I could try to split the solution if the conditional branch was enforced on a single variable, but there are several conditionals at the same time anyway. Out of my searches the penalty method looks extremely similar to my equations, but there's the hard constraints that haven't been merged into the main function.

I request the exact topic I can research, I'm a bit confused as all of this is new to me and I'm not sure I'm studying the right topics.

• Linear programming is not what you're after, since it optimizes over real values, whereas you optimize over integers . The integer version of linear programming is integer programming, but your objective function is not linear, so even this doesn't apply. A more general area is combinatorial optimization, but that might be too general. – Yuval Filmus May 20 '17 at 20:45

You can encode the max by the two constraints $p_j \ge 0$, $p_j \ge (\sum_i X_ij - D_j)^2$, where $p_j$ is a variable representing $p(X,j)$. Since you're going to minimize a sum of $p_j$'s, this suffices (the minimization objective will chose the smallest $p_j$ that satisfies both inequalities, which is the max).
Alternatively, if you're willing to remove the "squaring" in the definition of $p(X,j)$, this could be formulate as an instance of integer linear programming.