Optimization by Problem Partitioning using Simulated Annealing and GAMS Programming

By Dr Muhammad Al-Salamah

Abstract

We shown how a difficult optimization problem can be converted into two subproblems, on the hope that it will be easier to solve.  One subproblem is solved using a meta-heuristic procedure, simulated annealing in the current case, and the other will be solved using one of the solvers available under GAMS.

Simulated Annealing in Optimization

Simulated annealing has been used extensively in optimization, in which the problem is nonlinear with large number of constraints, discontinuous functions of either objective function or constraints, or large MIP. The motivation of simulated annealing and the steps of the procedure can be found in many books and websites. We concentrate here only on programming simulated annealing under GAMS environment. Simulated annealing has been successfully applied to solve unconstrained optimization problems with simple bounds. Problems with constraints are not natural extension of unconstrained problems, and they required conditioning before simulated annealing can be used to derive an acceptable solution to them. One conditioning technique that has been widely used is the penalty functions technique, by which the constrained problem is converted to a problem with penalty terms to the objective function for violating the constraints. Some commercial optimization packages utilize this technique.

We show how an optimization problem can be converted into two subproblems that are linked by one variable. This variable is the decision variable for one subproblem and parameter for the another subproblem. One of the subproblems is an unconstrained problem with simple bounds and the other subproblem is a more complicated problem with the original constraints.

Optimization Problem

Consider the constrained optimization problem

NLPO

This problem has three variables, and clearly it is nonlinear in objective function and two of the three constraints.  The solution of this problem is easy to get, given the power we have from modern solvers.  But, we will use this problem to illustrate problem partitioning and the simulated code in GAMS code.

Consider the problem again, and notice that it can be partitioned into two optimization problems as follows.  There are three variables x₁, x₂, and x₃; and any one of them can be the link variable between the two subproblems.  It will be better if x₃ is chosen to be the link variable, since it appears only once the problem and also its order is one.  If one of the other variables x₁ or x₂ is picked up for the link variable, then it is very hard to predict whether the optimization of the subproblems is going to converge to a reasonable solution.  Let y = x₃ and the problem NLPO becomes:

Therefore, the two subproblems are:

Subproblem 1:

Subproblem 2:

Subproblem 1 consists of a univariate function with simple bounds.  The bounds l and u are chosen carefully so they do not interfere when finding the optimal value of y.  Subproblem 2 is easier to solve the original problem NLPO since it has one variable less.

Solution Procedure of Simulated Annealing

The solution procedure to solve NLPO involves solving the two subproblems iteratively.  Subproblem 1 has only simple bounds, hence simulated annealing now can be used to solve it. Subproblem 2 can be solved now with less effort utilizing one of NLP solvers available under GAMS environment.

The illustration of the solution procedure is shown below.

Simulated Annealing GAMS Code

The GAMS code incorporating simulated annealing and calling NLP GAMS solver to solve problem NLPO is:

option seed=4;
variables x1,x2,objfun;

parameter y;

equations obj,con1,con2,con3;

obj..objfun=e=exp(x1+x2)-28*x2;
con1..power(x1-3,2)+power(x2-5,2)=l=y;
con2..14*x1-6*x2=e=12;
con3..-2*power(x1,2)+4*x1*x2-power(x2,2)=g=0;

model sales/all/;

** start of simulated annealing procedure

parameter TMP,y_best,index_l,objfun_best,y_current,objfun_current,index_i;
TMP=30;
y=round(uniform(-20,20));
solve sales using nlp minimizing objfun;
y_best=y;
objfun_best=objfun.l;
y_current=y;
objfun_current=objfun.l;
index_i=0;
while (index_i<=20,
index_i=index_i+1;
index_l=0;
while(index_l<=5,
index_l=index_l+1;
y=round(uniform(-20,20));
solve sales using nlp minimizing objfun;
if(exp((objfun_current-objfun.l)/Tmp)>uniform(0,1)<=,y_current=y;
objfun_current=objfun.l;););
if(objfun_current<=objfun_best,y_best=y_current;objfun_best=objfun_current;);
TMP=0.85*TMP;);

** end of simulated annealing procedure

display objfun_best,x1.l,x2.l,y_best;

Simulated Annealing Solution

The solution of the problem NLPO using BARON solver is

In the above code, the bounds on y have been put at -20 and 20.  The solution of the partitioned problem using the combination of simulated annealing and GAMS solver is

For this particular case, the time it took the solver to solve NLPO is about zero (very short).  However, the partitioned problem needed 3 seconds to solve.  The solution time of simulated annealing is dependent on the size of the outer and inner loop of the procedure; hence, solution time vs quality of solution time has to be balanced.

Created in 2008