5
$\begingroup$

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.

$\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
    Commented Jan 30, 2020 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
    Commented Jan 30, 2020 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$
    – G_B
    Commented Jan 31, 2020 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
    Commented Jan 31, 2020 at 13:46

2 Answers 2

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
    Commented Feb 14, 2020 at 12:31
1
$\begingroup$

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).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.