# What is the name for this type of constraint?

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?

• Please use mathematical notation to explain the constraint that you're trying to achieve. – Brian Borchers Mar 6 '19 at 0:58
• 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? – John Lawrence Aspden Mar 6 '19 at 15:28
• Stackexchange uses MathJax to implement LaTeX equations. – Brian Borchers Mar 6 '19 at 17:04

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) 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) 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) where we have conveniently used $$c$$ as the Big-M parameter.