Skip to content
Tutorials Center
My learning

Topics

Lesson 20 of 38 · Integer Programming

Binary Variables and Logic

Model yes/no decisions with 0-1 variables: knapsack, if-then and either-or rules, fixed charges and big-M constraints, all solved with SciPy milp.

A binary variable takes the value 0 or 1. It is the workhorse of integer programming because it can represent a decision: build or do not build, select or skip, open or close. With a few standard tricks, binary variables also let you express logic that plain linear constraints cannot, such as "if A then B", "at most two of these", or "pay a fixed cost whenever you produce anything".

This lesson collects those tricks, called modeling patterns. You will use them in almost every integer model later in the course.

The knapsack problem

You have a bag that holds a limited weight and a list of items, each with a value and a weight. Pick items to maximize value. Let x_i = 1 if item i is taken. The model is:

TEXT
maximize    sum v_i x_i
subject to  sum w_i x_i <= W,   x_i in {0, 1}
Python 0-1 knapsack: milp versus dynamic programming

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Both methods agree. Dynamic programming is great for a single constraint with small integers, but the MILP version keeps working when you add more constraints (volume, budget, conflicts), which is why it is the more flexible tool.

Logical constraints

Suppose x_A, x_B, x_C are binary "select" variables. These constraints are the standard translations:

Statement Constraint
At most one of A, B, C x_A + x_B + x_C <= 1
Exactly one x_A + x_B + x_C = 1
At least one x_A + x_B + x_C >= 1
If A then B (A requires B) x_A <= x_B
A and B cannot both be chosen x_A + x_B <= 1
A if and only if B x_A = x_B
At most k of n sum x_i <= k

Reading x_A <= x_B: if x_A = 1, then x_B must be 1; if x_A = 0, x_B can be anything. That is exactly "A implies B".

Python Project selection with dependencies

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Here "mobile" and "ml" both need the shared "api" project, so selecting either forces the api cost; the model weighs these hidden dependencies automatically.

Fixed charges and big-M

Many costs have a fixed part: starting a production run costs a setup fee regardless of quantity. Let x >= 0 be the quantity and y binary with y = 1 if we produce anything. Then:

TEXT
cost = c·x + F·y        x <= M·y

If y = 0, the constraint forces x = 0; if y = 1, x can go up to M. The constant M ("big-M") must be at least as large as any value x could really take. Choose it as small as validly possible: huge values of M make the LP relaxation weak, because y can then be a tiny fraction like 0.001 and still allow big x. The next lessons show this matters for solve time.

Python Fixed-charge production

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The solver spends all 100 hours on product 2, which earns 7 per hour against 4.5 and 3 for the others, so it pays only one setup (net profit 640).

Either-or constraints

To say "constraint 1 or constraint 2 must hold", add a binary z and a big-M that relaxes one of them:

TEXT
g1(x) <= b1 + M1 * z
g2(x) <= b2 + M2 * (1 - z)

If z = 0 the first constraint is enforced and the second is relaxed; if z = 1 it is the other way around. This is how scheduling models say "job A before job B, or B before A" (see Scheduling with MILP).

Sets and counts

  • Set covering: every demand must be covered by at least one chosen option: sum_{j covers i} x_j >= 1 for each i.
  • Set packing: each resource used at most once: sum <= 1.
  • Cardinality: open exactly k sites: sum y_j = k.
  • Minimum order: if produced, at least L units: L·y <= x <= M·y.

When a model gets slow, first check every big-M. A tighter valid constant is the cheapest speed-up you will ever find.

Check your understanding

Quick check · 4 questions

of 4 answered You scored / 4 · perfect!

  1. 1. Which constraint says: if project A is selected then project B must also be selected?

    When x_A = 1 the inequality forces x_B = 1; when x_A = 0 it imposes nothing.
  2. 2. In the fixed-charge model x <= M*y, what happens when y = 0?

    With y = 0 the right side is 0, so the quantity x is forced to 0 and no fixed cost is paid.
  3. 3. Why should big-M be as small as validly possible?

    A huge M lets the relaxed y be nearly zero while x is large, so the relaxation bound is poor and branch and bound needs many nodes.
  4. 4. How do you say 'choose exactly 3 of 8 sites'?

    An equality on the sum of binaries fixes the count exactly.

Summary

  • Binary variables model decisions; the knapsack problem is the basic example.
  • Logic becomes linear constraints: <= for implication, sums for at-most/at-least/exactly.
  • Fixed charges use x <= M·y with the smallest valid M.
  • Either-or conditions use a binary switch plus big-M on each side.
  • Set covering, packing and cardinality constraints appear in nearly every applied model.

Next: Branch and Bound