4

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.

user1868607
  • 173
  • 3

1 Answers1

4

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.

Sutanu Majumdar
  • 3,461
  • 1
  • 2
  • 11
  • A solver capable of solving linear programs should be enough, right? There are no integer variables in the model – Sune Feb 17 '23 at 15:43
  • Ipopt is a solver for large-scale (sparse) nonlinear programming, not for MIPs. – joni Feb 17 '23 at 15:43
  • Ok I misread the integer coeff as integer variable. I will edit it. Thanks for pointing it out. – Sutanu Majumdar Feb 17 '23 at 15:44
  • @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? – Sutanu Majumdar Feb 17 '23 at 15:52
  • 1
    SAS can also automatically linearize it: https://go.documentation.sas.com/doc/en/pgmsascdc/v_036/casmopt/casmopt_optmodel_details57.htm – RobPratt Feb 17 '23 at 16:05
  • what's the easiest way to use these? is there some online platform? – user1868607 Feb 17 '23 at 16:55
  • Google Colab, you can install import docplex & gurobi and may be others as well. – Sutanu Majumdar Feb 17 '23 at 17:15
  • I did not understand how can I transform the problem into a linear optimization problem. Could you be more specific? – user1868607 Feb 18 '23 at 09:52
  • Are you aware of objectives, constraints? There are some books like Winston's Operations Research to start with – Sutanu Majumdar Feb 18 '23 at 14:25
  • I will try & post a code using Gurobi. It will be in python, on a similar toy problem – Sutanu Majumdar Feb 18 '23 at 14:27
  • yes, i think i know the basics of linear optimization. But it is not clear to me how to transform $|x|_{\infty}$ into a linear objective. – user1868607 Feb 18 '23 at 16:06
  • Ok as I said define a new variable $z$ and for every $ x$ create 2 new constraints as in the answer. Basically you are saying that variable $z$ should be greater than every $x$ no matter $x$ is positive/negative. Then minimize z. – Sutanu Majumdar Feb 18 '23 at 16:55