Are fractional objective functions possible?
Hi all,
I am working on a project that involves finding the minimum energy solution to a fractional objective function. I am looking for thoughts, ideas, references or help on implementing such an objective function for use with the quantum annealer.
Here's some additional info which may be helpful to know:
- The fractional objective function consists of separate functions for the numerator and the denominator. The goal is to minimize the ratio between these two functions.
- The numerator and denominator functions yield values greater than zero for valid solutions to the problem. So the optimal solution to the fractional objective will give a value as close as possible to zero.
- The numerator and denominator functions rely on the same set of binary variables.
- The numerator and denominator functions are independent from each other.
- Since I don't have that many binary variables it is still feasible to evaluate the objective functions by brute force.
So, just as an example, considering the following fractional objective function :
minimize(F)
with
F = N/D
with
N = 1*q1 + 2*q2 + 3*q1*q2 + 4*q2*q3 + 5*q1*q2*q3...
D = 6*q1 + 4*q2 + 7*q1*q2 + 3*q2*q3 + 1*q1*q2*q3...
with all variables q being binary {0,1}
How would I go about finding an equivalent function that isn't written as a fraction? As I understand it, there is no way to directly input the fractional objective, since it doesn't directly fit into a QUBO formulation.
I have tried things like rewriting the objective as (N-lambda*D) or (-N*D) but these manipulations tend to change which solution is the most optimal. (And what would be a valid value for lambda anyway!?)
There are some research papers that discuss translating linear fractional programming (LFP) problems to linear programming (LP) problems. However, I am not sure if this particular problem qualifies as LFP, since there are some high-order binary variable multiplications in the objective functions. Given that a non-fractional objective function can be formulated, I intend to take care of these high-order terms via quadratization methods using auxiliary variables, i.e. using dimod.make_quadratic().
With that said, does anybody have any ideas?
Kind regards,
Kevin
Comments
Hello,
I reached out to a few of my colleagues to learn more about possible solutions to your problem.
It sounds like this is a tricky problem to implement on the QPU.
There were a few ways suggested that you might try to approach this.
One includes converting the numerator and denominator from a higher-order function to a linear function and then finding the minimum of a fractional linear function.
The step of going from higher-order to linear will require the addition of auxiliary variables, potentially a large number of the them.
This paper on cell formation has a fractional objective function:
https://www.researchgate.net/publication/271916515_Exact_model_for_the_cell_formation_problem
One method would be to formulate a minimization for N=D*z.
There are a few challenges here.
First, z is continuous.
With some effort it would be possible to discretize z to a given precision, which would come at a cost.
Second, D*z is a higher-order polynomial.
This term can be converted to reduce the order of the term, which will also come at a cost.
Another suggestion is to find some way of converting the objective function to a QUBO.
This might require converting D to a polynomial problem and then reducing the whole problem to a QUBO.
Converting to a QUBO would be quite costly, and might not fit directly on the QPU, but perhaps might be a candidate for the hybrid solver (i.e. LeapHybridSampler).
These are just some thoughts.
Please let us know what you try out, and if you get stuck with the libraries.
Hi David,
Thanks for your effort and suggestions! You are correct that if we were to replace all second-order (and higher) terms with new auxiliary linear terms, then the problem would definitely fall in the Linear Fractional Programming category. This would then probably allow for the conversion methods described in literature to be used, such as:
However I do think that this would very greatly increase the complexity of the problem. In my particular case, my simplest problem has 6 binary variables, with the objective containing all possible combinations of terms from 1st order up to 6th order. Unless I'm mistaken, that means a total of 63 different terms, including the original 6 linear terms. This then means that I would need to replace the 57 higher-order terms with new auxiliary linear variables.
As of yet, I haven't found any closed-form/direct methods of translating the fractional problem to a more usable form. However, I seem to be having some success with the iterative method described by Ajagekar and You in section 7 of their paper: https://doi.org/10.1016/j.compchemeng.2019.106630 Their method is more or less to iteratively solve the (N-lambda*D) problem, while adaptively finding and changing the value of lambda, until some error falls below a certain value.
I was hoping not to have to use an iterative method, but so far this method seems to be a valid way of rewriting the fractional objective and, after several iterations, finding the same optimal solution as is indicated by the original fractional expression.
Thanks again for your help! Since these types of fractional objectives appear to be somewhat common, perhaps D-Wave can look into implementing some type of solver that supports these problems in the future. It could be a handy tool to have in the quantum applications toolbox :)
Regards,
Kevin
Hello,
Thank you for sharing your progress!
I will definitely pass along your suggestions to the appropriate teams for consideration.
We always appreciate feedback.
It is important to be informed in our decisions of how to move forward with development, especially in what is useful to our users!
Also, thank you for sharing your references!
We and other users will really appreciate this in the future.
An iterative approach can be quite useful in some situations.
Have you taken a look at the dwave-hybrid libraries?
https://docs.ocean.dwavesys.com/en/latest/docs_hybrid/intro/overview.html
They could serve as a useful framework to automate some of this iteration.
Best luck moving forward!
We will pass any information that might be helpful in your research should we come across it.
Best regards,
Dave.
Hi there
I am relatively new to DWave. I work on an optimisation problem which I found it similar, but simpler than what discussed here, so I hope you can help me please.
My objective function to minimise is in the form f(x)=(AX+b)/(CX+d) with constant matrices A, C and constant values b, d and X being a matrix of 100 binary values. No extra constrain, no higher order X. I converted this from LFP(X) to LP(Y) based on the article suggested above. Now I have a g(Y)=EY+f. However I am not sure how to feed the decimal values of Y to the qbit biases. Bitwise operations may lead to many hundreds of qbits! Also I'm not sure if any constrain shall be applied at Y level and how to formulate it to MBQ. Any ideas?
Thanks
Amir
Hi Amir,
I'll do my best to provide you with some ideas, but I am by no means an expert in mathematics or LFP/LP methods. I'm just a student that has had to look into these things out of necessity for my thesis. Here are my thoughts pertaining to your question though:
The method that you have implementend essentially works by transforming the problem variables X into variables Y, which then allows the problem to be written as an LP. However, in our case, we know that X have to be binary variables, whereas I'm not sure what the resulting variables Y will look like. Probably, if the solution to every original variable X is limited to {0,1}, then the solution to every transformed variable Y will be limited to some set {0, a}, and if I understand correctly, you find a to be some decimal value.
As you have found out, it is not obvious how to implement this for use with the quantum annealer. In my opinion, it could very well be the case that the method proposed in that article is not compatible with the binary type of problem that we are dealing with. Again, I'm unfortunately not an expert. However, here is an idea:
In the case that you have found every Y to be in some set {0,a}, and you have some corresponding decimal factor E that Y is multiplied with. Thus, you would have this LP
g = EY + f
However, if you know that Y will be in {0,a}, would it then be valid to transform Y back into a purely binary variable (Y_b in {0,1}) by taking:
g = aE * Y_b + f
This would mean that your qubit biases for the QUBO would become aE when you input your problem on the quantum annealer. I'm not sure if this will work, it's just an idea. (small addendum: Since the paper gives this definition: Y = x/(dx+beta), this only works when your value of beta is non-zero, since otherwise one of the 'valid' choices of Y would be 0/0, which makes everything so much more problematic)
On a completely different note:
The second paper that I linked in my post above (https://doi.org/10.4236/ojop.2017.61001) has ( I think ) a much more user-friendly approach. This is under the condition that you can guess a valid solution to your problem beforehand. If I understand their method correctly, then all you need to do is this:
F' = F(X') = (AX' + b) / (CX' + d)
G = (A - F'C)X
Finally: I have managed to consistently find the correct optimum solution using the iterative method by Ajagekar, which I have also linked in one of my above posts. However, for your relatively 'simple' problem, I think at least one of the closed-form solution methods might work. Otherwise i recommend to look into the iterative method (which was pretty easy to implement actually!)
I hope these ideas may help you solve your problem! If you make any progress, please keep us up to date :)
Regards,
Kevin
Dear Kevin
Many thanks for your comprehensive reply, and sorry I was not available to reply to you any sooner.
I am also not a mathematician, nor an active LP/LFP programmer. I am a computer scientist new to quantum computing. This problem is a narrowed-down version of an AI problem, which is already solved using an iterative method. My intention is to try to see if QC can do it with any better efficiency.
Regarding your suggestion of g = aE * Y_b + f for when Y=a.Y_b, the point is that 'a' depends on X since Y=X/(CX+d) so that a=1/(CX+d) - a function of X. For knowing 'a' I must have already solved the problem.
I read the second paper you referred, and applied the formulation you suggested but still no success. I did not try it on DWave but on a sample problem with known answers, it did not give me anywhere near the solution yet. On the other hand, following the paper formulation was not easy for me and I just guess that the LFP to LP mapping might not be as simple as what you concluded. I have a God-feeling that linear biases are not enough and there must be some quadratic terms in the final BQM.
My data contains 100 points of binary X together with A, B, c and d values. There are some extra columns that I used to work out the LFP-LP formulation according to the first paper. The Y values are either 0 or a decimal value depending on all Xs.
Many thanks again.
Hi Amir,
Having taken a quick look at your data, I understand indeed why my initial suggestion wouldn't work, since it indeed would rely on the problem already being solved.. Unfortunately I cannot really help you any further with your predicament!
I do have a final suggestion: you should try getting in touch with the authors of these papers (the email addresses are often given in the paper!), as well as trying to contact any local expert in the LP/LFP field. In my experience people are happy to help if you can give them a concise explanation of your problem.
If I understand correctly, the main problem at this point is that your transformed LP problem is no longer written in terms of binary variables, making it difficult (impossible??) to implement with the quantum computer. For the method in the initial paper this is not really a problem as the unknown variables Y can just be numerically solved (and Y is not restricted to binary values), and then back-substituted to find what the solution X will be. This is not really doable in your case, since it is necessary for the problem to be written in terms of binary variables. What you are after therefore, is a method to transform your binary LFP to an equivalent LP problem which is also written in terms of binary variables.
A final comment based on your statement:
> I have a God-feeling that linear biases are not enough and there must be some quadratic terms in the final BQM.
In my experience, binary LP problems are quite trivial to solve. Since, the minimum solution will just be:
Adding in the quadratic variables is what makes the problem non-trivial, and worthwhile for implementation on the quantum computer.
Good luck in your efforts, and please keep the forum updated on your progress, for the benefit of other users in the future. :)
Regards,
Kevin
Many thanks Kevin.
You are quite right that the main problem can be expressed as "converting a binary LFP to a binary LP". Imagine that such a "binary LP" is found in the form g(Y)=EY+f without any constrain. As you said this can be simply solved by setting y_i=0 for positive elements of E and 1 for negative ones. However, this solution of Y may not be converted back to a binary X as we would needed for the original LFP. Therefore it seems to me that constrains play an important role, so that we need to have constrains for the LP problem. As I understand from BQM, the constrains can be "stiched" to some quadratic terms. This is why I thought some quadratic terms might be needed.
Not directly related to the above, but I just found some literature dealing with binary LFP, as they called it Fractional 0-1 Programs, such as
http://d-scholarship.pitt.edu/37617/
Thanks again, will update here if any progress!
Amir.
Hello again
It seems I have found a solution for this. The key is to formulate a constraint which limits the Y_b solutions to those values that can be converted back to binary X when X=dY/(1-CY). To do this we would need to find 'a' and 'Y_b' together in parallel in a single problem. Since 'a' is decimal, we need to consider a number of bits representing it. Therefore the problem will be to apply the constraint to a set of binary values consisting of some bits for Y_b and some extra bits for 'a'. The formulation of this constraint then includes both linear and quadratic terms!
I tried this on DWave on a smal problem conisting of 10 qbits for Y_b and 10 qbits for 'a' and it worked.
All the best
Amir.
Please sign in to leave a comment.