0
$\begingroup$

I'm using a JavaScript library ( jsLPSolver ) to solve optimization problems to do with building a deck of magic the gathering cards.

Currently my problem are linear, as the library can only solve linear problems. However, one of the powerful things about some Magic the Gathering decks is synergy between the cards.

For instance, one card may get more or less powerful depending on the other cards in the deck.

As an example, there is a card that might read "Return two Instant cards from the graveyard to your hand". An 'Instant' card is a type of card, and 'Graveyard' and 'Hand' are locations the game recognises. I can define these as variables in a way.

If you have no instant cards in your deck, the card is useless. If you have 1 it has marginal use, and so on. This probably continues linearly. (There's also the consideration that you might need to have ways to put the 'Instant' cards from another location into the 'Graveyard', but I think I can handle that separately be defining a relationship between another set of variables.)

From what little research I've done, this makes it a non-linear optimization problem, but I'm struggling to find resources on this because I don't know what kind of non-linear problem it is.

A non-magic the gathering example would be if you wanted to optimise a shopping list, and you got discounts on Item A, for buying Item B ( "Calculator X is 50% cheaper if you by the Amazo-Protractor!” ).

What is this sort of interrelated optimization problem called?

$\endgroup$
1
  • 1
    $\begingroup$ Look into mixed integer optimization, that is the typical way of formulating "if .. then .." logic in an optimization problem. $\endgroup$ – LinAlg Jun 27 '20 at 19:00
2
$\begingroup$

If the constraints are linear and you have products of up to two variables at a time in the objective function, you have a quadratic programming problem. Sometimes you can reformulate nonlinear problems to linear by introducing additional variables and constraints. If you describe your problem in more detail, maybe you will get more specific help.


Update:

Based on your GitHub code, I think the following is your linear optimization model. For each card $c \in C$, let binary decision variable $x_c$ indicate whether card $c$ is selected. Let $v_c$ be some measure of how valuable card $c$ is on its own. Let $k$ be the number of cards you are allowed to select. For each attribute $i\in I$, let $b_i$ be the minimum required amount of that attribute and let $a_{i,c}$ be the amount of attribute $i$ that card $c$ contributes. For each tactic $t\in T$, let $C_t \subseteq C$ be the set of cards that correspond to that tactic. The problem is to maximize $\sum_{c \in C} v_c x_c$ subject to linear constraints: \begin{align} \sum_{c \in C} x_c &= k \tag1 \\ \sum_{c \in C} a_{i,c} x_c &\ge b_i &&\text{for $i\in I$} \tag2 \\ \sum_{c \in C_t} x_c &\le 1 &&\text{for $t\in T$} \tag3 \\ \end{align}

For your sample data, it looks like $|C|=200$, $k=60$, $|I|=2$, and $b_i=10$.

If you want to account for synergy from pairs $\{c,d\}$ (with $c<d$) of cards, where you receive an additional reward of $w_{c,d}$ if both cards are selected, you can introduce a quadratic expression in the objective function so that the new objective is to maximize $$\sum_{c \in C} v_c x_c + \sum_{c<d} w_{c,d} x_c x_d.$$ This change modifies the problem type from integer linear programming to integer quadratic programming. But you can linearize the quadratic objective by introducing another decision variable $y_{c,d}$ to represent $x_c x_d$, replacing the objective function with $$\sum_{c \in C} v_c x_c + \sum_{c<d} w_{c,d} y_{c,d},$$ and including additional linear constraints \begin{align} y_{c,d} &\le x_c \tag4 \\ y_{c,d} &\le x_d \tag5 \end{align} that enforce the logical implication $y_{c,d} = 1 \implies (x_c = 1 \land x_d =1)$.

$\endgroup$
7
  • $\begingroup$ When you phrase it like that (we have products of variables), it seems obvious these are quadratic optimization problems. I'm not sure what additional information you would like but I can add more information to the question. $\endgroup$ – Pureferret Jun 27 '20 at 17:03
  • $\begingroup$ I think it would be useful to see what linear problems you are solving now. What are the decision variables, objective, and constraints? $\endgroup$ – RobPratt Jun 27 '20 at 17:41
  • $\begingroup$ Here is the GitHub link to my code, it might give you an idea. I think the decision variables would be my ratings if cards (this card is good for X thing, like 'Ramp') and the objective is to maximise all decision variables, while keeping decks size === to the maximum deck size. $\endgroup$ – Pureferret Jun 27 '20 at 19:06
  • $\begingroup$ @Pureferret, I updated my answer with a guess at your formulation. $\endgroup$ – RobPratt Jun 27 '20 at 20:04
  • 1
    $\begingroup$ The original formulation is integer linear, but I just added an extension to integer quadratic, as well as a linearization to get you back to integer linear. $\endgroup$ – RobPratt Jun 27 '20 at 23:17

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.