How to formulate case distinctions in AMPLs objective function?

Question

This is my first real optimization 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.

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? — EhsanK, Jan 30 '20 at 14:19
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$. — ə̷̶̸͇̘̜́̍͗̂̄︣͟, Jan 30 '20 at 19:57
Note that if M is set too large, you can run into numeric problems - see e.g. https://groups.google.com/forum/#!topic/ampl/3O7DsZuXIi4 so be careful to check that your solution really does satisfy the constraints. — GB supports the mod strike, Jan 31 '20 at 01:56
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 - — baxbear, Jan 31 '20 at 13:46

score 3 · Accepted Answer · edited Jan 30 '20 at 19:55

3

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)

edited Jan 30 '20 at 19:55

ə̷̶̸͇̘̜́̍͗̂̄︣͟

5,412
5
22
55

answered Jan 30 '20 at 09:59

ooo

1,589
4
12

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? – baxbear Feb 14 '20 at 12:31

score 1 · Answer 2 · answered Feb 26 '24 at 17:01

You can express this objective using AMPL's builtin if-then-else expression. I think the following corresponds to what you want to write:

param n;
set A;
set N {A} within A;
var x {1..n, A};
maximize ObjFunc:
   sum {a in A} (
      if (1/n) * sum {i in 1..n} (
         if sum {b in N[a]} x[i,b] >= 1 then 1 else 0 )
      >= 1 then 1 else 0 );

General support for if-then-else is present in current AMPL MIP solver distributions (except that for CPLEX this feature is still in beta and it's necessary to use cplexmp rather than cplex to get it).

How to formulate case distinctions in AMPLs objective function?

2 Answers2