Heuristic Search Methods
Dennis Blumenfeld · 2009
Let x1, x2, …, xN be N decision variables in an optimization problem. In the general case, the problem is to search for values of the variables, x1, x2, …, xN, to maximize (or minimize) a given general function of the variables, subject to a given set of general constraints on the variables. The general formulation for the maximization problem is ( )1 2Maximize , , , Nf x x x… (13.1) subject to the M constraints , , , , , , , , , g x x x b g x x x b g x x x b ⎫≤ ⎪⎪≤ ⎪⎬⎪⎪⎪≤ ⎭ … … … (13.2) where f(.) and gi(.) (i = 1, 2, …, M) are general functions bi (i = 1, 2, …, M) are constants Expressing the decision variables in vector notation: x x x ⎛ ⎞⎜ ⎟⎜ ⎟⎜ ⎟= ⎜ ⎟⎜ ⎟⎜ ⎟⎝ ⎠ x (13.3) the general formulation for the maximization problem is written as Maximize ( )f x (13.4) subject to the constraints ( ) ( 1, 2, , )i ig b i M≤ =x … (13.5) For the minimization problem, the corresponding general formulation is Minimize ( )f x (13.6) subject to the constraints ( ) ( 1, 2, , )i ig b i M≥ =x … (13.7) A set of values for x that satis es all the constraints in a given problem is a feasible solution. The collection of all feasible solutions is the feasible search space.