Constrained optimization topics

Question

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.

• Yuval Filmus: 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.

Answer 1

This can be formulated as a mixed-integer quadratically constrained quadratic programming (MIQCQP) problem, integer programming with quadratic constraints and a quadratic objective function. You can find off-the-shelf solvers out there, and I think some of them support MIQCQP. Unfortunately MIQCQP is a pretty hard problem, so it's hard to know whether this will be effective, for the size of problem you have. But it could be worth a try.

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.

• gia: Thank you!, cant modify the rules, can only move them around, like your max rewrite. Ill read up on that scary name.