Bsrgvty

I’m interested in the idea behind this in general, so I thought this would be the best place to post, though I have a practical and semi-urgent need of allocating the points on my credit card towards purchases.

Each purchase I make can be paid for in points. However, it goes by purchase, not by my total bill. Therefore, I can wind up with points left, but too few to be able to put them towards a purchase. Further, points don’t have the same value for each purchase. One purchase may regard a point as a cent, while another may regard a point as 0.9 cents.

My goal is to have as little left on my bill after I use points. Certainly I can do this by brute force and try out every combination of purchases to see which results in the lowest remaining bill, but that lacks elegance and seems like it would be quite slow (dealing with factorials).

My Questions

1. What slicker techniques are there for solving this minimization problem?




2. Is there existing software that will solve this problem?

Thanks!

EDIT

Responding to some comments...

CMichael (1): I get to make the decision at the end of the month when I am paying my bill. Instead of paying the entire bill, I can use points to pay off some purchases and then pay off the remaining bill. I want the remaining bill to be minimized.

CMichael (2): If I want to use points towards a purchase, I have to cover all of that purchase with points. If my purchases is $100 or 10,000 points, I can either spend the $100 or the 10,000 points, but $50 and 5000 points would not be allowed.

With the OP's clarifications I would say this is a straight-forward variant of the knapsack problem where you want to pack as many saved dollars into your budget of points. Find below the simple formalization where the index $i$ spans across all items on the current bill:

Capacity of the knapsack: $C$ = Available points

Item weight: $w_i$ = number of points necessary for item

Value of item: $v_i$ = dollar value of an item (note that if purchased with points you get to keep the money)

Decision variables: $y_i in 0,1$ = item is payed with points

Objective function: $maxlimits_y_i sumlimits_i left(v_i y_iright)$

subject to: $sumlimits_i left(y_i w_iright) leq C$

The little trick that may be confusing here is the following: The weight is not directly given but obtains from the price of item multiplied with the item's point conversion rate $gamma_i$ ($w_i = v_i gamma_i$).

A quick google search yielded the following web site with a simple branch and bound solver: https://jacopo.cc/BB/ Depending on the number of items on your bill you could also use Microsoft Excel - the built-in solver supports something like 200 decision variables. If you are dealing with larger problems you may want to look over here where somebody created a dynamic programming solution in VBA. Probably this could be integrated in your workflow?

If you want an ok heuristic solution you can try out greedy by value density - that is sort your items by descending $v_i / w_i$ and pick sequentially the items with the highest value density which fit into your point budget. Of course such a heuristic will not guarantee an optimal solution.

This seems like some sort of knapsack problem: Suppose you have a set of purchases and a certain amount of points. Each purchase can be "paid" by points as a whole, no partial usage of points for each purchase is viable.

Let's declare some sets and parameters: let $P=1,ldots,n$ be the set of purchases which each get a number to distinguish them. For each purchase $pin P$ you have an amount of points $w_p$ that is needed to cover the purchase with points completely. You also have a certain amount of points $M$ which you can use.
As you want to maximize the amount of money covered by using points, you define the value $v_p$ for each purchase which corresponds to the price of the purchase (as you have stated, the number of points used can differ from the actual amount of money you cover with the points).

Now you can use a standard knapsack solver to compute the solution with $w_p$ as weights, $v_p$ as values and $M$ as the maximum weight capacity.

The while the Knapsack problem is NP-hard, it is some of the more benevolent optimization problems that have a pseudo-polynomial time algorithm that uses dynamic programming. The solving time depends on the number of items and the maximum weight capacity $M$ (so you have $O(nM)$). There exist many implementations which you can find for example here. If your problem is reasonable small (which I can imagine as you wont make thousands of purchases per month) there shouldn't be a problem to solve your problem.

However, this only covers the decision for one month. If you want to decide at the end of a month how much points you should use or whether it is beneficial to save your points and use them later in the year, this problem is much harder and your problem changes into a online version. Here, you also have to guess the purchases you will do in the future. Maybe you have recurring stuff that you pay every month, but very likely there is an amount of purchases you won't know in advance.

That sounds like you could formulate it as MIP. You have a fixed set of planned purchases, right? Each of them ($p$) will yield a constraint of the form $x_p + c_p cdot y_p = t_p$, where $x_p$ is the amount of money you will spend on that purchase, $y_p$ the amount of points with the conversion rate (per purchase) and $t$ the total price. $x ge 0$ would be continuous, and $y ge 0$ integer.
Then you would need to limit the points available: $sumlimits_p y_p le Y$ and minimize the total amount of money spent.

Does that make sense?

EDIT: The above is a description of a MIP model formulation. To get the answer, you will need some solver software.

EDIT2: According to the comments, a purchase can not be made with a combination of money and points. In that case, the constraints need to change, e.g., by adding a $operatornameSOS1(x_p,y_p)$ for each purchase. But the problem can also be simplified by using binary variables for $x$ and $y$, with $x_p + y_p = 1$. In that case, you would need to limit the number of points used by $sumlimits_p d_pcdot y_p le Y$, where $d_p$ gives the number of points needed for $p$. The function to minimize is then $sumlimits_p c_p cdot x_p$ with $c_p$ the price of the purchase.