1

We are given a system of inequalities expressed in the following way: $$ Ax> \underline{k}$$ where $A\in\mathbb{M}_{n,m(\mathbb{R})}$, with n>m, and $\underline{k}=(k,k,\ldots,k)\in\mathbb{R}^n$.

In general, the system might or might not admit solutions. I would like to find a solution $x\in\mathbb{R}^m$ that minimizes the number of violated inequalities. It's the first time I have to deal with this sort of discrete optimization problems and to be honest I have no idea where to start from.

If you could at least direct me a bit, that would be very helpful.

Thank you!

fatoddsun
  • 2,169

1 Answers1

0

$Ax\gt k$ is a difficult concept in optimization. Usually we deal with $Ax\ge k$. (If needed you can add a small number $\varepsilon>0$ to $k$; note also that solvers typically employ a feasibility tolerance, so $\varepsilon$ should be larger than that).

So, assume we have $Ax\ge k$. Next we can do $$ \begin{align} \min\> & \sum_i \delta_i \\ &\sum_j a_{i,j} x_j \ge k - \delta_i M \\ &\delta_i \in \{0,1\} \end{align} $$

Here $M$ is a large enough number.

Erwin Kalvelagen
  • 4,267