0
$\begingroup$

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?

Improve this question
$\endgroup$
  • 1
    $\begingroup$ It might be helpful to post the whole program. In many cases the constraints helps to simplify the program. $\endgroup$ – callculus Aug 11 '18 at 3:30
  • 1
    $\begingroup$ Are you minimizing or maximizing the objective? $\endgroup$ – Johan Löfberg Aug 11 '18 at 9:26
  • $\begingroup$ I am minimizing the objective. See the edits. $\endgroup$ – zdm Aug 11 '18 at 12:55
  • $\begingroup$ Binary here means $\{0,1\}$ $\endgroup$ – zdm Aug 12 '18 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 '19 at 19:32
2
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.