5
$\begingroup$

I have what would be a straightforward mixed-integer linear programming problem, except for the fact that some of the constraints are of the form $f(x_1,x_2,x_3,\ldots,x_n) < c$, where $f$ is 'take the maximum of the largest coordinate and the sum of all the smaller ones'

In lisp:

(defn f [& l]
  (let [sl (reverse (sort l))]
    (max (first sl) (reduce + (rest sl)))))

(f 1 2 3 4 5) -> 10

In three dimensions e.g. I think I can rephrase this for e.g. $f<10$ as

(defn constraint [x,y,z]
  (or
   (and (<= x 10)
        (<= (+ y z) 10))
   (and (<= y 10)
        (<= (+ x z) 10))
   (and (<= z 10)
        (<= (+ x y) 10))))

Which is clearly the union of $3$ (or $n$) convex objects (prisms).

Is there a name for this type of constraint? Are there techniques and packages for solving these kinds of problems?

$\endgroup$
  • $\begingroup$ Please use mathematical notation to explain the constraint that you're trying to achieve. $\endgroup$ – Brian Borchers Mar 6 at 0:58
  • $\begingroup$ I don't know how! Even to write the first version. The second one would be easy in TeX, can I just type that in here? $\endgroup$ – John Lawrence Aspden Mar 6 at 15:28
  • 2
    $\begingroup$ Stackexchange uses MathJax to implement LaTeX equations. $\endgroup$ – Brian Borchers Mar 6 at 17:04
4
$\begingroup$

I would call the constraint "upper- and lower-bounds on the maximum element." Note that you are actually dealing with two separate constraints. Define the max element function as follows $$ \max:\mathbb{R}^{n}\to\mathbb{R}\qquad\max(x)\equiv\max_{i\in\{1,\ldots,n\}}x_{n}. $$ Your first constraint is "take the max element and ensure that it is less than $c$": $$ \max(x)<c,\tag{1} $$ while the second is "take the sum, subtract the max element, and ensure that the result is less than $c$": $$ \mathbf{1}^{T}x-\max(x)<c,\tag{2} $$ where $\mathbf{1}=[1,\ldots,1]^{T}$ is the usual column vector of ones. Observe that (1) is a convex upper-bound on $\max(x)$ while (2) is a nonconvex lower-bound.

Such problems with a fixed upper-bound have a very elegant solution via the Big-M method. Let $M$ be an arbitrary large number that satisfies $\max(x)\le M$ for all possible choices of $x$. Then it is easy to verify that $$ \alpha=\max(x)\le M\quad\iff\quad\alpha\ge x\ge\alpha-(1-z)M,\quad\mathbf{1}^{T}z=1,\quad z\in\{0,1\}^{n}. $$ Using the above identity, we can implement (1) and (2) exactly as the following mixed integer constraints $$ f(x)<c\quad\iff\quad\begin{array}{c} \mathbf{1}^{T}x-c<\alpha<c\\ \alpha-(1-z)c\le x\le\alpha\\ \alpha\in\mathbb{R},\quad z\in\{0,1\}^{n} \end{array} $$ where we have conveniently used $c$ as the Big-M parameter.

$\endgroup$
  • $\begingroup$ Thank you so much! This looks brilliant. Is there a name for what you've just done or is it just obvious to someone with the relevant skills? $\endgroup$ – John Lawrence Aspden Mar 8 at 14:40
  • $\begingroup$ You're welcome! Yes, it's a standard technique in industrial engineering / operations research. The idea is to implement an "or" statement using binary variables. Our students can identify such transformations quickly only because we put them in the final exam! See e.g. slide 12 in ocw.mit.edu/courses/sloan-school-of-management/… $\endgroup$ – Richard Zhang Mar 8 at 18:00

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.