2
$\begingroup$

I have a complicated non-linear objective function of positive integer variables subject to linear constraints:

$\mathop {Min}\limits_{\underline x} f(\underline x)$

s.t.

$A\underline x\leq \underline b$

$\underline x \in \mathbb{Z}$, $\underline x \geq 0$. $f(\underline x)=g(\underline x)+h(\underline x)+p(\underline x)+q(\underline x)$.

For the small version of the problem where A is 17×48, $g$ is defined as follows.

\begin{equation}\label{Ca1} C_a^1=\frac{1}{\frac{1}{\sum_{i=1}^{4} x_{i}C_i+(3-\sum_{i=1}^{4} x_{i})C_5}+\frac{1}{\sum_{i=5}^{8} x_{i}C_i+(3-\sum_{i=5}^{8} x_{i})C_5}} \end{equation}

\begin{equation}\label{Ca2} C_a^2=\frac{1}{\frac{1}{\sum_{i=9}^{12} x_{i}C_i+(3-\sum_{i=9}^{12} x_{i})C_5}+\frac{1}{\sum_{i=13}^{16} x_{i}C_i+(3-\sum_{i=13}^{16} x_{i})C_5}} \end{equation}

\begin{equation}\label{Cb1} C_b^1=\frac{1}{\frac{1}{\sum_{i=17}^{20} x_{i}C_i+(3-\sum_{i=17}^{20} x_{i})C_5}+\frac{1}{\sum_{i=21}^{24} x_{i}C_i+(3-\sum_{i=21}^{24} x_{i})C_5}} \end{equation}

\begin{equation}\label{Cb2} C_b^2=\frac{1}{\frac{1}{\sum_{i=25}^{28} x_{i}C_i+(3-\sum_{i=25}^{28} x_{i})C_5}+\frac{1}{\sum_{i=29}^{32} x_{i}C_i+(3-\sum_{i=29}^{32} x_{i})C_5}} \end{equation}

\begin{equation}\label{Cc1} C_c^1=\frac{1}{\frac{1}{\sum_{i=33}^{36} x_{i}C_i+(3-\sum_{i=33}^{36} x_{i})C_5}+\frac{1}{\sum_{i=37}^{40} x_{i}C_i+(3-\sum_{i=37}^{40} x_{i})C_5}} \end{equation}

\begin{equation}\label{Cc2} C_c^2=\frac{1}{\frac{1}{\sum_{i=41}^{44} x_{i}C_i+(3-\sum_{i=41}^{44} x_{i})C_5}+\frac{1}{\sum_{i=45}^{48} x_{i}C_i+(3-\sum_{i=45}^{48} x_{i})C_5}} \end{equation}

\begin{equation}\label{Ca} C_a=C_a^1+C_a^2 \end{equation} \begin{equation}\label{Cb} C_b=C_b^1+C_b^2 \end{equation} \begin{equation}\label{Cc} C_c=C_c^1+C_c^2 \end{equation} \begin{equation}\label{g} g(\underline{x})=(C_a+C_b+C_c)\sqrt{[C_a-\frac{1}{2}(C_b+C_c)]^2+(C_b-Cc)^2} \end{equation}

where $C_1$...$C_{48}$ are constant and known. $h$, $p$ and $q$ are as complicated.

In Matlab,each of $g,h,p,q$ is defined by a function which employs various other functions which contain many loops for different elements of $\underline x$.

Size of $A$ is in the order of 100 $\times$ 2000. I tried first to solve the problem in Matlab, using the ga function. Unfortunately, the solutions obtained for several runs never satisfied the constraints.

I have successfully implemented an algorithm in Matlab where in each iteration a random solution that satisfies the constraints is generated and $f(\underline x)$ is evaluated using multiple functions defined. Using a large number of iterations, say 1e6, I could find a reasonable yet not a globally optimal solution. My next plan was to use the CPLEX solution pool. For small $A$ and $b$, it was possible to have all the solutions of inequality $A\underline x\leq \underline b$, import these solutions as a CSV file in Matlab and evaluate them one by one so that the least objective function gives the globally optimal solution. This, however, does not work for actual $A$ and $b$ which make the CPLEX out of memory. My idea was to use an incumbent filter so that non-optimal solutions of $A\underline x\leq \underline b$ get discarded and therefore the memory problem gets resolved. For example the solutions for which $f(\underline x)>c$, where constant $c$ is heuristically defined, can be discarded. My question is:Is there a way to define my complicated objective function in GAMS environment the way I did in Matlab? Have you faced a similar situation which can be referred to so that I have a clue?

$\endgroup$
7
  • 5
    $\begingroup$ Can you tell us more about these mystery functions, g, h, p, q? Highly relevant to effective guidance. "employs various other functions which contain many loops for different elements of $x$" is a rather vague description. $\endgroup$ Jun 19 at 13:02
  • $\begingroup$ I'm not a MATLAB user, but according to the documentation of the ga() function, it should be able to accommodate linear constraints and integrality restrictions. You might want to ask MATLAB experts to check your code. $\endgroup$
    – prubin
    Jun 19 at 15:23
  • $\begingroup$ @MarkL.Stone I added the definition of $g$ as requested. Thanks! $\endgroup$ Jun 19 at 15:40
  • $\begingroup$ @prubin In Matlab I face the following: "Optimization terminated: average change in the penalty fitness value less than options.Fu​nctionTole​rance but constraints are not satisfied." It means that ga cannot handle this constrained optimization which is confirmed by looking into Ax-b after obtaining x. However my question is how I can utilize the solution pool of CPLEX while defining the objective function and not recording the non-optimal solutions of Ax≤b. $\endgroup$ Jun 19 at 15:43
  • 1
    $\begingroup$ You can try a MINLP solver. Either a global one, or one able to use callbacks as input neos-server.org/neos/solvers/index.html sections "Global optimization" and "Mixed-integer nonlinearly constrainted optimization" $\endgroup$
    – fontanf
    Jun 19 at 16:39

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.