Modeling Tricks 
===================== 

Variables 
--------- 

* If Ax ≤ b and x ≥ m, how do we model with half as many conditions? 
	
	Let y = x-m, and so replace x with y+m: 
	
	A(y+m) ≤ b i.e. Ay ≤ b - Am and (y+m) ≥ m so y ≥ 0 

* If x is free (not sign-constrained), how do we model with non-negative variables? 
	
	x = y-z, where y, z ≥ 0 are new variables. Replace all occurrences of x with (y-z) 


Objective Functions 
------------------- 

* If min f(x) is the objective, where f(x) is nonlinear, how can the objective function be 
  linearized (conditions can be nonlinear) 
	
	min f(x) --> t new variable.  min t, subject to t ≥ f(x) 


* min max objective function linearly 

	min max f_i --> t new variable, min t, t ≥ f_i for all i 

* Ratio of linear functions as objective function 

	min a*x/(b*x) --> 1/t = b*x substitution (b*x*t = 1) 
	
	min a*x*t --> w = x*t substitution, min a*w, ab*w = 1 condition 
	(we also substitute wt in b*x*t) 

	if there was other constraints, like d*x = f, instead, d*w = f*t is 
	sufficient, so x can be omitted 


Conditions 
---------- 

* absolute value conditions 


	x ≥ |f(y)| --> simply with conditions x ≥ f(y) and x ≥ -f(y) 

	x ≤ |f(y)| --> more difficult, we need a new indicator variable, d, which is 1 
								if 0 ≤ f(y), 0 otherwise. 
	
	conditions: 
		 f(y) ≤ d*M # if f(y) > 0 ==> d = 1 
		-f(y) ≤ (1-d)*M # if f(y) < 0 ==> d = 0. If f(y) = 0 ≥ d = 1 or 0!!! 
		    x ≤ f(y) + (1-d)*M # if f(y) > 0, so d=1, this condition is x ≤ f(y), 
					otherwise x ≤ f(y) + M i.e. as if it were not there 
		    x ≤ -f(y) + d*M # if f(y) < 0, so d=0, this is x ≤ -f(y), otherwise 
					x ≤ -f(y) + M i.e. as if it were not there 

	Let's choose M large enough: M = max{x, |f(y)|} is a good choice, but for each 
	condition we can also choose another M to be even more precise. 

* Alternative constraints: several conditions are given, but not all of them have to be 
  fulfilled. How can it be modeled? 

   For example: in a manufacturing problem, if we can produce from more than one 
	(interchangeable) raw materials (but only from one), then the capacity constraint 
	of one or the other must be met (non-exclusive or). 

   Let f(x) ≤ a, g(x) ≤ b be the two alternative constraints. 
   Let us have 2 new indicator variables, d_f and d_g, which is 1 if the condition is met, 
	i.e. f(x) ≤ a (g(x) ≤ b), 0 otherwise. 

   			f(x) ≤ a + (1-d_f)*M_f 
   			g(x) ≤ b + (1-d_g)*M_g 
   			d_f + d_g ≥ 1 

* Exclusive or: What if exactly one of them should met? 
	Then the previous constraints are not enough, it is also necessary to ensure that 
	d_f=1 (or d_g=1) if the condition is met (d=0 is allowed right now): 

			f(x) ≤ a + (1-d_f)*M_f
			f(x) ≥ a - d_f*M_f 
   			g(x) ≤ b + (1-d_g)*M_g 
   			g(x) ≥ b -d_g*M_g 
   			d_f + d_g = 1 

* Generalized to multiple constraints: There are N constraints, at least/at most or exactly 
  K must be met. 
	Indicator variable for each condition with the above constraints, and the sum of the 
	indicators must be ≤ / = / ≥ K  

* If then type constraints, e.g.: If we produce a product, we must produce at least K of it. 
	in general: f(x) > a --> g(x) ≤ b here we can apply what we know from logic: 
	P ==> Q is equivalent to ¬P ∨ Q so it can be modeled with alternative conditions. 

	f (x) ≤ a or g(x) ≤ b: 

			f(x) ≤ a + (1-d_f)*M_f 
   			g(x) ≤ b + (1-d_g)*M_g 
   			d_f + d_g ≥ 1 


Variables again 
------------- 

* bilinear terms: suppose we have two variables, x, y, whose product we need in the model. 
	introduce a new variable, w = x*y that models the product, and give linear  
	conditions so that it really varies like x*y. 

	- if x, y, (and thus w) are binary variables: 

		w ≥ x 
		w ≥ y 
		w ≤ x + y - 1 

	- if x is binary, y is continuous, so w is continuous. Having limits on y, 
	  i.e. L ≤ y ≤ U 

		w ≥ x*L 
		w ≥ y - U*(1-x) 
		w ≤ y - L*(1-x) 
		w ≤ x*U 

	- if x,y are continuous, there is no equivalent rewrite, only an approximation. 
	Let Lx ≤ x ≤ Ux and Ly ≤ y ≤ Uy 

		w ≥ Lx*y + Ly*x − Lx*Ly 
		w ≥ Ux*y + Uy*x − Ux*Uy 
		w ≤ Ux*y + Ly*x − Ux*Ly 
		w ≤ Lx*y + Uy*x − Lx*Uy 

	if the limits are large, we divide the variable with a smaller interval into 
	segments and write it with binary variables as many as the number of segments.