Responses to Week 7 Poll Questions

MGMT 306

• Can every logical condition be modeled using linear constraints?

  This is a great question. In fact, yes every logical condition can be modeled using (possibly many) linear inequality constraints.

  Suppose we have any logical condition on binary variables \(A_1,A_2,A_3\). We can form a truth table and check where our logical condition holds. For example, the truth table might look like the following:

  \(A_1\)	\(A_2\)	\(A_3\)	Condition
  0	0	0	True
  0	0	1	False
  0	1	0	True
  0	1	1	False
  1	0	0	False
  1	0	1	True
  1	1	0	True
  1	1	1	True

  Each row corresponds to one “scenario” for the values of \(A_1,A_2,A_3\). A set of linear inequality constraints correctly models the logical condition if for every “true” scenario, all of the linear inequality constraints hold; and for every “false” scenario, at least one constraint is violated.

  We can do this by looking at every false scenario and writing a linear inequality constraint ruling out that single scenario. For example, to disallow \((A_1,A_2,A_3) = (0,0,1)\), we could use the following constraint \[\begin{aligned} (A_1-0) + (A_2-0) + (A_3 - 1) \leq 2 \end{aligned}\] The left-hand-side of this constraint counts how many of the values \(A_1,A_2,A_3\) match the corresponding entry of \((0,0,1)\). The constraint says that we are not allowed to match every entry of \((0,0,1)\).

  By including one such constraint for each of the three assignments we want to prevent (the “false” scenarios), we can model the logical condition. Unfortunately, for very complicated logical conditions, this might lead to “exponentially many” constraints.

  In contrast, for most of the logical conditions we will see in this course, we will be able to write them with just a few linear constraints.

• Can you go over how to write linear constraint representations of more complicated “If Then” statements?

  The slides go over all of the basic rules. The rules to remember are

  Logical condition	How to model	Notes
  A and B	\(A + B = 2\)
  A or B	\(A + B \geq 1\)
  A xor B	\(A + B = 1\)
  If A, then B	\(A \leq B\)
  If A and B, then C	\(A + B - 1 \leq C\)	You should also know how to do multiple ANDs in the IF clause
  If A, then B or C	\(A \leq B + C\)	You should also know how to do multiple ORs in the IF clause

  Additional things to know:

  • “Not \(A\)” is represented by the expression \(1-A\)
  • An “If, Then” condition with ORs in the IF clause, splits
  • An “If, Then” condition with ANDs in the THEN clause, splits

  I’ll do an example putting these rules together:

  If A or not B or C, then D or not E

  This logical condition has ORs in the IF clause, so it splits into three separate logical conditions

  If A, then D or not E

  If not B, then D or not E

  If C, then D or not E

  Each of these logical conditions is very similar to “If A, then B or C” which we remember can be modeled as \(A \leq B + C\). All we need to do is replace the relevant terms to get: \[\begin{aligned} A &\leq D + (1-E)\\ (1-B) &\leq D + (1-E)\\ C &\leq D + (1-E) \end{aligned}\]

  We can put these constraints into standard form and use all three of the linear inequalities to model the original logical condition.

• Why are IPs more difficult than LPs?

  This is a very good question and it could seem counterintuitive at first.

  In an Integer Program, there are only a finite number of feasible solutions, while in a Linear Program the feasible region usually contains infinitely many points. So it might seem like IPs should be easier. For example, in principle, we could just check every possible solution.

  However, this is not the way that Solver or other optimization algorithms actually work.

  For Linear Programs, the feasible region is a continuous shape (a polygon in 2D) and we know that the optimal solution lies at one of the vertices (corners) of this region. The Simplex algorithm takes advantage of this property and moves from vertex to vertex, improving the objective function, until it finds the best one.

  For Integer Linear Programs, this structure disappears. Now, the feasible region is a collection of points with possibly very little structure. Because of this, the Solver must explore many different possibilities to determine which integer solution is best.

