I have the following optimization problem in binary variables $x_{ij}$ and $y_i$.

$$\begin{array}{ll} \text{minimize} & \displaystyle\sum_{i} y_i \max_j \big( c_{ij} x_{ij} \big)\\ \text{subject to} & \sum_{j}x_{ij}=1\\ & \sum_{i}y_i \leq 1\\ & y_i \geq x_{ij}\end{array}$$

where $c_{ij} \in \mathbb Z$ are given. Is it possible to linearize this objective? Or to make it convex?

  • 1
    $\begingroup$ It might be helpful to post the whole program. In many cases the constraints helps to simplify the program. $\endgroup$ Aug 11, 2018 at 3:30
  • 1
    $\begingroup$ Are you minimizing or maximizing the objective? $\endgroup$ Aug 11, 2018 at 9:26
  • $\begingroup$ I am minimizing the objective. See the edits. $\endgroup$
    – zdm
    Aug 11, 2018 at 12:55
  • $\begingroup$ Binary here means $\{0,1\}$ $\endgroup$
    – zdm
    Aug 12, 2018 at 13:21
  • $\begingroup$ Is $c_{ij} > 0$? Also, your constraints are infeasible unless there is only one $i$. For each $i$, the first constraint forces $x_{ij}=1$ for some $j$, and so the third constraint forces $y_i = $ for all $i$. $\endgroup$
    – RobPratt
    Aug 19, 2019 at 19:32

1 Answer 1


Start by the rewriting the objective as $\sum y_i t_i$ subject to the constraints $\max_{j} x_{ij}c_{ij} \leq t_i$.

The max constraints are modelled using standard epi-graph reformations, i.e. $x_{ij}c_{ij} \leq t_i$. The binary times continuous $y_i t_i$ terms you can do using standard big-M models, by introducing a new variable $w_i$ satisfying $-M(1-y_i) \leq w_i - t_i \leq M(1-y_i), -My_i \leq w_i \leq My_i$. Using the structure in your constraints, you can probably simplify things considerably, this is the brute-force model.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .