Boolean Integer Linear Optimization/Programming

Question

Trying to solve an ILP optimization problem with a number of potential boolean variables and then express constraints on these variables based on those boolean results.

Let's say I am doing 5 coin flips and allowing people to choose heads or tails for each coin flip. They are able to choose one or more specific flips and whether or not they think it would be heads, and then if they are correct they get tickets back depending on how many flips they chose. Eg: You pick heads for flip 3 and tails for flip 5 and if both are correct you get 3 tickets. Another person picks heads for flip 1, heads for flip 2 and tails for flip 3 and if they are correct they get 10 tickets.

I want to be able to express something like:

y=3 if x_3=1 (heads) & x_5=0 (tails)
y=10 if x_1=1 (heads) & x_2=1 (heads) and x_3=1 (heads)

So on and so forth

And with a large number of trials - how would I be able to determine what the best/worst case scenario is in terms of having to pay out the most/least tickets to optimize what the ideal results would be?

Thanks for any help

Answer 1

Yes, it is certainly do-able. Use a different $y$ for each rule, e.g., $y_1=1$ if the first rule triggers or $y_1=0$ otherwise, $y_2=1$ if the second rule triggers or $y_2=10$ otherwise, etc. Then your goal is to minimize or maximize $3y_1+10y_2+\dots+y_n$.

It is easy to express each rule (e.g., $y_1=1$ if $x_3=1$ and $x_5=0$, or $y_1=0$ otherwise) using the methods in Express boolean logic operations in zero-one integer linear programming (ILP). In particular, $y_i$ is a logical-AND of some of the $x_j$'s, so you can use the rule for logical-AND from there.