4
$\begingroup$

I want to solve the following optimization problem

min $\|x\|_{\infty}$ such that $Ax \ge b, x \ge 0$

where $A$ is a matrix with integer coefficients and $b$ is a vector with integer coefficients.

Here $\|x\|_{\infty} = \max\{|x_1|,\ldots,|x_n|\}$.

What kind of software could I use for that.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
4
$\begingroup$

Ok any solver that supports LP can solve it like IPOPT, Gurobi, Cplex, SAS-OR (I think academic or free editions available on google colab). As for give problem its called minmax (minimize the maximum). Generally its like introduce a variable $z$ and add constraints to the existing ones with $A$ and $b$
$ x_i \le z$
$-x_i \le z \ \forall i$
Then min $z$

BTW: Gurobi and SAS-OR has an in-built constraint to deal with abs. you wont need 2 constraints per $i$. CPLEX will also have one.

Improve this answer
$\endgroup$
12
  • $\begingroup$ A solver capable of solving linear programs should be enough, right? There are no integer variables in the model $\endgroup$
    – Sune
    Commented Feb 17, 2023 at 15:43
  • $\begingroup$ Ipopt is a solver for large-scale (sparse) nonlinear programming, not for MIPs. $\endgroup$
    – joni
    Commented Feb 17, 2023 at 15:43
  • $\begingroup$ Ok I misread the integer coeff as integer variable. I will edit it. Thanks for pointing it out. $\endgroup$
    – Sutanu Majumdar
    Commented Feb 17, 2023 at 15:44
  • $\begingroup$ @joni, I admit never used IPOPT but often see it with COIN-OR Project. I get it uses Interior Points method, that facilitates solving large scale problems. But doesn't it also tackle discrete problems? $\endgroup$
    – Sutanu Majumdar
    Commented Feb 17, 2023 at 15:52
  • 1
    $\begingroup$ SAS can also automatically linearize it: go.documentation.sas.com/doc/en/pgmsascdc/v_036/casmopt/… $\endgroup$
    – RobPratt
    Commented Feb 17, 2023 at 16:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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