BIM production for worst case#

# install dependencies and select solver
%pip install -q amplpy

SOLVER = "highs"

from amplpy import AMPL, ampl_notebook

ampl = ampl_notebook(
    modules=["highs"],  # modules to install
    license_uuid="default",  # license to use
)  # instantiate AMPL object and register magics

Minmax objective function#

Another class of seemingly complicated objective functions that can be easily rewritten as an LP are those stated as maxima over several linear functions. Given a finite set of indices \(K\) and a collection of vectors \(\{c_k\}_{k \in K}\), the minimax problem given by

\[ \begin{align} \min \; \max_{k \in K} \; c^\top_{k} x \end{align} \]

General expressions like the latter can be linearized by introducing an auxiliary variable \(z\) and setting

\[\begin{split} \begin{align*} \min \quad & z \\ \text{s.t.} \quad & c^\top_{k} x \leq z \qquad \forall\, k \in K. \end{align*} \end{split}\]

This trick works because if all the quantities corresponding to different indices \( k \in K\) are below the auxiliary variable \(z\), then we are guaranteed that also their maximum is also below \(z\) and vice versa. Note that the absolute value function can be rewritten \(|x_i|= \max\{x_i,-x_i\}\), hence the linearization of the optimization problem involving absolute values in the objective functions is a special case of this.

BIM problem variant: Maximizing the lowest possible profit#

In the same way we can minimize a maximum like above, we can also maximize the minimum. Let us consider the BIM microchip production problem, but suppose that there is uncertainty regarding the selling prices of the microchips. Instead of just the nominal prices 12 € and 9 €, BIM estimates that the prices may more generally take the values \(P=\{ (12,9), (11,10), (8, 11) \}\). The optimization problem for a production plan that achieves the maximum among the lowest possible profits can be formulated using the trick mentioned above and can be implemented in AMPL as follows.

%%writefile bim_maxmin.mod

var x1 >= 0;
var x2 >= 0;
var z;

set costs dimen 2;

maximize profit: z;
    
s.t. maxmin {(c1,c2) in costs}:
    z <= c1 * x1 + c2 * x2;

s.t. silicon: x1 <= 1000;
s.t. germanium: x2 <= 1500;
s.t. plastic: x1 + x2 <= 1750;
s.t. copper: 4 * x1 + 2 * x2 <= 4800;

Writing bim_maxmin.mod

def BIM_maxmin(costs):
    ampl = AMPL()
    ampl.read("bim_maxmin.mod")

    ampl.set["costs"] = costs

    return ampl


m = BIM_maxmin([[12, 9], [11, 10], [8, 11]])
m.option["solver"] = SOLVER
m.solve()
print(
    "x=({:.1f},{:.1f}) revenue={:.3f}".format(
        m.var["x1"].value(), m.var["x2"].value(), m.obj["profit"].value()
    )
)

HiGHS 1.5.1: HiGHS 1.5.1: optimal solution; objective 17500
4 simplex iterations
0 barrier iterations
x=(583.3,1166.7) revenue=17500.000