Chapter 2 linear programming problems

Step 2.1. Generate y
ing box DB.

j

∈ DB using uniform distribution on the bound-

Step 2.2. Test feasibility of y

j

.

Step 2.3. If y

j
is feasible, go to step 2.4. Otherwise, go to step 2.1.

40

2. Computation in DP:


Step 2.4. Compute g_j = b′y

j
, j = 1,2,··· ,j_o.
Step 2.5. g_n−o = min_j(g_j), j = 1,2,··· ,j_o and g_n−o = associated y
with g_n−o.

3. Termination in DP:

j

Step 2.6. Keep the values of y

n−o

, g_n−o and stop.

• Termination in restarting: if (g_n−o − z_n−o) ≤ ǫ, small positive value, or

and stop restart.
the number of restarting get equal to its initial value, then output the values of z_n−o, x_n−o, g_n−o, y
n−o
,