5
$\begingroup$

This is my first real optimisation problem I formulated and now trying to solve by using AMPL.

The following objective function is from a linear 0-1 LP means all variables $x_i^b\in\{0,1\}$, with $i\in[1,n]$ and $b$ referring to the type of the node, which means $0$ and $1$ say a node is or is not of a certain type.

The objective function is as follows with $A$ a set of nodes, $N[a]$ a set of all neighbours of $a$ including $a$, and $n$ a given number of types:

$$\min - \sum_{a\in A}f\left(\frac1n\sum\limits_{i=1}^nf\left(\sum\limits_{b\in N[a]}x_i^b\right)\right)$$

with

$$ f:\mathbb{R}\mapsto\{0,1\}\\ f(x):=\begin{cases}0,&x<1\\1,&x\geq 1\end{cases} $$

I already heard that AMPL doesn't support the definition of functions/methods and that I have to use the Big M method to create this objective function. I couldn't really figure out yet how to use the method to replace my case distinctions...

$\endgroup$
3
$\begingroup$

Let $\rho$ be some small value. \begin{align}M \times f(x) &\geq x - 1 + \rho\\M \times (1 - f(x)) &\geq 1 - x - \rho\end{align}

Here is the small working code in Python pulp

import pulp as pl

prob = pl.LpProblem("Problem", pl.LpMinimize)
x = 1
f = pl.LpVariable("f_{0}", 0, 1, pl.LpBinary)
prob += f
M = 100
prob += M * f >= x - 1 + 0.001
prob += M * (1 - f) >= 1 - x - 0.0001

print(prob)
prob.solve()

for v in prob.variables():
    print(v.name, "=", v.varValue)
| improve this answer | |
$\endgroup$
  • $\begingroup$ Can I ask for another detail - I am very interested in the "WHY" so why is it not possible to solve objective functions with case distinctions directly? $\endgroup$ – baxbear Feb 14 at 12:31

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.