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$
4
  • $\begingroup$ Welcome to OR.SE! Have you checked other questions on the site, such as this one: In an integer program, how can I “activate” a constraint only if a decision variable has a certain value? $\endgroup$
    – EhsanK
    Jan 30 '20 at 14:19
  • $\begingroup$ I suppose you mean $\min \sum\limits_{a\in A}f\left(\dfrac1n\sum\limits_{i=1}^nf\left(\sum\limits_{b\in N[a]}x_i^b\right)\right)$ as the minus sign would indicate $\max$. $\endgroup$
    – TheSimpliFire
    Jan 30 '20 at 19:57
  • $\begingroup$ Note that if M is set too large, you can run into numeric problems - see e.g. groups.google.com/forum/#!topic/ampl/3O7DsZuXIi4 so be careful to check that your solution really does satisfy the constraints. $\endgroup$ Jan 31 '20 at 1:56
  • $\begingroup$ yeah it has been a max but I thought to remember, that I have to minimise the objective function when all constraints are $\geq C$ maybe I was wrong (therefore I turned the max + to min - $\endgroup$
    – baxbear
    Jan 31 '20 at 13:46
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)
$\endgroup$
1
  • $\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 '20 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.