The example case is as follows:
Maximize(a1 * X1 + a2 * X2 + a3 * X3 + a1 * a2 * Y12 + a1 * a3 * Y13 + a2 * a3 * Y23)
constraints are:
a1, a2, a3 are binary variable belongs to [0, 1], and
a1 + a2 + a3 = 2
Xi and Yi are real numbers given.
Thank you Gifari for your answer. However, I have more than 500 binary variables. Having ai * aj for all i and j makes the problem more complex. I am still struglling to define the dependency between two components (ai's) and (ai * aj's).
First, technical remarks.
In optimization models, variables are usually denoted by the latest letters of the Latin alphabet : x,y,z (also, t,u,v,w) and parameters when specified in the "symbolic" way, not as numbers by the initial letters: a, b, c, ,d.
Your problem is not linear since it contains products of variables like a1 * a3 (unless "linear multiplicative" stands for the case).
Returning to the main question, try this
https://download.aimms.com/aimms/download/manuals/AIMMS3OM_IntegerProgrammingTricks.pdf
7.7 Elimination of products of variables
It is described there how to replace a product of 2 binary variables with an additional binary variable and 3 simple linear constraints. You still have binary variables, but no more products of them. Of course, in your case it means that with more than 500 variables, you are going to have more than 500*499/2=124750 more additional variables (one for each product ai*aj). The "cost" of getting rid of non-linearity in fomulas may be then too large.
One more question. How does the a1 + a2 + a3 = 2 constraint look like in case of more than 3 variables? Is it still equal 2 (a1 + a2 + a3+....+a499+a500 = 2) or is it "number of variables minus one" (a1 + a2 + a3+....+a499+a500 = 499)?
Thanks Przemysław Kowalik for correcting the variable representation. I really appreciate your help. I read the documentation and I figured out how can I represent the multiplication using the suggested method.
Bur for my case, Xi is a 1-D array while Yij is a 2-D array. Yij is selected only if Xi and Xj are chosen i.e. the choice of a1 and a2 and I don't know how can I choose Yij using a new variable say t1.
Also for my case, a1 + a2 + a3 = K where K is a constant.
Each new variable which is a replacement for an "ai * aj" product and should be double-indexed for clarity of the model.
The term "ai * aj * Yij" is replaced with "tij * Yij" and new constraints connected with this replacement are added
tij
- Badges
- Science topic
- Similar topics
- Computer Science
- Program