# Stunningly Useful Suggestion

Andrew Makhorin, the GPLK maintainer, suggested that I look into "column generation" as a technique to make my LP more tractable. The basic idea is to start with a reduced set of solution variables, then iteratively solve the reduced problem, analyze the solution, and identify new variables (columns) which may improve the minimization.

This ought to be a good fit for my push-or-fold-lowball problem, as I expect that most of the small blind's strategies will go unused. (I expect most hands to have pure strategies, but I don't know it for sure.) I just have to come up with some way of identifying which variable (or variables) to add that have the most negative "reduced cost".

For example, we can start with only "push and stand pat" as an option. Solving this as a LP produces a column of duals "y" to the master problem. (Each dual corresponds to one of the constraints.) Then we have to identify whether there's a column Aj we can add such that yTAj is positive (?)--- i.e., adding it will let us reduce the objective. This is the "pricing problem".

The most common example given for this technique is the "cutting stock problem", where the pricing problem is just the knapsack problem. For push-or-fold lowball it doesn't seem as straightforward. We need to identify a hand that SB is playing "badly" against BB's response and come up with the best possible replacement strategy. (The duals must encode BB's strategy in a way I don't quite grasp.)

If we can determine what BB's best choices are, then we can calculate, for each hand, what the best draws are based on BB's current hand ranges. This reduces the problem from searching through 256 options to 4*4 = 16. It's not clear how to pick which hand to look at though--- I don't know how feasible it is to calculate which hand's losing us the most money. If we can do so then it seems like a good heuristic is to first add in "fold" then add "best draw", possibly adding alternate "best draws" if necessary.
Tags:
• Post a new comment

#### Error

default userpic