9.1 Modelling with integer variables

A binary variable \(y \in \{0, 1\}\) expresses a decision, and linear constraints on binaries express logic.

Fixed charges. A product costs \(F\) to set up and \(c\) per unit, with at most \(M\) units: cost \(Fy + cx\) with \(0 \leq x \leq My\), so that \(x > 0\) forces \(y = 1\).
Either–or constraints. To require \(g_1(x) \leq 0\) or \(g_2(x) \leq 0\), impose \(g_1(x) \leq My\) and \(g_2(x) \leq M(1 - y)\) with \(M\) an upper bound on both.
Logical conditions. “At most \(k\) of these projects” is \(\sum y_j \leq k\); “project \(2\) only if project \(1\)” is \(y_2 \leq y_1\).
Set covering. Choose sites \(y_j\) to cover every customer \(i\) by at least one site: \(\sum _{j \in S_i}y_j \geq 1\).

The knapsack problem, maximise \(\sum v_jy_j\) subject to \(\sum w_jy_j \leq W\), \(y \in \{0, 1\}^n\), is the simplest IP and already NP-hard. The value of \(M\) matters in practice: too small cuts off solutions, too large weakens the LP relaxation described next.

[next] [front] [up]

Questions on this section

Stuck on something here? Ask below and it stays attached to this topic.