• Why do we care about the LP relaxation and which constraints do you drop to get the LP relaxation?

  Linear Programs are generally much easier to solve than Integer Linear Programs. Because of this, even if a problem naturally should include Integer or Binary constraints, we might drop them and consider the LP relaxation instead.

  A common pattern is: We model a problem and choose to use an IP in order to get the most accurate model of our problem. We attempt to solve the problem and see that Solver crashes / is unable to solve the problem after a few hours. We relax the IP model to its LP relaxation and solve that instead. Here, we would be trading the fidelity (accuracy) of the model with the ability to actually solve it.

  Recall that an Integer Linear Program by definition is a model where the objective is a linear function, all of the constraints are linear except for some constraints of the form:

  \(x_1\) is binary

  \(x_2\) is integer

  To get the LP relaxation, we would replace “\(x_1\) is binary” with the constraint \(0\leq x_1\leq 1\) and simply delete the “\(x_2\) is integer” constraint. We would leave the objective function and all linear constraints alone.

  As an example, the LP relaxation of the Franklin Clothing Company IP is:

  Variables \[\begin{aligned} & D &&\text{number of dresses to produce/week}\\ & S &&\text{number of shorts to produce/week}\\ & P &&\text{number of pants to produce/week}\\ & R_D &&\text{whether to rent dress machinery}\\ & R_S &&\text{whether to rent shorts machinery}\\ & R_P &&\text{whether to rent pants machinery} \end{aligned}\]

  Model \[\begin{aligned} \max\qquad &15 D + 8 S + 14 P – 200 R_D – 150 R_S – 100 R_P&&\text{(total profit)}\\ \text{s.t.}\qquad&3 D + 2 S + 6 P \leq 150 &&\text{(labor)}\\ &4 D + 3 S + 4 P \leq 160 &&\text{(cloth)}\\ &D – 40 R_D \leq 0 &&\text{(linking dresses)}\\ &S – 53 R_S \leq 0 &&\text{(linking shorts)}\\ & P – 25 R_P \leq 0 &&\text{(linking pants)}\\ & S - 40 R_S \geq 0 &&\text{(logical 1)}\\ & D + 10 R_P \leq 50 && \text{(logical 2)}\\ &D,S,P\geq 0\\ &0\leq R_D,R_S,R_P \leq 1 \end{aligned}\]

  Note that here, the variables \(R_D,R_S,R_P\) are supposed to model binary decisions but our model allows them to take fractional values between 0 and 1. This is something that we will sometimes choose to do. This is why we insist that you put binary constraints in your constraints (not just the description of the variable) if that is something you want to enforce.

• What if we have multiple objectives?

  All of the standard models that we cover in this course only deal with a single objective at a time. In the final module of MGMT 306, we will cover scenarios where we have multiple objectives.

  Let’s imagine we have two objectives in some logistics/supply chain problem: minimize cost and minimize carbon emissions. There are a few ways to deal with this depending on how we prioritize the two objectives:

  • If we have a preference order on the objectives: 1) minimize cost, 2) minimize carbon emissions, then we can first minimize the cost, then among the optimal solutions of the first objective, minimize the carbon emissions. That is, we want to minimize carbon emissions as much as we can without sacrificing the cost (allowing the total costs to increase).
  • If we have a way to convert the ``units’’ of one objective to the other, then we could combine all objectives into a single objective. For example, if we value carbon emissions at $4/kg, then we could roll everything into a single objective function: \[\text{minimize} \quad(\text{cost in \$}) + \$4/\text{kg}(\text{carbon emissions in kg})\]
  • If we have no way of breaking ties, then we can talk about pareto efficient/pareto dominated feasible solutions. In this example, the shipping plans so that no other shipping plan achieves a smaller cost and a smaller carbon emission. I will explain this more in Module 6.

• What Solver options should we use for Integer Linear Programs?

  In MGMT 306, for Integer Linear Programs, we will use the Simplex LP algorithm with Integer Optimality set to 0%.