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?
optimization linear-programming mixed-integer-programming terminology
edited Mar 5 at 17:59
John Lawrence Aspden
asked Mar 5 at 14:00
John Lawrence AspdenJohn Lawrence Aspden
$\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
$\begingroup$ Stackexchange uses MathJax to implement LaTeX equations. $\endgroup$ – Brian Borchers Mar 6 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)<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.
answered Mar 5 at 20:42
Richard ZhangRichard Zhang
$\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
Not the answer you're looking for? Browse other questions tagged optimization linear-programming mixed-integer-programming terminology or ask your own question.
Anisotropic cover with n-cuboids
Choosing subset of vectors to approximate a subspace
Does this "reverse binary search" have a name?
Inverted value is not consistent with expectation
Breaking symmetries in a (binary) integer program
Loooking for name of this geometrical optimization technique
Approach to handle a quadratic constraint xy <= z
Why can't we discretize continuous domains in distributed non-convex constraint optimization problems?
Optimization of a blackbox function with an equality constraint?
Is there a name for this integer linear optimization problem?