1
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ I can’t quite see the linear programming problem. And I can’t quite see what you want to optimise. $\endgroup$
    – gnasher729
    Dec 27, 2022 at 13:43
  • $\begingroup$ Want to optimize tickets paid out (whether that be min/max) - which would be dependent on the "guesses" that people made on each coin flip. If there are 10 "wagers" and each person guessed that flip 3 would be heads - then for me obviously the best outcome would be tails for flip 3. But how do I actually solve for this result is my question $\endgroup$
    – B.D.
    Dec 27, 2022 at 15:10

1 Answer 1

0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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