Linear and Integer Programming: Problem Types & Constraints

Variable Logical Constraints

Variable Logical Constraints: (Use ‘if ≤ then’ for these questions, and/or usually represented with +)

If bring eggs and chicken then can’t bring bread: X1 + X2 + X3 ≤ 2
If bring eggs, then must bring chicken and/or bread: X1 ≤ X2 + X3
If bring eggs, then must bring both chicken and bread: X1 ≤ X2 and X1 ≤ X3
If bring eggs, then must bring chicken or bread but not both: X1 ≤ X2 + X3 and X1 + X2 + X3 ≤ 2
If don’t bring eggs then must bring chicken and/or bread: 1 ≤ X1 + X2 + X3

(Deciding which product to bring constrained by weight, volume, etc.)

Vars: Xi = 1 if we bring item, = 0 if not
Obj function: Max: value(Xi) + value(Xi)…
Constraints: Weight Constraint: Weight(Xi) + Weight(X2) ≤ Weight constraint in question. Xi ∈ {0,1}

(Trying to minimize total number of buildings needed in towns, arcs represent distances, Node represents town)

Let Xi = 1 if we open station in town i, = 0 if not
MIN (XA + XB + XC…)
Cover Constraints: Figure out for each node which station could provide coverage (use arcs to see distances). Ex: if max distance is 12 then for town A find distances that are less than 12 and write in constraint: Node A: XA + XB ≥ 1 (Do for each node).

Deciding whether to open/close location before we can use their supply.

Let Xij represent units shipped from i = (A, B) to j (1, 2, 3). Let Y = 1 if we open factory and 0 if not
MAX sum of arc numbers + fixed cost of demand nodes
Supply constraints: XA1 + XA2 + XA3 ≤ supply of node A ⋅ (YA). Demand Constraints: XA1 + XB1 = Demand of node 1 (do for all nodes)

Arcs are distances, trying to ship 1 thing (supply and demand of 1) through shortest path to last node.

Let Xij = 1 if your route travels along ij, 0 if otherwise.
MIN sum of each arc you take
Demand constraint: XAB + XAC + XAD = 1, Supply constraint: CG + EG + FG = 1, middle constraints: what goes in must come out.

Send as much flow from S to T while obeying capacities on arcs.

Let Xij represent the flow sent from i to j
MAX XTS
XSA + XSB + XSC = XTS (do the previous constraint for every node, basically what comes out of a node must go all the way through back to S). Capacity constraints: XSA ≤ 6, XSB ≤ 1 (using numbers from arcs, do for all arcs).

Arcs have costs nodes going to one another with supply nodes on left and demand nodes on right.

Variables are XA1, XA2, XA3, XB1, XB2… Where letter is demand node and number is supply node
MIN 5XA1 + 6XA2.. + 10XB1 (do for all arcs)
Supply constraint: XA1 + XA2 + XA3 ≤ 200 (200 is the supply found on node A, need constraint for all supply nodes, use = instead if you can’t fill all demand). Demand constraint: XA1 + XB1 = 100 (100 is demand on node 1, Need constraint for all demand nodes, use = if all demand can be filled if not, use ≤)

Same as transportation problem except: need constraint for middle nodes (constraint is: what goes in must come out).

Trying to minimize cost while meeting customer demand in terms of a product.

Pi represent # of product produced in month i (1, 2, 3…), Oi represents # of product produced in overtime per month i (1, 2, 3, 4), Si represents # of laptops in inventory at end of each month, i (1, 2, 3, 4).
MIN 400(P1 + P2 + P3 + P4) + 500 (O1 + O2 + O3 + O4) + 20(S1 + S2 + S3 + S4) (the 400, 500 and 20 are the costs associated with producing, holding and producing in OT)
Capacity Constraints: P1 ≤ 90, P2 ≤ 90… O1 ≤ 20 O2 ≤ 90… Inventory Balance constraint: Apr: P1 + O1 = 80 + S1, May P2 + O1 + S1 = 100 + S2, June P3 + O3 + S2 = 120 + S3. (Numbers are from table given in question).

Employees, part and full time, trying to minimize labor while meeting reqs.

Let Pi represent # part times who work shift i, let Fi represent # of full timers that start at shift i.
MIN (15)(4)(P1 + P2 + P3) + 20(*)(F1 + F2) (numbers are wages and shift time)
Shift cover constraint: 8am-noon: P1 + F1 ≥ 7, noon-4pm P2 + F2 + F1 ≥ 12 (notice that the full timers are usually in two constraints cuz their shifts are longer).