12
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Is your goal to spend as many points as possible, or do you want to maximize the value/enjoyment that you get out of the products that you buy? $\endgroup$ – Kevin Dalmeijer Sep 19 at 2:23
  • 1
    $\begingroup$ @CMichael I don't follow what online/offline has to do with anything, but it's a decision I make at the end of the month when I pay my bill. The purchases are set: on the 7th, I bought groceries for \$67.44, 6,744 points; on the 8th, I had car maintanence for \$275.44, 27,133 points, etc. This would be the latter case. $\endgroup$ – Dave Sep 19 at 10:19
  • 2
    $\begingroup$ The online vs. offline comment by @CMichael is not about whether the purchase id made in an online store or in a brick-and-mortar one, but when the decision to use the points is made: Is it at the time of the purchase (online - you do not know your purchased of the rest of the month) or at the end of a month when all purchases have been made (offline). $\endgroup$ – JakobS Sep 19 at 11:13
  • 1
    $\begingroup$ Do points expire at the end of the month? How many purchases do you typically have? $\endgroup$ – Acccumulation Sep 19 at 16:33
  • 1
    $\begingroup$ Dave this would then be the transition to an online version of the problem. $\endgroup$ – CMichael Sep 19 at 23:51
9
$\begingroup$

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: $\max\limits_{y_i} \sum\limits_i \left(v_i y_i\right)$

subject to: $\sum\limits_i \left(y_i w_i\right) \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.

$\endgroup$
  • 1
    $\begingroup$ I like R and found a package that solves the knapsack problem: rdocumentation.org/packages/adagio/versions/0.7.1/topics/…. It looks like I put the point values in the first argument, the money values (in cents) in the second argument, and my total number of points as the last argument. $\endgroup$ – Dave Sep 19 at 22:11
  • $\begingroup$ Exactly - keep us updated how it works out. $\endgroup$ – CMichael Sep 19 at 23:22
  • 2
    $\begingroup$ Knapsack managed to use ALL of my points and save me over a hundred bucks! $\endgroup$ – Dave Sep 20 at 16:38
  • 1
    $\begingroup$ That's terrific - I really liked this problem. As an instructor it is so nice to learn about application which do not encompass packing per se. If you are content feel free to accept one of the helpful answers. $\endgroup$ – CMichael Sep 20 at 17:00
8
$\begingroup$

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 $p\in 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.

$\endgroup$
  • 4
    $\begingroup$ Perhaps it would be valuable to mention that the knapsack problem can be solved in $O(nM)$ time using dynamic programming (which can even easily be implemented in Excel). $\endgroup$ – Rolf van Lieshout Sep 19 at 13:23
7
$\begingroup$

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: $\sum\limits_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 $\operatorname{SOS1}(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 $\sum\limits_p d_p\cdot y_p \le Y$, where $d_p$ gives the number of points needed for $p$. The function to minimize is then $\sum\limits_p c_p \cdot x_p$ with $c_p$ the price of the purchase.

$\endgroup$
  • $\begingroup$ I think this is getting at what I want to do. What, though, would be the method for finding the minimum? $\endgroup$ – Dave Sep 19 at 9:43
  • 1
    $\begingroup$ @Dave From the original description it is unclear if you have to pay a purchase completely with points if you go for points or if a partial payment (points and cash) is possible. The latter case is modelled here, the other case would have $y_p \in \{0,1\}$ and an adjustment to not be able to spend cash. I think this is what you are looking for because otherwise I cannot image that you have leftover points which you could just use for partial payments? $\endgroup$ – CMichael Sep 19 at 10:19
  • 1
    $\begingroup$ @CMichael If I want to use points towards a purchase, I have to cover the entire purchase with points. A combination of points and cash is fine for the whole bill, but each purchase is either done with points or with cash, never a mix of the two. $\endgroup$ – Dave Sep 19 at 10:26
  • $\begingroup$ @Dave, the method of solving was implicit in my answer: Formulate the model described and hand it to a MIP solver, as implemented in software. $\endgroup$ – Robert Schwarz Sep 19 at 11:52
  • 1
    $\begingroup$ Robert is referring to dedicated solvers for mixed-integer problems - e.g., Gurobi, CPLEX, Excel Solver. These can be provided with the problem formulation and the relevant data and it can subsequently be solved to optimality. Such solvers tackle integer problems by virtue of a combination of LP solving, Branch and Bound, Heuristics etc. $\endgroup$ – CMichael Sep 19 at 12:24

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.