Optimization Methods in Business Analytics

<div class="xblock xblock-public_view xblock-public_view-vertical" data-usage-id="block-v1:MITx+15.053x+3T2016+type@vertical+block@acfcf1937d594ef3a2e333f8729aaddc" data-block-type="vertical" data-graded="True" data-course-id="course-v1:MITx+15.053x+3T2016" data-has-score="False" data-request-token="a7efc0db852911ef8f57023e4242adeb" data-init="VerticalStudentView" data-runtime-class="LmsRuntime" data-runtime-version="1"> <h2 class="hd hd-2 unit-title">Problem 1</h2> <div class="vert-mod"> <div class="vert vert-0" data-id="block-v1:MITx+15.053x+3T2016+type@problem+block@7369b3ba138f442b8110e40dde8f729a"> <div class="xblock xblock-public_view xblock-public_view-problem xmodule_display xmodule_ProblemBlock" data-usage-id="block-v1:MITx+15.053x+3T2016+type@problem+block@7369b3ba138f442b8110e40dde8f729a" data-block-type="problem" data-graded="True" data-course-id="course-v1:MITx+15.053x+3T2016" data-has-score="True" data-request-token="a7efc0db852911ef8f57023e4242adeb" data-init="XBlockToXModuleShim" data-runtime-class="LmsRuntime" data-runtime-version="1"> <script type="json/xblock-args" class="xblock-json-init-args"> {"xmodule-type": "Problem"} </script> <div id="problem_7369b3ba138f442b8110e40dde8f729a" class="problems-wrapper" role="group" aria-labelledby="7369b3ba138f442b8110e40dde8f729a-problem-title" data-problem-id="block-v1:MITx+15.053x+3T2016+type@problem+block@7369b3ba138f442b8110e40dde8f729a" data-url="/courses/course-v1:MITx+15.053x+3T2016/xblock/block-v1:MITx+15.053x+3T2016+type@problem+block@7369b3ba138f442b8110e40dde8f729a/handler/xmodule_handler" data-problem-score="0.0" data-problem-total-possible="1.0" data-attempts-used="0" data-content=" <h3 class="hd hd-3 problem-header" id="7369b3ba138f442b8110e40dde8f729a-problem-title" aria-describedby="block-v1:MITx+15.053x+3T2016+type@problem+block@7369b3ba138f442b8110e40dde8f729a-problem-progress" tabindex="-1"> PART A </h3> <div class="problem-progress" id="block-v1:MITx+15.053x+3T2016+type@problem+block@7369b3ba138f442b8110e40dde8f729a-problem-progress"></div> <div class="problem"> <div> <span> <p class="equation">\[\left.\begin{array}{rrcl} \max &amp; 32x_1 + 12x_2 + 22x_3 + 24x_4 + 18x_5 + 13x_6 \\ \text {s.t.:} &amp; &amp; &amp; \\ &amp; 5x_1 + 9x_2 + 7x_3 + 8x_4 + 6x_5 + 4x_6 \leq 200 \\ &amp; x_1, x_2, x_3 \in \{0,1\} \\ &amp; 0 \leq x_4, x_5, x_6 \leq 100 \end{array}\right\}\]</p> </span> <p>Which of the statements or constraints below is (by itself) equivalent to the statement "If $x_1=1$, then $ x_2=0$"? HINT: three of the choices are correct. </p> <div class="wrapper-problem-response" tabindex="-1" aria-label="Question 1" role="group"><div class="choicegroup capa_inputtype" id="inputtype_7369b3ba138f442b8110e40dde8f729a_2_1"> <fieldset aria-describedby="status_7369b3ba138f442b8110e40dde8f729a_2_1"> <div class="field"> <input type="checkbox" name="input_7369b3ba138f442b8110e40dde8f729a_2_1[]" id="input_7369b3ba138f442b8110e40dde8f729a_2_1_choice_0" class="field-input input-checkbox" value="choice_0"/><label id="7369b3ba138f442b8110e40dde8f729a_2_1-choice_0-label" for="input_7369b3ba138f442b8110e40dde8f729a_2_1_choice_0" class="response-label field-label label-inline" aria-describedby="status_7369b3ba138f442b8110e40dde8f729a_2_1"> If $x_2=0$ then $x_1=1$ </label> </div> <div class="field"> <input type="checkbox" name="input_7369b3ba138f442b8110e40dde8f729a_2_1[]" id="input_7369b3ba138f442b8110e40dde8f729a_2_1_choice_1" class="field-input input-checkbox" value="choice_1"/><label id="7369b3ba138f442b8110e40dde8f729a_2_1-choice_1-label" for="input_7369b3ba138f442b8110e40dde8f729a_2_1_choice_1" class="response-label field-label label-inline" aria-describedby="status_7369b3ba138f442b8110e40dde8f729a_2_1"> If $x_2=1$ then $x_1=0$ </label> </div> <div class="field"> <input type="checkbox" name="input_7369b3ba138f442b8110e40dde8f729a_2_1[]" id="input_7369b3ba138f442b8110e40dde8f729a_2_1_choice_2" class="field-input input-checkbox" value="choice_2"/><label id="7369b3ba138f442b8110e40dde8f729a_2_1-choice_2-label" for="input_7369b3ba138f442b8110e40dde8f729a_2_1_choice_2" class="response-label field-label label-inline" aria-describedby="status_7369b3ba138f442b8110e40dde8f729a_2_1"> $x_1=1$ or $x_2=1$ </label> </div> <div class="field"> <input type="checkbox" name="input_7369b3ba138f442b8110e40dde8f729a_2_1[]" id="input_7369b3ba138f442b8110e40dde8f729a_2_1_choice_3" class="field-input input-checkbox" value="choice_3"/><label id="7369b3ba138f442b8110e40dde8f729a_2_1-choice_3-label" for="input_7369b3ba138f442b8110e40dde8f729a_2_1_choice_3" class="response-label field-label label-inline" aria-describedby="status_7369b3ba138f442b8110e40dde8f729a_2_1"> $x_1=0$ or $x_2=0$ </label> </div> <div class="field"> <input type="checkbox" name="input_7369b3ba138f442b8110e40dde8f729a_2_1[]" id="input_7369b3ba138f442b8110e40dde8f729a_2_1_choice_4" class="field-input input-checkbox" value="choice_4"/><label id="7369b3ba138f442b8110e40dde8f729a_2_1-choice_4-label" for="input_7369b3ba138f442b8110e40dde8f729a_2_1_choice_4" class="response-label field-label label-inline" aria-describedby="status_7369b3ba138f442b8110e40dde8f729a_2_1"> $x_1+x_2 \leq 1$ </label> </div> <div class="field"> <input type="checkbox" name="input_7369b3ba138f442b8110e40dde8f729a_2_1[]" id="input_7369b3ba138f442b8110e40dde8f729a_2_1_choice_5" class="field-input input-checkbox" value="choice_5"/><label id="7369b3ba138f442b8110e40dde8f729a_2_1-choice_5-label" for="input_7369b3ba138f442b8110e40dde8f729a_2_1_choice_5" class="response-label field-label label-inline" aria-describedby="status_7369b3ba138f442b8110e40dde8f729a_2_1"> $x_1 - x_2 \leq 0$ </label> </div> <div class="field"> <input type="checkbox" name="input_7369b3ba138f442b8110e40dde8f729a_2_1[]" id="input_7369b3ba138f442b8110e40dde8f729a_2_1_choice_6" class="field-input input-checkbox" value="choice_6"/><label id="7369b3ba138f442b8110e40dde8f729a_2_1-choice_6-label" for="input_7369b3ba138f442b8110e40dde8f729a_2_1_choice_6" class="response-label field-label label-inline" aria-describedby="status_7369b3ba138f442b8110e40dde8f729a_2_1"> $x_1+x_2 \geq 1$ </label> </div> <div class="field"> <input type="checkbox" name="input_7369b3ba138f442b8110e40dde8f729a_2_1[]" id="input_7369b3ba138f442b8110e40dde8f729a_2_1_choice_7" class="field-input input-checkbox" value="choice_7"/><label id="7369b3ba138f442b8110e40dde8f729a_2_1-choice_7-label" for="input_7369b3ba138f442b8110e40dde8f729a_2_1_choice_7" class="response-label field-label label-inline" aria-describedby="status_7369b3ba138f442b8110e40dde8f729a_2_1"> $x_1 \neq x_2$ </label> </div> <span id="answer_7369b3ba138f442b8110e40dde8f729a_2_1"/> </fieldset> <div class="indicator-container"> <span class="status unanswered" id="status_7369b3ba138f442b8110e40dde8f729a_2_1" data-tooltip="Not yet answered."> <span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/> </span> </div> </div></div> <div class="solution-span"> <span id="solution_7369b3ba138f442b8110e40dde8f729a_solution_1"/> </div></div> <div class="action"> <input type="hidden" name="problem_id" value="PART A" /> <div class="submit-attempt-container"> <button type="button" class="submit btn-brand" data-submitting="Submitting" data-value="Submit" data-should-enable-submit-button="True" aria-describedby="submission_feedback_7369b3ba138f442b8110e40dde8f729a" > <span class="submit-label">Submit</span> </button> <div class="submission-feedback" id="submission_feedback_7369b3ba138f442b8110e40dde8f729a"> <span class="sr">Some problems have options such as save, reset, hints, or show answer. These options follow the Submit button.</span> </div> </div> <div class="problem-action-buttons-wrapper"> </div> </div> <div class="notification warning notification-gentle-alert is-hidden" tabindex="-1"> <span class="icon fa fa-exclamation-circle" aria-hidden="true"></span> <span class="notification-message" aria-describedby="7369b3ba138f442b8110e40dde8f729a-problem-title"> </span> <div class="notification-btn-wrapper"> <button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button> </div> </div> <div class="notification warning notification-save is-hidden" tabindex="-1"> <span class="icon fa fa-save" aria-hidden="true"></span> <span class="notification-message" aria-describedby="7369b3ba138f442b8110e40dde8f729a-problem-title">None </span> <div class="notification-btn-wrapper"> <button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button> </div> </div> <div class="notification general notification-show-answer is-hidden" tabindex="-1"> <span class="icon fa fa-info-circle" aria-hidden="true"></span> <span class="notification-message" aria-describedby="7369b3ba138f442b8110e40dde8f729a-problem-title">Answers are displayed within the problem </span> <div class="notification-btn-wrapper"> <button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button> </div> </div> </div> " data-graded="True"> <p class="loading-spinner"> <i class="fa fa-spinner fa-pulse fa-2x fa-fw"></i> <span class="sr">Loading…</span> </p> </div> </div> </div> <div class="vert vert-1" data-id="block-v1:MITx+15.053x+3T2016+type@problem+block@c433ef52260e4dbba6c80a9d6e9f0828"> <div class="xblock xblock-public_view xblock-public_view-problem xmodule_display xmodule_ProblemBlock" data-usage-id="block-v1:MITx+15.053x+3T2016+type@problem+block@c433ef52260e4dbba6c80a9d6e9f0828" data-block-type="problem" data-graded="True" data-course-id="course-v1:MITx+15.053x+3T2016" data-has-score="True" data-request-token="a7efc0db852911ef8f57023e4242adeb" data-init="XBlockToXModuleShim" data-runtime-class="LmsRuntime" data-runtime-version="1"> <script type="json/xblock-args" class="xblock-json-init-args"> {"xmodule-type": "Problem"} </script> <div id="problem_c433ef52260e4dbba6c80a9d6e9f0828" class="problems-wrapper" role="group" aria-labelledby="c433ef52260e4dbba6c80a9d6e9f0828-problem-title" data-problem-id="block-v1:MITx+15.053x+3T2016+type@problem+block@c433ef52260e4dbba6c80a9d6e9f0828" data-url="/courses/course-v1:MITx+15.053x+3T2016/xblock/block-v1:MITx+15.053x+3T2016+type@problem+block@c433ef52260e4dbba6c80a9d6e9f0828/handler/xmodule_handler" data-problem-score="0.0" data-problem-total-possible="1.0" data-attempts-used="0" data-content=" <h3 class="hd hd-3 problem-header" id="c433ef52260e4dbba6c80a9d6e9f0828-problem-title" aria-describedby="block-v1:MITx+15.053x+3T2016+type@problem+block@c433ef52260e4dbba6c80a9d6e9f0828-problem-progress" tabindex="-1"> PART B </h3> <div class="problem-progress" id="block-v1:MITx+15.053x+3T2016+type@problem+block@c433ef52260e4dbba6c80a9d6e9f0828-problem-progress"></div> <div class="problem"> <div> <p>Which of the statements or constraints below is (by itself) equivalent to the statement "$x_2=1$ or $ x_3=0$ but not both"? HINT: two of the answers are correct. </p> <div class="wrapper-problem-response" tabindex="-1" aria-label="Question 1" role="group"><div class="choicegroup capa_inputtype" id="inputtype_c433ef52260e4dbba6c80a9d6e9f0828_2_1"> <fieldset aria-describedby="status_c433ef52260e4dbba6c80a9d6e9f0828_2_1"> <div class="field"> <input type="checkbox" name="input_c433ef52260e4dbba6c80a9d6e9f0828_2_1[]" id="input_c433ef52260e4dbba6c80a9d6e9f0828_2_1_choice_0" class="field-input input-checkbox" value="choice_0"/><label id="c433ef52260e4dbba6c80a9d6e9f0828_2_1-choice_0-label" for="input_c433ef52260e4dbba6c80a9d6e9f0828_2_1_choice_0" class="response-label field-label label-inline" aria-describedby="status_c433ef52260e4dbba6c80a9d6e9f0828_2_1"> $x_2=(1-x_3)$ </label> </div> <div class="field"> <input type="checkbox" name="input_c433ef52260e4dbba6c80a9d6e9f0828_2_1[]" id="input_c433ef52260e4dbba6c80a9d6e9f0828_2_1_choice_1" class="field-input input-checkbox" value="choice_1"/><label id="c433ef52260e4dbba6c80a9d6e9f0828_2_1-choice_1-label" for="input_c433ef52260e4dbba6c80a9d6e9f0828_2_1_choice_1" class="response-label field-label label-inline" aria-describedby="status_c433ef52260e4dbba6c80a9d6e9f0828_2_1"> $x_2=x_3$ </label> </div> <div class="field"> <input type="checkbox" name="input_c433ef52260e4dbba6c80a9d6e9f0828_2_1[]" id="input_c433ef52260e4dbba6c80a9d6e9f0828_2_1_choice_2" class="field-input input-checkbox" value="choice_2"/><label id="c433ef52260e4dbba6c80a9d6e9f0828_2_1-choice_2-label" for="input_c433ef52260e4dbba6c80a9d6e9f0828_2_1_choice_2" class="response-label field-label label-inline" aria-describedby="status_c433ef52260e4dbba6c80a9d6e9f0828_2_1"> $x_2 \neq x_3$ </label> </div> <div class="field"> <input type="checkbox" name="input_c433ef52260e4dbba6c80a9d6e9f0828_2_1[]" id="input_c433ef52260e4dbba6c80a9d6e9f0828_2_1_choice_3" class="field-input input-checkbox" value="choice_3"/><label id="c433ef52260e4dbba6c80a9d6e9f0828_2_1-choice_3-label" for="input_c433ef52260e4dbba6c80a9d6e9f0828_2_1_choice_3" class="response-label field-label label-inline" aria-describedby="status_c433ef52260e4dbba6c80a9d6e9f0828_2_1"> $x_2-x_3 \leq 0$ </label> </div> <div class="field"> <input type="checkbox" name="input_c433ef52260e4dbba6c80a9d6e9f0828_2_1[]" id="input_c433ef52260e4dbba6c80a9d6e9f0828_2_1_choice_4" class="field-input input-checkbox" value="choice_4"/><label id="c433ef52260e4dbba6c80a9d6e9f0828_2_1-choice_4-label" for="input_c433ef52260e4dbba6c80a9d6e9f0828_2_1_choice_4" class="response-label field-label label-inline" aria-describedby="status_c433ef52260e4dbba6c80a9d6e9f0828_2_1"> $-x_2-x_3 \leq 0$ </label> </div> <div class="field"> <input type="checkbox" name="input_c433ef52260e4dbba6c80a9d6e9f0828_2_1[]" id="input_c433ef52260e4dbba6c80a9d6e9f0828_2_1_choice_5" class="field-input input-checkbox" value="choice_5"/><label id="c433ef52260e4dbba6c80a9d6e9f0828_2_1-choice_5-label" for="input_c433ef52260e4dbba6c80a9d6e9f0828_2_1_choice_5" class="response-label field-label label-inline" aria-describedby="status_c433ef52260e4dbba6c80a9d6e9f0828_2_1"> If $x_2=1$ then $x_3=1$ </label> </div> <div class="field"> <input type="checkbox" name="input_c433ef52260e4dbba6c80a9d6e9f0828_2_1[]" id="input_c433ef52260e4dbba6c80a9d6e9f0828_2_1_choice_6" class="field-input input-checkbox" value="choice_6"/><label id="c433ef52260e4dbba6c80a9d6e9f0828_2_1-choice_6-label" for="input_c433ef52260e4dbba6c80a9d6e9f0828_2_1_choice_6" class="response-label field-label label-inline" aria-describedby="status_c433ef52260e4dbba6c80a9d6e9f0828_2_1"> $x_2=0$ or $x_3=1$ but not both </label> </div> <span id="answer_c433ef52260e4dbba6c80a9d6e9f0828_2_1"/> </fieldset> <div class="indicator-container"> <span class="status unanswered" id="status_c433ef52260e4dbba6c80a9d6e9f0828_2_1" data-tooltip="Not yet answered."> <span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/> </span> </div> </div></div> <div class="solution-span"> <span id="solution_c433ef52260e4dbba6c80a9d6e9f0828_solution_1"/> </div></div> <div class="action"> <input type="hidden" name="problem_id" value="PART B" /> <div class="submit-attempt-container"> <button type="button" class="submit btn-brand" data-submitting="Submitting" data-value="Submit" data-should-enable-submit-button="True" aria-describedby="submission_feedback_c433ef52260e4dbba6c80a9d6e9f0828" > <span class="submit-label">Submit</span> </button> <div class="submission-feedback" id="submission_feedback_c433ef52260e4dbba6c80a9d6e9f0828"> <span class="sr">Some problems have options such as save, reset, hints, or show answer. These options follow the Submit button.</span> </div> </div> <div class="problem-action-buttons-wrapper"> </div> </div> <div class="notification warning notification-gentle-alert is-hidden" tabindex="-1"> <span class="icon fa fa-exclamation-circle" aria-hidden="true"></span> <span class="notification-message" aria-describedby="c433ef52260e4dbba6c80a9d6e9f0828-problem-title"> </span> <div class="notification-btn-wrapper"> <button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button> </div> </div> <div class="notification warning notification-save is-hidden" tabindex="-1"> <span class="icon fa fa-save" aria-hidden="true"></span> <span class="notification-message" aria-describedby="c433ef52260e4dbba6c80a9d6e9f0828-problem-title">None </span> <div class="notification-btn-wrapper"> <button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button> </div> </div> <div class="notification general notification-show-answer is-hidden" tabindex="-1"> <span class="icon fa fa-info-circle" aria-hidden="true"></span> <span class="notification-message" aria-describedby="c433ef52260e4dbba6c80a9d6e9f0828-problem-title">Answers are displayed within the problem </span> <div class="notification-btn-wrapper"> <button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button> </div> </div> </div> " data-graded="True"> <p class="loading-spinner"> <i class="fa fa-spinner fa-pulse fa-2x fa-fw"></i> <span class="sr">Loading…</span> </p> </div> </div> </div> <div class="vert vert-2" data-id="block-v1:MITx+15.053x+3T2016+type@problem+block@633026b1fea04ff3a5777e5ed024826d"> <div class="xblock xblock-public_view xblock-public_view-problem xmodule_display xmodule_ProblemBlock" data-usage-id="block-v1:MITx+15.053x+3T2016+type@problem+block@633026b1fea04ff3a5777e5ed024826d" data-block-type="problem" data-graded="True" data-course-id="course-v1:MITx+15.053x+3T2016" data-has-score="True" data-request-token="a7efc0db852911ef8f57023e4242adeb" data-init="XBlockToXModuleShim" data-runtime-class="LmsRuntime" data-runtime-version="1"> <script type="json/xblock-args" class="xblock-json-init-args"> {"xmodule-type": "Problem"} </script> <div id="problem_633026b1fea04ff3a5777e5ed024826d" class="problems-wrapper" role="group" aria-labelledby="633026b1fea04ff3a5777e5ed024826d-problem-title" data-problem-id="block-v1:MITx+15.053x+3T2016+type@problem+block@633026b1fea04ff3a5777e5ed024826d" data-url="/courses/course-v1:MITx+15.053x+3T2016/xblock/block-v1:MITx+15.053x+3T2016+type@problem+block@633026b1fea04ff3a5777e5ed024826d/handler/xmodule_handler" data-problem-score="0.0" data-problem-total-possible="1.0" data-attempts-used="0" data-content=" <h3 class="hd hd-3 problem-header" id="633026b1fea04ff3a5777e5ed024826d-problem-title" aria-describedby="block-v1:MITx+15.053x+3T2016+type@problem+block@633026b1fea04ff3a5777e5ed024826d-problem-progress" tabindex="-1"> PART C </h3> <div class="problem-progress" id="block-v1:MITx+15.053x+3T2016+type@problem+block@633026b1fea04ff3a5777e5ed024826d-problem-progress"></div> <div class="problem"> <div> <div class="wrapper-problem-response" tabindex="-1" aria-label="Question 1" role="group"><div class="choicegroup capa_inputtype" id="inputtype_633026b1fea04ff3a5777e5ed024826d_2_1"> <fieldset aria-describedby="status_633026b1fea04ff3a5777e5ed024826d_2_1"> <legend id="633026b1fea04ff3a5777e5ed024826d_2_1-legend" class="response-fieldset-legend field-group-hd">Add a binary variable $w_1$, and add two constraints that ensure that if $w_1 = 1$ then $x_5 + x_6 \ge 70$, and if $w_1 = 0$ then $x_5 + x_6 \le 69$. Select the two correct constraints from below.</legend> <div class="field"> <input type="checkbox" name="input_633026b1fea04ff3a5777e5ed024826d_2_1[]" id="input_633026b1fea04ff3a5777e5ed024826d_2_1_choice_0" class="field-input input-checkbox" value="choice_0"/><label id="633026b1fea04ff3a5777e5ed024826d_2_1-choice_0-label" for="input_633026b1fea04ff3a5777e5ed024826d_2_1_choice_0" class="response-label field-label label-inline" aria-describedby="status_633026b1fea04ff3a5777e5ed024826d_2_1"> $x_5 + x_6 \ge 70 + M (1 - w_1), w_1 \in \{0,1\} $ </label> </div> <div class="field"> <input type="checkbox" name="input_633026b1fea04ff3a5777e5ed024826d_2_1[]" id="input_633026b1fea04ff3a5777e5ed024826d_2_1_choice_1" class="field-input input-checkbox" value="choice_1"/><label id="633026b1fea04ff3a5777e5ed024826d_2_1-choice_1-label" for="input_633026b1fea04ff3a5777e5ed024826d_2_1_choice_1" class="response-label field-label label-inline" aria-describedby="status_633026b1fea04ff3a5777e5ed024826d_2_1"> $x_5 + x_6 \ge 70 - M (1 - w_1), w_1 \in \{0,1\} $ </label> </div> <div class="field"> <input type="checkbox" name="input_633026b1fea04ff3a5777e5ed024826d_2_1[]" id="input_633026b1fea04ff3a5777e5ed024826d_2_1_choice_2" class="field-input input-checkbox" value="choice_2"/><label id="633026b1fea04ff3a5777e5ed024826d_2_1-choice_2-label" for="input_633026b1fea04ff3a5777e5ed024826d_2_1_choice_2" class="response-label field-label label-inline" aria-describedby="status_633026b1fea04ff3a5777e5ed024826d_2_1"> $x_5 + x_6 \le 69 + M (1 - w_1), w_1 \in \{0,1\} $ </label> </div> <div class="field"> <input type="checkbox" name="input_633026b1fea04ff3a5777e5ed024826d_2_1[]" id="input_633026b1fea04ff3a5777e5ed024826d_2_1_choice_3" class="field-input input-checkbox" value="choice_3"/><label id="633026b1fea04ff3a5777e5ed024826d_2_1-choice_3-label" for="input_633026b1fea04ff3a5777e5ed024826d_2_1_choice_3" class="response-label field-label label-inline" aria-describedby="status_633026b1fea04ff3a5777e5ed024826d_2_1"> $x_5 + x_6 \le 69 + Mw_1, w_1 \in \{0,1\} $ </label> </div> <div class="field"> <input type="checkbox" name="input_633026b1fea04ff3a5777e5ed024826d_2_1[]" id="input_633026b1fea04ff3a5777e5ed024826d_2_1_choice_4" class="field-input input-checkbox" value="choice_4"/><label id="633026b1fea04ff3a5777e5ed024826d_2_1-choice_4-label" for="input_633026b1fea04ff3a5777e5ed024826d_2_1_choice_4" class="response-label field-label label-inline" aria-describedby="status_633026b1fea04ff3a5777e5ed024826d_2_1"> $x_5 + x_6 \le 69 - Mw_1, w_1 \in \{0,1\} $ </label> </div> <span id="answer_633026b1fea04ff3a5777e5ed024826d_2_1"/> </fieldset> <div class="indicator-container"> <span class="status unanswered" id="status_633026b1fea04ff3a5777e5ed024826d_2_1" data-tooltip="Not yet answered."> <span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/> </span> </div> </div></div> <div class="solution-span"> <span id="solution_633026b1fea04ff3a5777e5ed024826d_solution_1"/> </div></div> <div class="action"> <input type="hidden" name="problem_id" value="PART C" /> <div class="submit-attempt-container"> <button type="button" class="submit btn-brand" data-submitting="Submitting" data-value="Submit" data-should-enable-submit-button="True" aria-describedby="submission_feedback_633026b1fea04ff3a5777e5ed024826d" > <span class="submit-label">Submit</span> </button> <div class="submission-feedback" id="submission_feedback_633026b1fea04ff3a5777e5ed024826d"> <span class="sr">Some problems have options such as save, reset, hints, or show answer. These options follow the Submit button.</span> </div> </div> <div class="problem-action-buttons-wrapper"> </div> </div> <div class="notification warning notification-gentle-alert is-hidden" tabindex="-1"> <span class="icon fa fa-exclamation-circle" aria-hidden="true"></span> <span class="notification-message" aria-describedby="633026b1fea04ff3a5777e5ed024826d-problem-title"> </span> <div class="notification-btn-wrapper"> <button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button> </div> </div> <div class="notification warning notification-save is-hidden" tabindex="-1"> <span class="icon fa fa-save" aria-hidden="true"></span> <span class="notification-message" aria-describedby="633026b1fea04ff3a5777e5ed024826d-problem-title">None </span> <div class="notification-btn-wrapper"> <button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button> </div> </div> <div class="notification general notification-show-answer is-hidden" tabindex="-1"> <span class="icon fa fa-info-circle" aria-hidden="true"></span> <span class="notification-message" aria-describedby="633026b1fea04ff3a5777e5ed024826d-problem-title">Answers are displayed within the problem </span> <div class="notification-btn-wrapper"> <button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button> </div> </div> </div> " data-graded="True"> <p class="loading-spinner"> <i class="fa fa-spinner fa-pulse fa-2x fa-fw"></i> <span class="sr">Loading…</span> </p> </div> </div> </div> <div class="vert vert-3" data-id="block-v1:MITx+15.053x+3T2016+type@problem+block@463a41121fa74d3799d6da3e4a691352"> <div class="xblock xblock-public_view xblock-public_view-problem xmodule_display xmodule_ProblemBlock" data-usage-id="block-v1:MITx+15.053x+3T2016+type@problem+block@463a41121fa74d3799d6da3e4a691352" data-block-type="problem" data-graded="True" data-course-id="course-v1:MITx+15.053x+3T2016" data-has-score="True" data-request-token="a7efc0db852911ef8f57023e4242adeb" data-init="XBlockToXModuleShim" data-runtime-class="LmsRuntime" data-runtime-version="1"> <script type="json/xblock-args" class="xblock-json-init-args"> {"xmodule-type": "Problem"} </script> <div id="problem_463a41121fa74d3799d6da3e4a691352" class="problems-wrapper" role="group" aria-labelledby="463a41121fa74d3799d6da3e4a691352-problem-title" data-problem-id="block-v1:MITx+15.053x+3T2016+type@problem+block@463a41121fa74d3799d6da3e4a691352" data-url="/courses/course-v1:MITx+15.053x+3T2016/xblock/block-v1:MITx+15.053x+3T2016+type@problem+block@463a41121fa74d3799d6da3e4a691352/handler/xmodule_handler" data-problem-score="0.0" data-problem-total-possible="1.0" data-attempts-used="0" data-content=" <h3 class="hd hd-3 problem-header" id="463a41121fa74d3799d6da3e4a691352-problem-title" aria-describedby="block-v1:MITx+15.053x+3T2016+type@problem+block@463a41121fa74d3799d6da3e4a691352-problem-progress" tabindex="-1"> PART D </h3> <div class="problem-progress" id="block-v1:MITx+15.053x+3T2016+type@problem+block@463a41121fa74d3799d6da3e4a691352-problem-progress"></div> <div class="problem"> <div> <p>Add 3 binary variables $w_2, w_3$, and $w_4$, and 4 constraints so as to ensure that at least one of the constraints $x_4 \le 92, x_5 \ge 40,$ and $x_6 \le 74$ are satisfied. Select the 4 correct constraints below.</p> <div class="wrapper-problem-response" tabindex="-1" aria-label="Question 1" role="group"><div class="choicegroup capa_inputtype" id="inputtype_463a41121fa74d3799d6da3e4a691352_2_1"> <fieldset aria-describedby="status_463a41121fa74d3799d6da3e4a691352_2_1"> <div class="field"> <input type="checkbox" name="input_463a41121fa74d3799d6da3e4a691352_2_1[]" id="input_463a41121fa74d3799d6da3e4a691352_2_1_choice_0" class="field-input input-checkbox" value="choice_0"/><label id="463a41121fa74d3799d6da3e4a691352_2_1-choice_0-label" for="input_463a41121fa74d3799d6da3e4a691352_2_1_choice_0" class="response-label field-label label-inline" aria-describedby="status_463a41121fa74d3799d6da3e4a691352_2_1"> $ x_4 \le 92 + M (1 &#8211; w_2) $ </label> </div> <div class="field"> <input type="checkbox" name="input_463a41121fa74d3799d6da3e4a691352_2_1[]" id="input_463a41121fa74d3799d6da3e4a691352_2_1_choice_1" class="field-input input-checkbox" value="choice_1"/><label id="463a41121fa74d3799d6da3e4a691352_2_1-choice_1-label" for="input_463a41121fa74d3799d6da3e4a691352_2_1_choice_1" class="response-label field-label label-inline" aria-describedby="status_463a41121fa74d3799d6da3e4a691352_2_1"> $ x_4 \le 92 &#8211; M (1 &#8211; w_2) $ </label> </div> <div class="field"> <input type="checkbox" name="input_463a41121fa74d3799d6da3e4a691352_2_1[]" id="input_463a41121fa74d3799d6da3e4a691352_2_1_choice_2" class="field-input input-checkbox" value="choice_2"/><label id="463a41121fa74d3799d6da3e4a691352_2_1-choice_2-label" for="input_463a41121fa74d3799d6da3e4a691352_2_1_choice_2" class="response-label field-label label-inline" aria-describedby="status_463a41121fa74d3799d6da3e4a691352_2_1"> $ x_5 \ge 40 + M (1 &#8211; w_3) $ </label> </div> <div class="field"> <input type="checkbox" name="input_463a41121fa74d3799d6da3e4a691352_2_1[]" id="input_463a41121fa74d3799d6da3e4a691352_2_1_choice_3" class="field-input input-checkbox" value="choice_3"/><label id="463a41121fa74d3799d6da3e4a691352_2_1-choice_3-label" for="input_463a41121fa74d3799d6da3e4a691352_2_1_choice_3" class="response-label field-label label-inline" aria-describedby="status_463a41121fa74d3799d6da3e4a691352_2_1"> $ x_5 \ge 40 &#8211; M (1 &#8211; w_3)$ </label> </div> <div class="field"> <input type="checkbox" name="input_463a41121fa74d3799d6da3e4a691352_2_1[]" id="input_463a41121fa74d3799d6da3e4a691352_2_1_choice_4" class="field-input input-checkbox" value="choice_4"/><label id="463a41121fa74d3799d6da3e4a691352_2_1-choice_4-label" for="input_463a41121fa74d3799d6da3e4a691352_2_1_choice_4" class="response-label field-label label-inline" aria-describedby="status_463a41121fa74d3799d6da3e4a691352_2_1"> $ x_6 \le 74 + M (1 &#8211; w_4) $ </label> </div> <div class="field"> <input type="checkbox" name="input_463a41121fa74d3799d6da3e4a691352_2_1[]" id="input_463a41121fa74d3799d6da3e4a691352_2_1_choice_5" class="field-input input-checkbox" value="choice_5"/><label id="463a41121fa74d3799d6da3e4a691352_2_1-choice_5-label" for="input_463a41121fa74d3799d6da3e4a691352_2_1_choice_5" class="response-label field-label label-inline" aria-describedby="status_463a41121fa74d3799d6da3e4a691352_2_1"> $ x_6 \le 74 &#8211; M (1 &#8211; w_4)$ </label> </div> <div class="field"> <input type="checkbox" name="input_463a41121fa74d3799d6da3e4a691352_2_1[]" id="input_463a41121fa74d3799d6da3e4a691352_2_1_choice_6" class="field-input input-checkbox" value="choice_6"/><label id="463a41121fa74d3799d6da3e4a691352_2_1-choice_6-label" for="input_463a41121fa74d3799d6da3e4a691352_2_1_choice_6" class="response-label field-label label-inline" aria-describedby="status_463a41121fa74d3799d6da3e4a691352_2_1"> $ w_2 + w_3 + w_4 \ge 1, w_2, w_3, w_4 \in \{0, 1\}$ </label> </div> <div class="field"> <input type="checkbox" name="input_463a41121fa74d3799d6da3e4a691352_2_1[]" id="input_463a41121fa74d3799d6da3e4a691352_2_1_choice_7" class="field-input input-checkbox" value="choice_7"/><label id="463a41121fa74d3799d6da3e4a691352_2_1-choice_7-label" for="input_463a41121fa74d3799d6da3e4a691352_2_1_choice_7" class="response-label field-label label-inline" aria-describedby="status_463a41121fa74d3799d6da3e4a691352_2_1"> $ w_2 + w_3 + w_4 \le 1, w_2, w_3, w_4 \in \{0, 1\}$ </label> </div> <span id="answer_463a41121fa74d3799d6da3e4a691352_2_1"/> </fieldset> <div class="indicator-container"> <span class="status unanswered" id="status_463a41121fa74d3799d6da3e4a691352_2_1" data-tooltip="Not yet answered."> <span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/> </span> </div> </div></div> <div class="solution-span"> <span id="solution_463a41121fa74d3799d6da3e4a691352_solution_1"/> </div></div> <div class="action"> <input type="hidden" name="problem_id" value="PART D" /> <div class="submit-attempt-container"> <button type="button" class="submit btn-brand" data-submitting="Submitting" data-value="Submit" data-should-enable-submit-button="True" aria-describedby="submission_feedback_463a41121fa74d3799d6da3e4a691352" > <span class="submit-label">Submit</span> </button> <div class="submission-feedback" id="submission_feedback_463a41121fa74d3799d6da3e4a691352"> <span class="sr">Some problems have options such as save, reset, hints, or show answer. These options follow the Submit button.</span> </div> </div> <div class="problem-action-buttons-wrapper"> </div> </div> <div class="notification warning notification-gentle-alert is-hidden" tabindex="-1"> <span class="icon fa fa-exclamation-circle" aria-hidden="true"></span> <span class="notification-message" aria-describedby="463a41121fa74d3799d6da3e4a691352-problem-title"> </span> <div class="notification-btn-wrapper"> <button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button> </div> </div> <div class="notification warning notification-save is-hidden" tabindex="-1"> <span class="icon fa fa-save" aria-hidden="true"></span> <span class="notification-message" aria-describedby="463a41121fa74d3799d6da3e4a691352-problem-title">None </span> <div class="notification-btn-wrapper"> <button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button> </div> </div> <div class="notification general notification-show-answer is-hidden" tabindex="-1"> <span class="icon fa fa-info-circle" aria-hidden="true"></span> <span class="notification-message" aria-describedby="463a41121fa74d3799d6da3e4a691352-problem-title">Answers are displayed within the problem </span> <div class="notification-btn-wrapper"> <button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button> </div> </div> </div> " data-graded="True"> <p class="loading-spinner"> <i class="fa fa-spinner fa-pulse fa-2x fa-fw"></i> <span class="sr">Loading…</span> </p> </div> </div> </div> <div class="vert vert-4" data-id="block-v1:MITx+15.053x+3T2016+type@problem+block@382dcf1d014e4633b5203b268716eabd"> <div class="xblock xblock-public_view xblock-public_view-problem xmodule_display xmodule_ProblemBlock" data-usage-id="block-v1:MITx+15.053x+3T2016+type@problem+block@382dcf1d014e4633b5203b268716eabd" data-block-type="problem" data-graded="True" data-course-id="course-v1:MITx+15.053x+3T2016" data-has-score="True" data-request-token="a7efc0db852911ef8f57023e4242adeb" data-init="XBlockToXModuleShim" data-runtime-class="LmsRuntime" data-runtime-version="1"> <script type="json/xblock-args" class="xblock-json-init-args"> {"xmodule-type": "Problem"} </script> <div id="problem_382dcf1d014e4633b5203b268716eabd" class="problems-wrapper" role="group" aria-labelledby="382dcf1d014e4633b5203b268716eabd-problem-title" data-problem-id="block-v1:MITx+15.053x+3T2016+type@problem+block@382dcf1d014e4633b5203b268716eabd" data-url="/courses/course-v1:MITx+15.053x+3T2016/xblock/block-v1:MITx+15.053x+3T2016+type@problem+block@382dcf1d014e4633b5203b268716eabd/handler/xmodule_handler" data-problem-score="0.0" data-problem-total-possible="1.0" data-attempts-used="0" data-content=" <h3 class="hd hd-3 problem-header" id="382dcf1d014e4633b5203b268716eabd-problem-title" aria-describedby="block-v1:MITx+15.053x+3T2016+type@problem+block@382dcf1d014e4633b5203b268716eabd-problem-progress" tabindex="-1"> PART E </h3> <div class="problem-progress" id="block-v1:MITx+15.053x+3T2016+type@problem+block@382dcf1d014e4633b5203b268716eabd-problem-progress"></div> <div class="problem"> <div> <p>Add a single integer variable $w_5$ and a constraint that ensures that $x_6$ is divisible by 2 but not divisible by 4. Equivalently, the remainder when dividing by 4 must be 2. Which of the following constraints satisfies these conditions? Select only one of them.</p> <div class="wrapper-problem-response" tabindex="-1" aria-label="Question 1" role="group"><div class="choicegroup capa_inputtype" id="inputtype_382dcf1d014e4633b5203b268716eabd_2_1"> <fieldset aria-describedby="status_382dcf1d014e4633b5203b268716eabd_2_1"> <div class="field"> <input type="radio" name="input_382dcf1d014e4633b5203b268716eabd_2_1" id="input_382dcf1d014e4633b5203b268716eabd_2_1_choice_0" class="field-input input-radio" value="choice_0"/><label id="382dcf1d014e4633b5203b268716eabd_2_1-choice_0-label" for="input_382dcf1d014e4633b5203b268716eabd_2_1_choice_0" class="response-label field-label label-inline" aria-describedby="status_382dcf1d014e4633b5203b268716eabd_2_1"> $x_6 + 2w_5 = 4, w_5 \ge 0, w_5 \in \bf{Z}$ </label> </div> <div class="field"> <input type="radio" name="input_382dcf1d014e4633b5203b268716eabd_2_1" id="input_382dcf1d014e4633b5203b268716eabd_2_1_choice_1" class="field-input input-radio" value="choice_1"/><label id="382dcf1d014e4633b5203b268716eabd_2_1-choice_1-label" for="input_382dcf1d014e4633b5203b268716eabd_2_1_choice_1" class="response-label field-label label-inline" aria-describedby="status_382dcf1d014e4633b5203b268716eabd_2_1"> $x_6 &#8211; 2w_5 = 4, w_5 \ge 0, w_5 \in \bf{Z}$ </label> </div> <div class="field"> <input type="radio" name="input_382dcf1d014e4633b5203b268716eabd_2_1" id="input_382dcf1d014e4633b5203b268716eabd_2_1_choice_2" class="field-input input-radio" value="choice_2"/><label id="382dcf1d014e4633b5203b268716eabd_2_1-choice_2-label" for="input_382dcf1d014e4633b5203b268716eabd_2_1_choice_2" class="response-label field-label label-inline" aria-describedby="status_382dcf1d014e4633b5203b268716eabd_2_1"> $x_6 &#8211; 4w_5 = 2, w_5 \ge 0, w_5 \in \bf{Z}$ </label> </div> <div class="field"> <input type="radio" name="input_382dcf1d014e4633b5203b268716eabd_2_1" id="input_382dcf1d014e4633b5203b268716eabd_2_1_choice_3" class="field-input input-radio" value="choice_3"/><label id="382dcf1d014e4633b5203b268716eabd_2_1-choice_3-label" for="input_382dcf1d014e4633b5203b268716eabd_2_1_choice_3" class="response-label field-label label-inline" aria-describedby="status_382dcf1d014e4633b5203b268716eabd_2_1"> $x_6 + 4w_5 = 2, w_5 \ge 0, w_5 \in \bf{Z}$ </label> </div> <div class="field"> <input type="radio" name="input_382dcf1d014e4633b5203b268716eabd_2_1" id="input_382dcf1d014e4633b5203b268716eabd_2_1_choice_4" class="field-input input-radio" value="choice_4"/><label id="382dcf1d014e4633b5203b268716eabd_2_1-choice_4-label" for="input_382dcf1d014e4633b5203b268716eabd_2_1_choice_4" class="response-label field-label label-inline" aria-describedby="status_382dcf1d014e4633b5203b268716eabd_2_1"> None of the choices </label> </div> <span id="answer_382dcf1d014e4633b5203b268716eabd_2_1"/> </fieldset> <div class="indicator-container"> <span class="status unanswered" id="status_382dcf1d014e4633b5203b268716eabd_2_1" data-tooltip="Not yet answered."> <span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/> </span> </div> </div></div> <div class="solution-span"> <span id="solution_382dcf1d014e4633b5203b268716eabd_solution_1"/> </div></div> <div class="action"> <input type="hidden" name="problem_id" value="PART E" /> <div class="submit-attempt-container"> <button type="button" class="submit btn-brand" data-submitting="Submitting" data-value="Submit" data-should-enable-submit-button="True" aria-describedby="submission_feedback_382dcf1d014e4633b5203b268716eabd" > <span class="submit-label">Submit</span> </button> <div class="submission-feedback" id="submission_feedback_382dcf1d014e4633b5203b268716eabd"> <span class="sr">Some problems have options such as save, reset, hints, or show answer. These options follow the Submit button.</span> </div> </div> <div class="problem-action-buttons-wrapper"> </div> </div> <div class="notification warning notification-gentle-alert is-hidden" tabindex="-1"> <span class="icon fa fa-exclamation-circle" aria-hidden="true"></span> <span class="notification-message" aria-describedby="382dcf1d014e4633b5203b268716eabd-problem-title"> </span> <div class="notification-btn-wrapper"> <button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button> </div> </div> <div class="notification warning notification-save is-hidden" tabindex="-1"> <span class="icon fa fa-save" aria-hidden="true"></span> <span class="notification-message" aria-describedby="382dcf1d014e4633b5203b268716eabd-problem-title">None </span> <div class="notification-btn-wrapper"> <button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button> </div> </div> <div class="notification general notification-show-answer is-hidden" tabindex="-1"> <span class="icon fa fa-info-circle" aria-hidden="true"></span> <span class="notification-message" aria-describedby="382dcf1d014e4633b5203b268716eabd-problem-title">Answers are displayed within the problem </span> <div class="notification-btn-wrapper"> <button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button> </div> </div> </div> " data-graded="True"> <p class="loading-spinner"> <i class="fa fa-spinner fa-pulse fa-2x fa-fw"></i> <span class="sr">Loading…</span> </p> </div> </div> </div> <div class="vert vert-5" data-id="block-v1:MITx+15.053x+3T2016+type@problem+block@b567c4a43e28451bbc93ce9c3cd23d9b"> <div class="xblock xblock-public_view xblock-public_view-problem xmodule_display xmodule_ProblemBlock" data-usage-id="block-v1:MITx+15.053x+3T2016+type@problem+block@b567c4a43e28451bbc93ce9c3cd23d9b" data-block-type="problem" data-graded="True" data-course-id="course-v1:MITx+15.053x+3T2016" data-has-score="True" data-request-token="a7efc0db852911ef8f57023e4242adeb" data-init="XBlockToXModuleShim" data-runtime-class="LmsRuntime" data-runtime-version="1"> <script type="json/xblock-args" class="xblock-json-init-args"> {"xmodule-type": "Problem"} </script> <div id="problem_b567c4a43e28451bbc93ce9c3cd23d9b" class="problems-wrapper" role="group" aria-labelledby="b567c4a43e28451bbc93ce9c3cd23d9b-problem-title" data-problem-id="block-v1:MITx+15.053x+3T2016+type@problem+block@b567c4a43e28451bbc93ce9c3cd23d9b" data-url="/courses/course-v1:MITx+15.053x+3T2016/xblock/block-v1:MITx+15.053x+3T2016+type@problem+block@b567c4a43e28451bbc93ce9c3cd23d9b/handler/xmodule_handler" data-problem-score="0.0" data-problem-total-possible="1.0" data-attempts-used="0" data-content=" <h3 class="hd hd-3 problem-header" id="b567c4a43e28451bbc93ce9c3cd23d9b-problem-title" aria-describedby="block-v1:MITx+15.053x+3T2016+type@problem+block@b567c4a43e28451bbc93ce9c3cd23d9b-problem-progress" tabindex="-1"> PART F </h3> <div class="problem-progress" id="block-v1:MITx+15.053x+3T2016+type@problem+block@b567c4a43e28451bbc93ce9c3cd23d9b-problem-progress"></div> <div class="problem"> <div> <p>Add three binary variables $w_6, w_7, $ and $ w_8 $ and two constraints that ensures that $x_6 = 13$ or $39$ or $88$. Select the two correct constraints from below.</p> <div class="wrapper-problem-response" tabindex="-1" aria-label="Question 1" role="group"><div class="choicegroup capa_inputtype" id="inputtype_b567c4a43e28451bbc93ce9c3cd23d9b_2_1"> <fieldset aria-describedby="status_b567c4a43e28451bbc93ce9c3cd23d9b_2_1"> <div class="field"> <input type="checkbox" name="input_b567c4a43e28451bbc93ce9c3cd23d9b_2_1[]" id="input_b567c4a43e28451bbc93ce9c3cd23d9b_2_1_choice_0" class="field-input input-checkbox" value="choice_0"/><label id="b567c4a43e28451bbc93ce9c3cd23d9b_2_1-choice_0-label" for="input_b567c4a43e28451bbc93ce9c3cd23d9b_2_1_choice_0" class="response-label field-label label-inline" aria-describedby="status_b567c4a43e28451bbc93ce9c3cd23d9b_2_1"> $ x_6 = 13w_6 &#8211; 39w_7 &#8211; 88w_8 $ </label> </div> <div class="field"> <input type="checkbox" name="input_b567c4a43e28451bbc93ce9c3cd23d9b_2_1[]" id="input_b567c4a43e28451bbc93ce9c3cd23d9b_2_1_choice_1" class="field-input input-checkbox" value="choice_1"/><label id="b567c4a43e28451bbc93ce9c3cd23d9b_2_1-choice_1-label" for="input_b567c4a43e28451bbc93ce9c3cd23d9b_2_1_choice_1" class="response-label field-label label-inline" aria-describedby="status_b567c4a43e28451bbc93ce9c3cd23d9b_2_1"> $ x_6 = 13w_6 + 39w_7 + 88w_8 $ </label> </div> <div class="field"> <input type="checkbox" name="input_b567c4a43e28451bbc93ce9c3cd23d9b_2_1[]" id="input_b567c4a43e28451bbc93ce9c3cd23d9b_2_1_choice_2" class="field-input input-checkbox" value="choice_2"/><label id="b567c4a43e28451bbc93ce9c3cd23d9b_2_1-choice_2-label" for="input_b567c4a43e28451bbc93ce9c3cd23d9b_2_1_choice_2" class="response-label field-label label-inline" aria-describedby="status_b567c4a43e28451bbc93ce9c3cd23d9b_2_1"> $ w_6 + w_7 + w_8 \ge 1, w_6, w_7, w_8 \in \{0, 1\} $ </label> </div> <div class="field"> <input type="checkbox" name="input_b567c4a43e28451bbc93ce9c3cd23d9b_2_1[]" id="input_b567c4a43e28451bbc93ce9c3cd23d9b_2_1_choice_3" class="field-input input-checkbox" value="choice_3"/><label id="b567c4a43e28451bbc93ce9c3cd23d9b_2_1-choice_3-label" for="input_b567c4a43e28451bbc93ce9c3cd23d9b_2_1_choice_3" class="response-label field-label label-inline" aria-describedby="status_b567c4a43e28451bbc93ce9c3cd23d9b_2_1"> $ w_6 + w_7 + w_8 \le 1, w_6, w_7, w_8 \in \{0, 1\}$ </label> </div> <div class="field"> <input type="checkbox" name="input_b567c4a43e28451bbc93ce9c3cd23d9b_2_1[]" id="input_b567c4a43e28451bbc93ce9c3cd23d9b_2_1_choice_4" class="field-input input-checkbox" value="choice_4"/><label id="b567c4a43e28451bbc93ce9c3cd23d9b_2_1-choice_4-label" for="input_b567c4a43e28451bbc93ce9c3cd23d9b_2_1_choice_4" class="response-label field-label label-inline" aria-describedby="status_b567c4a43e28451bbc93ce9c3cd23d9b_2_1"> $ w_6 + w_7 + w_8 = 1, w_6, w_7, w_8 \in \{0, 1\} $ </label> </div> <span id="answer_b567c4a43e28451bbc93ce9c3cd23d9b_2_1"/> </fieldset> <div class="indicator-container"> <span class="status unanswered" id="status_b567c4a43e28451bbc93ce9c3cd23d9b_2_1" data-tooltip="Not yet answered."> <span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/> </span> </div> </div></div> <div class="solution-span"> <span id="solution_b567c4a43e28451bbc93ce9c3cd23d9b_solution_1"/> </div></div> <div class="action"> <input type="hidden" name="problem_id" value="PART F" /> <div class="submit-attempt-container"> <button type="button" class="submit btn-brand" data-submitting="Submitting" data-value="Submit" data-should-enable-submit-button="True" aria-describedby="submission_feedback_b567c4a43e28451bbc93ce9c3cd23d9b" > <span class="submit-label">Submit</span> </button> <div class="submission-feedback" id="submission_feedback_b567c4a43e28451bbc93ce9c3cd23d9b"> <span class="sr">Some problems have options such as save, reset, hints, or show answer. These options follow the Submit button.</span> </div> </div> <div class="problem-action-buttons-wrapper"> </div> </div> <div class="notification warning notification-gentle-alert is-hidden" tabindex="-1"> <span class="icon fa fa-exclamation-circle" aria-hidden="true"></span> <span class="notification-message" aria-describedby="b567c4a43e28451bbc93ce9c3cd23d9b-problem-title"> </span> <div class="notification-btn-wrapper"> <button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button> </div> </div> <div class="notification warning notification-save is-hidden" tabindex="-1"> <span class="icon fa fa-save" aria-hidden="true"></span> <span class="notification-message" aria-describedby="b567c4a43e28451bbc93ce9c3cd23d9b-problem-title">None </span> <div class="notification-btn-wrapper"> <button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button> </div> </div> <div class="notification general notification-show-answer is-hidden" tabindex="-1"> <span class="icon fa fa-info-circle" aria-hidden="true"></span> <span class="notification-message" aria-describedby="b567c4a43e28451bbc93ce9c3cd23d9b-problem-title">Answers are displayed within the problem </span> <div class="notification-btn-wrapper"> <button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button> </div> </div> </div> " data-graded="True"> <p class="loading-spinner"> <i class="fa fa-spinner fa-pulse fa-2x fa-fw"></i> <span class="sr">Loading…</span> </p> </div> </div> </div> </div> </div>

<div class="xblock xblock-public_view xblock-public_view-vertical" data-usage-id="block-v1:MITx+15.053x+3T2016+type@vertical+block@f5f4f176984b469c9a0cf4810d2ae939" data-block-type="vertical" data-graded="True" data-course-id="course-v1:MITx+15.053x+3T2016" data-has-score="False" data-request-token="a7efc0db852911ef8f57023e4242adeb" data-init="VerticalStudentView" data-runtime-class="LmsRuntime" data-runtime-version="1"> <h2 class="hd hd-2 unit-title">Problem 2</h2> <div class="vert-mod"> <div class="vert vert-0" data-id="block-v1:MITx+15.053x+3T2016+type@problem+block@da41632336294aa5ae2cf72dab8e04cb"> <div class="xblock xblock-public_view xblock-public_view-problem xmodule_display xmodule_ProblemBlock" data-usage-id="block-v1:MITx+15.053x+3T2016+type@problem+block@da41632336294aa5ae2cf72dab8e04cb" data-block-type="problem" data-graded="True" data-course-id="course-v1:MITx+15.053x+3T2016" data-has-score="True" data-request-token="a7efc0db852911ef8f57023e4242adeb" data-init="XBlockToXModuleShim" data-runtime-class="LmsRuntime" data-runtime-version="1"> <script type="json/xblock-args" class="xblock-json-init-args"> {"xmodule-type": "Problem"} </script> <div id="problem_da41632336294aa5ae2cf72dab8e04cb" class="problems-wrapper" role="group" aria-labelledby="da41632336294aa5ae2cf72dab8e04cb-problem-title" data-problem-id="block-v1:MITx+15.053x+3T2016+type@problem+block@da41632336294aa5ae2cf72dab8e04cb" data-url="/courses/course-v1:MITx+15.053x+3T2016/xblock/block-v1:MITx+15.053x+3T2016+type@problem+block@da41632336294aa5ae2cf72dab8e04cb/handler/xmodule_handler" data-problem-score="0.0" data-problem-total-possible="1.0" data-attempts-used="0" data-content=" <h3 class="hd hd-3 problem-header" id="da41632336294aa5ae2cf72dab8e04cb-problem-title" aria-describedby="block-v1:MITx+15.053x+3T2016+type@problem+block@da41632336294aa5ae2cf72dab8e04cb-problem-progress" tabindex="-1"> PART A </h3> <div class="problem-progress" id="block-v1:MITx+15.053x+3T2016+type@problem+block@da41632336294aa5ae2cf72dab8e04cb-problem-progress"></div> <div class="problem"> <div> <p>Integer Programming Formulation, eHarmony</p> <p>eHarmony is an online dating site focused on long term relationships. It takes a scientific approach to love and marriage. About nearly 4% of US marriages in 2012 are a result of eHarmony. The company has generated over $1 billion in cumulative revenue from 2000, the year it was founded. Unlike other online dating websites, eHarmony does not have users browse others' profiles. Instead, eHarmony computes a compatibility score between two people and uses optimization algorithms to determine their users' best matches. In this problem, we are going to see how eHamony uses integer programming to find good matches. The compatibility scores in the table below indicates how compatible a match is. A higher number indicates that the compatibility is greater.</p> <center> <table> <tbody> <tr> <th scope="col" style="text-align: center; border: 1px solid black; padding: 10px;"/> <th scope="col" style="text-align: center; border: 1px solid black; padding: 10px;">Woman 1</th> <th scope="col" style="text-align: center; border: 1px solid black; padding: 10px;">Woman 2</th> <th scope="col" style="text-align: center; border: 1px solid black; padding: 10px;">Woman 3</th> </tr> <tr> <th scope="row" style="text-align: center; border: 1px solid black; padding: 10px;">Man 1</th> <td style="text-align: center; border: 1px solid black; padding: 10px;">1</td> <td style="text-align: center; border: 1px solid black; padding: 10px;">3</td> <td style="text-align: center; border: 1px solid black; padding: 10px;">5</td> </tr> <tr> <th scope="row" style="text-align: center; border: 1px solid black; padding: 10px;">Man 2</th> <td style="text-align: center; border: 1px solid black; padding: 10px;">4</td> <td style="text-align: center; border: 1px solid black; padding: 10px;">2</td> <td style="text-align: center; border: 1px solid black; padding: 10px;">2</td> </tr> <tr> <th scope="row" style="text-align: center; border: 1px solid black; padding: 10px;">Man 3</th> <td style="text-align: center; border: 1px solid black; padding: 10px;">1</td> <td style="text-align: center; border: 1px solid black; padding: 10px;">5</td> <td style="text-align: center; border: 1px solid black; padding: 10px;">3</td> </tr> </tbody> <caption>Table 1: Compatibility Scores</caption> </table> </center> <p/> <p>Decision variables:</p> <ul> <li>$x_{ij} \in \{0,1\}$, indicator variable. $ x_{ij}=1 $ is man $i$ is matched with woman $j$; 0 if man $i$ is not matched with woman $j$ </li> </ul> <p>Objective Function:</p> <ul> <li>$x_{11} + 3x_{12} + 5x_{13} + 4x_{21} + 2x_{22} + 2x_{23} + x_{31} + 5x_{32} + 3x_{33}$</li> </ul> <p>Should the objective function be maximized or minimized?</p> <div class="wrapper-problem-response" tabindex="-1" aria-label="Question 1" role="group"><div class="choicegroup capa_inputtype" id="inputtype_da41632336294aa5ae2cf72dab8e04cb_2_1"> <fieldset aria-describedby="status_da41632336294aa5ae2cf72dab8e04cb_2_1"> <div class="field"> <input type="radio" name="input_da41632336294aa5ae2cf72dab8e04cb_2_1" id="input_da41632336294aa5ae2cf72dab8e04cb_2_1_choice_1a#AA" class="field-input input-radio" value="choice_1a#AA"/><label id="da41632336294aa5ae2cf72dab8e04cb_2_1-choice_1a#AA-label" for="input_da41632336294aa5ae2cf72dab8e04cb_2_1_choice_1a#AA" class="response-label field-label label-inline" aria-describedby="status_da41632336294aa5ae2cf72dab8e04cb_2_1"> MAX </label> </div> <div class="field"> <input type="radio" name="input_da41632336294aa5ae2cf72dab8e04cb_2_1" id="input_da41632336294aa5ae2cf72dab8e04cb_2_1_choice_1a#BB" class="field-input input-radio" value="choice_1a#BB"/><label id="da41632336294aa5ae2cf72dab8e04cb_2_1-choice_1a#BB-label" for="input_da41632336294aa5ae2cf72dab8e04cb_2_1_choice_1a#BB" class="response-label field-label label-inline" aria-describedby="status_da41632336294aa5ae2cf72dab8e04cb_2_1"> MIN </label> </div> <span id="answer_da41632336294aa5ae2cf72dab8e04cb_2_1"/> </fieldset> <div class="indicator-container"> <span class="status unanswered" id="status_da41632336294aa5ae2cf72dab8e04cb_2_1" data-tooltip="Not yet answered."> <span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/> </span> </div> </div></div> <div class="solution-span"> <span id="solution_da41632336294aa5ae2cf72dab8e04cb_solution_1"/> </div></div> <div class="action"> <input type="hidden" name="problem_id" value="PART A" /> <div class="submit-attempt-container"> <button type="button" class="submit btn-brand" data-submitting="Submitting" data-value="Submit" data-should-enable-submit-button="True" aria-describedby="submission_feedback_da41632336294aa5ae2cf72dab8e04cb" > <span class="submit-label">Submit</span> </button> <div class="submission-feedback" id="submission_feedback_da41632336294aa5ae2cf72dab8e04cb"> <span class="sr">Some problems have options such as save, reset, hints, or show answer. These options follow the Submit button.</span> </div> </div> <div class="problem-action-buttons-wrapper"> </div> </div> <div class="notification warning notification-gentle-alert is-hidden" tabindex="-1"> <span class="icon fa fa-exclamation-circle" aria-hidden="true"></span> <span class="notification-message" aria-describedby="da41632336294aa5ae2cf72dab8e04cb-problem-title"> </span> <div class="notification-btn-wrapper"> <button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button> </div> </div> <div class="notification warning notification-save is-hidden" tabindex="-1"> <span class="icon fa fa-save" aria-hidden="true"></span> <span class="notification-message" aria-describedby="da41632336294aa5ae2cf72dab8e04cb-problem-title">None </span> <div class="notification-btn-wrapper"> <button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button> </div> </div> <div class="notification general notification-show-answer is-hidden" tabindex="-1"> <span class="icon fa fa-info-circle" aria-hidden="true"></span> <span class="notification-message" aria-describedby="da41632336294aa5ae2cf72dab8e04cb-problem-title">Answers are displayed within the problem </span> <div class="notification-btn-wrapper"> <button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button> </div> </div> </div> " data-graded="True"> <p class="loading-spinner"> <i class="fa fa-spinner fa-pulse fa-2x fa-fw"></i> <span class="sr">Loading…</span> </p> </div> </div> </div> <div class="vert vert-1" data-id="block-v1:MITx+15.053x+3T2016+type@problem+block@4201fe74bbbd4643be95ce498ee86729"> <div class="xblock xblock-public_view xblock-public_view-problem xmodule_display xmodule_ProblemBlock" data-usage-id="block-v1:MITx+15.053x+3T2016+type@problem+block@4201fe74bbbd4643be95ce498ee86729" data-block-type="problem" data-graded="True" data-course-id="course-v1:MITx+15.053x+3T2016" data-has-score="True" data-request-token="a7efc0db852911ef8f57023e4242adeb" data-init="XBlockToXModuleShim" data-runtime-class="LmsRuntime" data-runtime-version="1"> <script type="json/xblock-args" class="xblock-json-init-args"> {"xmodule-type": "Problem"} </script> <div id="problem_4201fe74bbbd4643be95ce498ee86729" class="problems-wrapper" role="group" aria-labelledby="4201fe74bbbd4643be95ce498ee86729-problem-title" data-problem-id="block-v1:MITx+15.053x+3T2016+type@problem+block@4201fe74bbbd4643be95ce498ee86729" data-url="/courses/course-v1:MITx+15.053x+3T2016/xblock/block-v1:MITx+15.053x+3T2016+type@problem+block@4201fe74bbbd4643be95ce498ee86729/handler/xmodule_handler" data-problem-score="0.0" data-problem-total-possible="1.0" data-attempts-used="0" data-content=" <h3 class="hd hd-3 problem-header" id="4201fe74bbbd4643be95ce498ee86729-problem-title" aria-describedby="block-v1:MITx+15.053x+3T2016+type@problem+block@4201fe74bbbd4643be95ce498ee86729-problem-progress" tabindex="-1"> PART B </h3> <div class="problem-progress" id="block-v1:MITx+15.053x+3T2016+type@problem+block@4201fe74bbbd4643be95ce498ee86729-problem-progress"></div> <div class="problem"> <div> <p>Which of the following constraints corresponds to the constraint "Each man should be matched to exactly one woman"? There are three constraints that should be selected.</p> <p>Check all that apply</p> <div class="wrapper-problem-response" tabindex="-1" aria-label="Question 1" role="group"><div class="choicegroup capa_inputtype" id="inputtype_4201fe74bbbd4643be95ce498ee86729_2_1"> <fieldset aria-describedby="status_4201fe74bbbd4643be95ce498ee86729_2_1"> <div class="field"> <input type="checkbox" name="input_4201fe74bbbd4643be95ce498ee86729_2_1[]" id="input_4201fe74bbbd4643be95ce498ee86729_2_1_choice_0" class="field-input input-checkbox" value="choice_0"/><label id="4201fe74bbbd4643be95ce498ee86729_2_1-choice_0-label" for="input_4201fe74bbbd4643be95ce498ee86729_2_1_choice_0" class="response-label field-label label-inline" aria-describedby="status_4201fe74bbbd4643be95ce498ee86729_2_1"> $x_{11} + x_{12} + x_{13} = 1$. </label> </div> <div class="field"> <input type="checkbox" name="input_4201fe74bbbd4643be95ce498ee86729_2_1[]" id="input_4201fe74bbbd4643be95ce498ee86729_2_1_choice_1" class="field-input input-checkbox" value="choice_1"/><label id="4201fe74bbbd4643be95ce498ee86729_2_1-choice_1-label" for="input_4201fe74bbbd4643be95ce498ee86729_2_1_choice_1" class="response-label field-label label-inline" aria-describedby="status_4201fe74bbbd4643be95ce498ee86729_2_1"> $x_{21} + x_{22} + x_{23} = 1$ </label> </div> <div class="field"> <input type="checkbox" name="input_4201fe74bbbd4643be95ce498ee86729_2_1[]" id="input_4201fe74bbbd4643be95ce498ee86729_2_1_choice_2" class="field-input input-checkbox" value="choice_2"/><label id="4201fe74bbbd4643be95ce498ee86729_2_1-choice_2-label" for="input_4201fe74bbbd4643be95ce498ee86729_2_1_choice_2" class="response-label field-label label-inline" aria-describedby="status_4201fe74bbbd4643be95ce498ee86729_2_1"> $x_{31} + x_{32} + x_{33} = 1$ </label> </div> <div class="field"> <input type="checkbox" name="input_4201fe74bbbd4643be95ce498ee86729_2_1[]" id="input_4201fe74bbbd4643be95ce498ee86729_2_1_choice_3" class="field-input input-checkbox" value="choice_3"/><label id="4201fe74bbbd4643be95ce498ee86729_2_1-choice_3-label" for="input_4201fe74bbbd4643be95ce498ee86729_2_1_choice_3" class="response-label field-label label-inline" aria-describedby="status_4201fe74bbbd4643be95ce498ee86729_2_1"> $x_{11} + x_{21} + x_{31} = 1$ </label> </div> <div class="field"> <input type="checkbox" name="input_4201fe74bbbd4643be95ce498ee86729_2_1[]" id="input_4201fe74bbbd4643be95ce498ee86729_2_1_choice_4" class="field-input input-checkbox" value="choice_4"/><label id="4201fe74bbbd4643be95ce498ee86729_2_1-choice_4-label" for="input_4201fe74bbbd4643be95ce498ee86729_2_1_choice_4" class="response-label field-label label-inline" aria-describedby="status_4201fe74bbbd4643be95ce498ee86729_2_1"> $x_{12} + x_{22} + x_{32} = 1$ </label> </div> <div class="field"> <input type="checkbox" name="input_4201fe74bbbd4643be95ce498ee86729_2_1[]" id="input_4201fe74bbbd4643be95ce498ee86729_2_1_choice_5" class="field-input input-checkbox" value="choice_5"/><label id="4201fe74bbbd4643be95ce498ee86729_2_1-choice_5-label" for="input_4201fe74bbbd4643be95ce498ee86729_2_1_choice_5" class="response-label field-label label-inline" aria-describedby="status_4201fe74bbbd4643be95ce498ee86729_2_1"> $x_{13} + x_{23} + x_{33} = 1$ </label> </div> <span id="answer_4201fe74bbbd4643be95ce498ee86729_2_1"/> </fieldset> <div class="indicator-container"> <span class="status unanswered" id="status_4201fe74bbbd4643be95ce498ee86729_2_1" data-tooltip="Not yet answered."> <span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/> </span> </div> </div></div> <div class="solution-span"> <span id="solution_4201fe74bbbd4643be95ce498ee86729_solution_1"/> </div></div> <div class="action"> <input type="hidden" name="problem_id" value="PART B" /> <div class="submit-attempt-container"> <button type="button" class="submit btn-brand" data-submitting="Submitting" data-value="Submit" data-should-enable-submit-button="True" aria-describedby="submission_feedback_4201fe74bbbd4643be95ce498ee86729" > <span class="submit-label">Submit</span> </button> <div class="submission-feedback" id="submission_feedback_4201fe74bbbd4643be95ce498ee86729"> <span class="sr">Some problems have options such as save, reset, hints, or show answer. These options follow the Submit button.</span> </div> </div> <div class="problem-action-buttons-wrapper"> </div> </div> <div class="notification warning notification-gentle-alert is-hidden" tabindex="-1"> <span class="icon fa fa-exclamation-circle" aria-hidden="true"></span> <span class="notification-message" aria-describedby="4201fe74bbbd4643be95ce498ee86729-problem-title"> </span> <div class="notification-btn-wrapper"> <button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button> </div> </div> <div class="notification warning notification-save is-hidden" tabindex="-1"> <span class="icon fa fa-save" aria-hidden="true"></span> <span class="notification-message" aria-describedby="4201fe74bbbd4643be95ce498ee86729-problem-title">None </span> <div class="notification-btn-wrapper"> <button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button> </div> </div> <div class="notification general notification-show-answer is-hidden" tabindex="-1"> <span class="icon fa fa-info-circle" aria-hidden="true"></span> <span class="notification-message" aria-describedby="4201fe74bbbd4643be95ce498ee86729-problem-title">Answers are displayed within the problem </span> <div class="notification-btn-wrapper"> <button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button> </div> </div> </div> " data-graded="True"> <p class="loading-spinner"> <i class="fa fa-spinner fa-pulse fa-2x fa-fw"></i> <span class="sr">Loading…</span> </p> </div> </div> </div> <div class="vert vert-2" data-id="block-v1:MITx+15.053x+3T2016+type@problem+block@e16c89d34b004117b945393d48ad6cec"> <div class="xblock xblock-public_view xblock-public_view-problem xmodule_display xmodule_ProblemBlock" data-usage-id="block-v1:MITx+15.053x+3T2016+type@problem+block@e16c89d34b004117b945393d48ad6cec" data-block-type="problem" data-graded="True" data-course-id="course-v1:MITx+15.053x+3T2016" data-has-score="True" data-request-token="a7efc0db852911ef8f57023e4242adeb" data-init="XBlockToXModuleShim" data-runtime-class="LmsRuntime" data-runtime-version="1"> <script type="json/xblock-args" class="xblock-json-init-args"> {"xmodule-type": "Problem"} </script> <div id="problem_e16c89d34b004117b945393d48ad6cec" class="problems-wrapper" role="group" aria-labelledby="e16c89d34b004117b945393d48ad6cec-problem-title" data-problem-id="block-v1:MITx+15.053x+3T2016+type@problem+block@e16c89d34b004117b945393d48ad6cec" data-url="/courses/course-v1:MITx+15.053x+3T2016/xblock/block-v1:MITx+15.053x+3T2016+type@problem+block@e16c89d34b004117b945393d48ad6cec/handler/xmodule_handler" data-problem-score="0.0" data-problem-total-possible="1.0" data-attempts-used="0" data-content=" <h3 class="hd hd-3 problem-header" id="e16c89d34b004117b945393d48ad6cec-problem-title" aria-describedby="block-v1:MITx+15.053x+3T2016+type@problem+block@e16c89d34b004117b945393d48ad6cec-problem-progress" tabindex="-1"> PART C </h3> <div class="problem-progress" id="block-v1:MITx+15.053x+3T2016+type@problem+block@e16c89d34b004117b945393d48ad6cec-problem-progress"></div> <div class="problem"> <div> <p>What is the female assignment constraint "Each woman should be matched to exactly one man"?</p> <p>Check all that apply</p> <div class="wrapper-problem-response" tabindex="-1" aria-label="Question 1" role="group"><div class="choicegroup capa_inputtype" id="inputtype_e16c89d34b004117b945393d48ad6cec_2_1"> <fieldset aria-describedby="status_e16c89d34b004117b945393d48ad6cec_2_1"> <div class="field"> <input type="checkbox" name="input_e16c89d34b004117b945393d48ad6cec_2_1[]" id="input_e16c89d34b004117b945393d48ad6cec_2_1_choice_0" class="field-input input-checkbox" value="choice_0"/><label id="e16c89d34b004117b945393d48ad6cec_2_1-choice_0-label" for="input_e16c89d34b004117b945393d48ad6cec_2_1_choice_0" class="response-label field-label label-inline" aria-describedby="status_e16c89d34b004117b945393d48ad6cec_2_1"> $x_{11} + x_{12} + x_{13} = 1$ </label> </div> <div class="field"> <input type="checkbox" name="input_e16c89d34b004117b945393d48ad6cec_2_1[]" id="input_e16c89d34b004117b945393d48ad6cec_2_1_choice_1" class="field-input input-checkbox" value="choice_1"/><label id="e16c89d34b004117b945393d48ad6cec_2_1-choice_1-label" for="input_e16c89d34b004117b945393d48ad6cec_2_1_choice_1" class="response-label field-label label-inline" aria-describedby="status_e16c89d34b004117b945393d48ad6cec_2_1"> $x_{21} + x_{22} + x_{23} = 1$ </label> </div> <div class="field"> <input type="checkbox" name="input_e16c89d34b004117b945393d48ad6cec_2_1[]" id="input_e16c89d34b004117b945393d48ad6cec_2_1_choice_2" class="field-input input-checkbox" value="choice_2"/><label id="e16c89d34b004117b945393d48ad6cec_2_1-choice_2-label" for="input_e16c89d34b004117b945393d48ad6cec_2_1_choice_2" class="response-label field-label label-inline" aria-describedby="status_e16c89d34b004117b945393d48ad6cec_2_1"> $x_{31} + x_{32} + x_{33} = 1$ </label> </div> <div class="field"> <input type="checkbox" name="input_e16c89d34b004117b945393d48ad6cec_2_1[]" id="input_e16c89d34b004117b945393d48ad6cec_2_1_choice_3" class="field-input input-checkbox" value="choice_3"/><label id="e16c89d34b004117b945393d48ad6cec_2_1-choice_3-label" for="input_e16c89d34b004117b945393d48ad6cec_2_1_choice_3" class="response-label field-label label-inline" aria-describedby="status_e16c89d34b004117b945393d48ad6cec_2_1"> $x_{11} + x_{21} + x_{31} = 1$ </label> </div> <div class="field"> <input type="checkbox" name="input_e16c89d34b004117b945393d48ad6cec_2_1[]" id="input_e16c89d34b004117b945393d48ad6cec_2_1_choice_4" class="field-input input-checkbox" value="choice_4"/><label id="e16c89d34b004117b945393d48ad6cec_2_1-choice_4-label" for="input_e16c89d34b004117b945393d48ad6cec_2_1_choice_4" class="response-label field-label label-inline" aria-describedby="status_e16c89d34b004117b945393d48ad6cec_2_1"> $x_{12} + x_{22} + x_{32} = 1$ </label> </div> <div class="field"> <input type="checkbox" name="input_e16c89d34b004117b945393d48ad6cec_2_1[]" id="input_e16c89d34b004117b945393d48ad6cec_2_1_choice_5" class="field-input input-checkbox" value="choice_5"/><label id="e16c89d34b004117b945393d48ad6cec_2_1-choice_5-label" for="input_e16c89d34b004117b945393d48ad6cec_2_1_choice_5" class="response-label field-label label-inline" aria-describedby="status_e16c89d34b004117b945393d48ad6cec_2_1"> $x_{13} + x_{23} + x_{33} = 1$ </label> </div> <span id="answer_e16c89d34b004117b945393d48ad6cec_2_1"/> </fieldset> <div class="indicator-container"> <span class="status unanswered" id="status_e16c89d34b004117b945393d48ad6cec_2_1" data-tooltip="Not yet answered."> <span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/> </span> </div> </div></div> <div class="solution-span"> <span id="solution_e16c89d34b004117b945393d48ad6cec_solution_1"/> </div></div> <div class="action"> <input type="hidden" name="problem_id" value="PART C" /> <div class="submit-attempt-container"> <button type="button" class="submit btn-brand" data-submitting="Submitting" data-value="Submit" data-should-enable-submit-button="True" aria-describedby="submission_feedback_e16c89d34b004117b945393d48ad6cec" > <span class="submit-label">Submit</span> </button> <div class="submission-feedback" id="submission_feedback_e16c89d34b004117b945393d48ad6cec"> <span class="sr">Some problems have options such as save, reset, hints, or show answer. These options follow the Submit button.</span> </div> </div> <div class="problem-action-buttons-wrapper"> </div> </div> <div class="notification warning notification-gentle-alert is-hidden" tabindex="-1"> <span class="icon fa fa-exclamation-circle" aria-hidden="true"></span> <span class="notification-message" aria-describedby="e16c89d34b004117b945393d48ad6cec-problem-title"> </span> <div class="notification-btn-wrapper"> <button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button> </div> </div> <div class="notification warning notification-save is-hidden" tabindex="-1"> <span class="icon fa fa-save" aria-hidden="true"></span> <span class="notification-message" aria-describedby="e16c89d34b004117b945393d48ad6cec-problem-title">None </span> <div class="notification-btn-wrapper"> <button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button> </div> </div> <div class="notification general notification-show-answer is-hidden" tabindex="-1"> <span class="icon fa fa-info-circle" aria-hidden="true"></span> <span class="notification-message" aria-describedby="e16c89d34b004117b945393d48ad6cec-problem-title">Answers are displayed within the problem </span> <div class="notification-btn-wrapper"> <button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button> </div> </div> </div> " data-graded="True"> <p class="loading-spinner"> <i class="fa fa-spinner fa-pulse fa-2x fa-fw"></i> <span class="sr">Loading…</span> </p> </div> </div> </div> <div class="vert vert-3" data-id="block-v1:MITx+15.053x+3T2016+type@problem+block@bb3a3774aaef42ef841ddb9489ed7040"> <div class="xblock xblock-public_view xblock-public_view-problem xmodule_display xmodule_ProblemBlock" data-usage-id="block-v1:MITx+15.053x+3T2016+type@problem+block@bb3a3774aaef42ef841ddb9489ed7040" data-block-type="problem" data-graded="True" data-course-id="course-v1:MITx+15.053x+3T2016" data-has-score="True" data-request-token="a7efc0db852911ef8f57023e4242adeb" data-init="XBlockToXModuleShim" data-runtime-class="LmsRuntime" data-runtime-version="1"> <script type="json/xblock-args" class="xblock-json-init-args"> {"xmodule-type": "Problem"} </script> <div id="problem_bb3a3774aaef42ef841ddb9489ed7040" class="problems-wrapper" role="group" aria-labelledby="bb3a3774aaef42ef841ddb9489ed7040-problem-title" data-problem-id="block-v1:MITx+15.053x+3T2016+type@problem+block@bb3a3774aaef42ef841ddb9489ed7040" data-url="/courses/course-v1:MITx+15.053x+3T2016/xblock/block-v1:MITx+15.053x+3T2016+type@problem+block@bb3a3774aaef42ef841ddb9489ed7040/handler/xmodule_handler" data-problem-score="0.0" data-problem-total-possible="1.0" data-attempts-used="0" data-content=" <h3 class="hd hd-3 problem-header" id="bb3a3774aaef42ef841ddb9489ed7040-problem-title" aria-describedby="block-v1:MITx+15.053x+3T2016+type@problem+block@bb3a3774aaef42ef841ddb9489ed7040-problem-progress" tabindex="-1"> PART D </h3> <div class="problem-progress" id="block-v1:MITx+15.053x+3T2016+type@problem+block@bb3a3774aaef42ef841ddb9489ed7040-problem-progress"></div> <div class="problem"> <div> <p>Solve the integer program above. What is the optimal objective function value?</p> <div class="wrapper-problem-response" tabindex="-1" aria-label="Question 1" role="group"><div id="formulaequationinput_bb3a3774aaef42ef841ddb9489ed7040_2_1" class="inputtype formulaequationinput"> <div class="unanswered"> <input type="text" name="input_bb3a3774aaef42ef841ddb9489ed7040_2_1" id="input_bb3a3774aaef42ef841ddb9489ed7040_2_1" data-input-id="bb3a3774aaef42ef841ddb9489ed7040_2_1" value="" aria-describedby="status_bb3a3774aaef42ef841ddb9489ed7040_2_1" size="20"/> <span class="trailing_text" id="trailing_text_bb3a3774aaef42ef841ddb9489ed7040_2_1"/> <span class="status unanswered" id="status_bb3a3774aaef42ef841ddb9489ed7040_2_1" data-tooltip="Not yet answered."> <span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/> </span> <p id="answer_bb3a3774aaef42ef841ddb9489ed7040_2_1" class="answer"/> <div id="input_bb3a3774aaef42ef841ddb9489ed7040_2_1_preview" class="equation">  <img src="/static/images/spinner.bc34f953403f.gif" class="loading" alt="Loading"/> </div> </div> <div class="script_placeholder" data-src="/static/js/capa/src/formula_equation_preview.b1967ab28c31.js"/> </div></div> <div class="solution-span"> <span id="solution_bb3a3774aaef42ef841ddb9489ed7040_solution_1"/> </div></div> <div class="action"> <input type="hidden" name="problem_id" value="PART D" /> <div class="submit-attempt-container"> <button type="button" class="submit btn-brand" data-submitting="Submitting" data-value="Submit" data-should-enable-submit-button="True" aria-describedby="submission_feedback_bb3a3774aaef42ef841ddb9489ed7040" > <span class="submit-label">Submit</span> </button> <div class="submission-feedback" id="submission_feedback_bb3a3774aaef42ef841ddb9489ed7040"> <span class="sr">Some problems have options such as save, reset, hints, or show answer. These options follow the Submit button.</span> </div> </div> <div class="problem-action-buttons-wrapper"> </div> </div> <div class="notification warning notification-gentle-alert is-hidden" tabindex="-1"> <span class="icon fa fa-exclamation-circle" aria-hidden="true"></span> <span class="notification-message" aria-describedby="bb3a3774aaef42ef841ddb9489ed7040-problem-title"> </span> <div class="notification-btn-wrapper"> <button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button> </div> </div> <div class="notification warning notification-save is-hidden" tabindex="-1"> <span class="icon fa fa-save" aria-hidden="true"></span> <span class="notification-message" aria-describedby="bb3a3774aaef42ef841ddb9489ed7040-problem-title">None </span> <div class="notification-btn-wrapper"> <button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button> </div> </div> <div class="notification general notification-show-answer is-hidden" tabindex="-1"> <span class="icon fa fa-info-circle" aria-hidden="true"></span> <span class="notification-message" aria-describedby="bb3a3774aaef42ef841ddb9489ed7040-problem-title">Answers are displayed within the problem </span> <div class="notification-btn-wrapper"> <button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button> </div> </div> </div> " data-graded="True"> <p class="loading-spinner"> <i class="fa fa-spinner fa-pulse fa-2x fa-fw"></i> <span class="sr">Loading…</span> </p> </div> </div> </div> <div class="vert vert-4" data-id="block-v1:MITx+15.053x+3T2016+type@problem+block@26e96c4f8df347ff852259f0d07dfffb"> <div class="xblock xblock-public_view xblock-public_view-problem xmodule_display xmodule_ProblemBlock" data-usage-id="block-v1:MITx+15.053x+3T2016+type@problem+block@26e96c4f8df347ff852259f0d07dfffb" data-block-type="problem" data-graded="True" data-course-id="course-v1:MITx+15.053x+3T2016" data-has-score="True" data-request-token="a7efc0db852911ef8f57023e4242adeb" data-init="XBlockToXModuleShim" data-runtime-class="LmsRuntime" data-runtime-version="1"> <script type="json/xblock-args" class="xblock-json-init-args"> {"xmodule-type": "Problem"} </script> <div id="problem_26e96c4f8df347ff852259f0d07dfffb" class="problems-wrapper" role="group" aria-labelledby="26e96c4f8df347ff852259f0d07dfffb-problem-title" data-problem-id="block-v1:MITx+15.053x+3T2016+type@problem+block@26e96c4f8df347ff852259f0d07dfffb" data-url="/courses/course-v1:MITx+15.053x+3T2016/xblock/block-v1:MITx+15.053x+3T2016+type@problem+block@26e96c4f8df347ff852259f0d07dfffb/handler/xmodule_handler" data-problem-score="0.0" data-problem-total-possible="1.0" data-attempts-used="0" data-content=" <h3 class="hd hd-3 problem-header" id="26e96c4f8df347ff852259f0d07dfffb-problem-title" aria-describedby="block-v1:MITx+15.053x+3T2016+type@problem+block@26e96c4f8df347ff852259f0d07dfffb-problem-progress" tabindex="-1"> PART D II </h3> <div class="problem-progress" id="block-v1:MITx+15.053x+3T2016+type@problem+block@26e96c4f8df347ff852259f0d07dfffb-problem-progress"></div> <div class="problem"> <div> <p>Now solve the problem as a linear program by relaxing the integrality/binary constraints. What is the optimal objective function value now?</p> <div class="wrapper-problem-response" tabindex="-1" aria-label="Question 1" role="group"><div id="formulaequationinput_26e96c4f8df347ff852259f0d07dfffb_2_1" class="inputtype formulaequationinput"> <div class="unanswered"> <input type="text" name="input_26e96c4f8df347ff852259f0d07dfffb_2_1" id="input_26e96c4f8df347ff852259f0d07dfffb_2_1" data-input-id="26e96c4f8df347ff852259f0d07dfffb_2_1" value="" aria-describedby="status_26e96c4f8df347ff852259f0d07dfffb_2_1" size="20"/> <span class="trailing_text" id="trailing_text_26e96c4f8df347ff852259f0d07dfffb_2_1"/> <span class="status unanswered" id="status_26e96c4f8df347ff852259f0d07dfffb_2_1" data-tooltip="Not yet answered."> <span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/> </span> <p id="answer_26e96c4f8df347ff852259f0d07dfffb_2_1" class="answer"/> <div id="input_26e96c4f8df347ff852259f0d07dfffb_2_1_preview" class="equation">  <img src="/static/images/spinner.bc34f953403f.gif" class="loading" alt="Loading"/> </div> </div> <div class="script_placeholder" data-src="/static/js/capa/src/formula_equation_preview.b1967ab28c31.js"/> </div></div> <div class="solution-span"> <span id="solution_26e96c4f8df347ff852259f0d07dfffb_solution_1"/> </div></div> <div class="action"> <input type="hidden" name="problem_id" value="PART D II" /> <div class="submit-attempt-container"> <button type="button" class="submit btn-brand" data-submitting="Submitting" data-value="Submit" data-should-enable-submit-button="True" aria-describedby="submission_feedback_26e96c4f8df347ff852259f0d07dfffb" > <span class="submit-label">Submit</span> </button> <div class="submission-feedback" id="submission_feedback_26e96c4f8df347ff852259f0d07dfffb"> <span class="sr">Some problems have options such as save, reset, hints, or show answer. These options follow the Submit button.</span> </div> </div> <div class="problem-action-buttons-wrapper"> </div> </div> <div class="notification warning notification-gentle-alert is-hidden" tabindex="-1"> <span class="icon fa fa-exclamation-circle" aria-hidden="true"></span> <span class="notification-message" aria-describedby="26e96c4f8df347ff852259f0d07dfffb-problem-title"> </span> <div class="notification-btn-wrapper"> <button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button> </div> </div> <div class="notification warning notification-save is-hidden" tabindex="-1"> <span class="icon fa fa-save" aria-hidden="true"></span> <span class="notification-message" aria-describedby="26e96c4f8df347ff852259f0d07dfffb-problem-title">None </span> <div class="notification-btn-wrapper"> <button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button> </div> </div> <div class="notification general notification-show-answer is-hidden" tabindex="-1"> <span class="icon fa fa-info-circle" aria-hidden="true"></span> <span class="notification-message" aria-describedby="26e96c4f8df347ff852259f0d07dfffb-problem-title">Answers are displayed within the problem </span> <div class="notification-btn-wrapper"> <button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button> </div> </div> </div> " data-graded="True"> <p class="loading-spinner"> <i class="fa fa-spinner fa-pulse fa-2x fa-fw"></i> <span class="sr">Loading…</span> </p> </div> </div> </div> <div class="vert vert-5" data-id="block-v1:MITx+15.053x+3T2016+type@problem+block@f41a8ae3eb2e4aefa9f3d3c2daaf3009"> <div class="xblock xblock-public_view xblock-public_view-problem xmodule_display xmodule_ProblemBlock" data-usage-id="block-v1:MITx+15.053x+3T2016+type@problem+block@f41a8ae3eb2e4aefa9f3d3c2daaf3009" data-block-type="problem" data-graded="True" data-course-id="course-v1:MITx+15.053x+3T2016" data-has-score="True" data-request-token="a7efc0db852911ef8f57023e4242adeb" data-init="XBlockToXModuleShim" data-runtime-class="LmsRuntime" data-runtime-version="1"> <script type="json/xblock-args" class="xblock-json-init-args"> {"xmodule-type": "Problem"} </script> <div id="problem_f41a8ae3eb2e4aefa9f3d3c2daaf3009" class="problems-wrapper" role="group" aria-labelledby="f41a8ae3eb2e4aefa9f3d3c2daaf3009-problem-title" data-problem-id="block-v1:MITx+15.053x+3T2016+type@problem+block@f41a8ae3eb2e4aefa9f3d3c2daaf3009" data-url="/courses/course-v1:MITx+15.053x+3T2016/xblock/block-v1:MITx+15.053x+3T2016+type@problem+block@f41a8ae3eb2e4aefa9f3d3c2daaf3009/handler/xmodule_handler" data-problem-score="0.0" data-problem-total-possible="1.0" data-attempts-used="0" data-content=" <h3 class="hd hd-3 problem-header" id="f41a8ae3eb2e4aefa9f3d3c2daaf3009-problem-title" aria-describedby="block-v1:MITx+15.053x+3T2016+type@problem+block@f41a8ae3eb2e4aefa9f3d3c2daaf3009-problem-progress" tabindex="-1"> PART E </h3> <div class="problem-progress" id="block-v1:MITx+15.053x+3T2016+type@problem+block@f41a8ae3eb2e4aefa9f3d3c2daaf3009-problem-progress"></div> <div class="problem"> <div> <p>Consider the following two logic constraints eHarmony wants to impose</p> <ul> <li>If man 1 matches woman 3, then man 2 must match woman 2</li> <li>If man 3 matches woman 3, then man 2 must match woman 2</li> </ul> <p>Write two more constraints on top of part (a) to achieve these two logic requirements</p> <div class="wrapper-problem-response" tabindex="-1" aria-label="Question 1" role="group"><div class="choicegroup capa_inputtype" id="inputtype_f41a8ae3eb2e4aefa9f3d3c2daaf3009_2_1"> <fieldset aria-describedby="status_f41a8ae3eb2e4aefa9f3d3c2daaf3009_2_1"> <div class="field"> <input type="radio" name="input_f41a8ae3eb2e4aefa9f3d3c2daaf3009_2_1" id="input_f41a8ae3eb2e4aefa9f3d3c2daaf3009_2_1_choice_0" class="field-input input-radio" value="choice_0"/><label id="f41a8ae3eb2e4aefa9f3d3c2daaf3009_2_1-choice_0-label" for="input_f41a8ae3eb2e4aefa9f3d3c2daaf3009_2_1_choice_0" class="response-label field-label label-inline" aria-describedby="status_f41a8ae3eb2e4aefa9f3d3c2daaf3009_2_1"> $x_{13} \leq x_{22}\\ x_{33} \leq x_{22}$ </label> </div> <div class="field"> <input type="radio" name="input_f41a8ae3eb2e4aefa9f3d3c2daaf3009_2_1" id="input_f41a8ae3eb2e4aefa9f3d3c2daaf3009_2_1_choice_1" class="field-input input-radio" value="choice_1"/><label id="f41a8ae3eb2e4aefa9f3d3c2daaf3009_2_1-choice_1-label" for="input_f41a8ae3eb2e4aefa9f3d3c2daaf3009_2_1_choice_1" class="response-label field-label label-inline" aria-describedby="status_f41a8ae3eb2e4aefa9f3d3c2daaf3009_2_1"> $x_{13} \geq x_{22}\\ x_{33} \geq x_{22}$ </label> </div> <div class="field"> <input type="radio" name="input_f41a8ae3eb2e4aefa9f3d3c2daaf3009_2_1" id="input_f41a8ae3eb2e4aefa9f3d3c2daaf3009_2_1_choice_2" class="field-input input-radio" value="choice_2"/><label id="f41a8ae3eb2e4aefa9f3d3c2daaf3009_2_1-choice_2-label" for="input_f41a8ae3eb2e4aefa9f3d3c2daaf3009_2_1_choice_2" class="response-label field-label label-inline" aria-describedby="status_f41a8ae3eb2e4aefa9f3d3c2daaf3009_2_1"> $x_{13} \geq x_{22}\\ x_{33} \leq x_{22}$ </label> </div> <div class="field"> <input type="radio" name="input_f41a8ae3eb2e4aefa9f3d3c2daaf3009_2_1" id="input_f41a8ae3eb2e4aefa9f3d3c2daaf3009_2_1_choice_3" class="field-input input-radio" value="choice_3"/><label id="f41a8ae3eb2e4aefa9f3d3c2daaf3009_2_1-choice_3-label" for="input_f41a8ae3eb2e4aefa9f3d3c2daaf3009_2_1_choice_3" class="response-label field-label label-inline" aria-describedby="status_f41a8ae3eb2e4aefa9f3d3c2daaf3009_2_1"> $x_{13} \leq x_{22}\\ x_{33} \geq x_{22}$ </label> </div> <div class="field"> <input type="radio" name="input_f41a8ae3eb2e4aefa9f3d3c2daaf3009_2_1" id="input_f41a8ae3eb2e4aefa9f3d3c2daaf3009_2_1_choice_4" class="field-input input-radio" value="choice_4"/><label id="f41a8ae3eb2e4aefa9f3d3c2daaf3009_2_1-choice_4-label" for="input_f41a8ae3eb2e4aefa9f3d3c2daaf3009_2_1_choice_4" class="response-label field-label label-inline" aria-describedby="status_f41a8ae3eb2e4aefa9f3d3c2daaf3009_2_1"> $x_{13} = x_{22}\\ x_{33} = x_{22}$ </label> </div> <span id="answer_f41a8ae3eb2e4aefa9f3d3c2daaf3009_2_1"/> </fieldset> <div class="indicator-container"> <span class="status unanswered" id="status_f41a8ae3eb2e4aefa9f3d3c2daaf3009_2_1" data-tooltip="Not yet answered."> <span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/> </span> </div> </div></div> <div class="solution-span"> <span id="solution_f41a8ae3eb2e4aefa9f3d3c2daaf3009_solution_1"/> </div></div> <div class="action"> <input type="hidden" name="problem_id" value="PART E" /> <div class="submit-attempt-container"> <button type="button" class="submit btn-brand" data-submitting="Submitting" data-value="Submit" data-should-enable-submit-button="True" aria-describedby="submission_feedback_f41a8ae3eb2e4aefa9f3d3c2daaf3009" > <span class="submit-label">Submit</span> </button> <div class="submission-feedback" id="submission_feedback_f41a8ae3eb2e4aefa9f3d3c2daaf3009"> <span class="sr">Some problems have options such as save, reset, hints, or show answer. These options follow the Submit button.</span> </div> </div> <div class="problem-action-buttons-wrapper"> </div> </div> <div class="notification warning notification-gentle-alert is-hidden" tabindex="-1"> <span class="icon fa fa-exclamation-circle" aria-hidden="true"></span> <span class="notification-message" aria-describedby="f41a8ae3eb2e4aefa9f3d3c2daaf3009-problem-title"> </span> <div class="notification-btn-wrapper"> <button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button> </div> </div> <div class="notification warning notification-save is-hidden" tabindex="-1"> <span class="icon fa fa-save" aria-hidden="true"></span> <span class="notification-message" aria-describedby="f41a8ae3eb2e4aefa9f3d3c2daaf3009-problem-title">None </span> <div class="notification-btn-wrapper"> <button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button> </div> </div> <div class="notification general notification-show-answer is-hidden" tabindex="-1"> <span class="icon fa fa-info-circle" aria-hidden="true"></span> <span class="notification-message" aria-describedby="f41a8ae3eb2e4aefa9f3d3c2daaf3009-problem-title">Answers are displayed within the problem </span> <div class="notification-btn-wrapper"> <button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button> </div> </div> </div> " data-graded="True"> <p class="loading-spinner"> <i class="fa fa-spinner fa-pulse fa-2x fa-fw"></i> <span class="sr">Loading…</span> </p> </div> </div> </div> <div class="vert vert-6" data-id="block-v1:MITx+15.053x+3T2016+type@problem+block@a1fbce5839d24b5a8182e6d003f01fbe"> <div class="xblock xblock-public_view xblock-public_view-problem xmodule_display xmodule_ProblemBlock" data-usage-id="block-v1:MITx+15.053x+3T2016+type@problem+block@a1fbce5839d24b5a8182e6d003f01fbe" data-block-type="problem" data-graded="True" data-course-id="course-v1:MITx+15.053x+3T2016" data-has-score="True" data-request-token="a7efc0db852911ef8f57023e4242adeb" data-init="XBlockToXModuleShim" data-runtime-class="LmsRuntime" data-runtime-version="1"> <script type="json/xblock-args" class="xblock-json-init-args"> {"xmodule-type": "Problem"} </script> <div id="problem_a1fbce5839d24b5a8182e6d003f01fbe" class="problems-wrapper" role="group" aria-labelledby="a1fbce5839d24b5a8182e6d003f01fbe-problem-title" data-problem-id="block-v1:MITx+15.053x+3T2016+type@problem+block@a1fbce5839d24b5a8182e6d003f01fbe" data-url="/courses/course-v1:MITx+15.053x+3T2016/xblock/block-v1:MITx+15.053x+3T2016+type@problem+block@a1fbce5839d24b5a8182e6d003f01fbe/handler/xmodule_handler" data-problem-score="0.0" data-problem-total-possible="1.0" data-attempts-used="0" data-content=" <h3 class="hd hd-3 problem-header" id="a1fbce5839d24b5a8182e6d003f01fbe-problem-title" aria-describedby="block-v1:MITx+15.053x+3T2016+type@problem+block@a1fbce5839d24b5a8182e6d003f01fbe-problem-progress" tabindex="-1"> PART F </h3> <div class="problem-progress" id="block-v1:MITx+15.053x+3T2016+type@problem+block@a1fbce5839d24b5a8182e6d003f01fbe-problem-progress"></div> <div class="problem"> <div> <p>Solve the IP, and include the constraints from part E. What is the optimal objective function value?</p> <div class="wrapper-problem-response" tabindex="-1" aria-label="Question 1" role="group"><div id="formulaequationinput_a1fbce5839d24b5a8182e6d003f01fbe_2_1" class="inputtype formulaequationinput"> <div class="unanswered"> <input type="text" name="input_a1fbce5839d24b5a8182e6d003f01fbe_2_1" id="input_a1fbce5839d24b5a8182e6d003f01fbe_2_1" data-input-id="a1fbce5839d24b5a8182e6d003f01fbe_2_1" value="" aria-describedby="status_a1fbce5839d24b5a8182e6d003f01fbe_2_1" size="20"/> <span class="trailing_text" id="trailing_text_a1fbce5839d24b5a8182e6d003f01fbe_2_1"/> <span class="status unanswered" id="status_a1fbce5839d24b5a8182e6d003f01fbe_2_1" data-tooltip="Not yet answered."> <span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/> </span> <p id="answer_a1fbce5839d24b5a8182e6d003f01fbe_2_1" class="answer"/> <div id="input_a1fbce5839d24b5a8182e6d003f01fbe_2_1_preview" class="equation">  <img src="/static/images/spinner.bc34f953403f.gif" class="loading" alt="Loading"/> </div> </div> <div class="script_placeholder" data-src="/static/js/capa/src/formula_equation_preview.b1967ab28c31.js"/> </div></div> <div class="solution-span"> <span id="solution_a1fbce5839d24b5a8182e6d003f01fbe_solution_1"/> </div></div> <div class="action"> <input type="hidden" name="problem_id" value="PART F" /> <div class="submit-attempt-container"> <button type="button" class="submit btn-brand" data-submitting="Submitting" data-value="Submit" data-should-enable-submit-button="True" aria-describedby="submission_feedback_a1fbce5839d24b5a8182e6d003f01fbe" > <span class="submit-label">Submit</span> </button> <div class="submission-feedback" id="submission_feedback_a1fbce5839d24b5a8182e6d003f01fbe"> <span class="sr">Some problems have options such as save, reset, hints, or show answer. These options follow the Submit button.</span> </div> </div> <div class="problem-action-buttons-wrapper"> </div> </div> <div class="notification warning notification-gentle-alert is-hidden" tabindex="-1"> <span class="icon fa fa-exclamation-circle" aria-hidden="true"></span> <span class="notification-message" aria-describedby="a1fbce5839d24b5a8182e6d003f01fbe-problem-title"> </span> <div class="notification-btn-wrapper"> <button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button> </div> </div> <div class="notification warning notification-save is-hidden" tabindex="-1"> <span class="icon fa fa-save" aria-hidden="true"></span> <span class="notification-message" aria-describedby="a1fbce5839d24b5a8182e6d003f01fbe-problem-title">None </span> <div class="notification-btn-wrapper"> <button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button> </div> </div> <div class="notification general notification-show-answer is-hidden" tabindex="-1"> <span class="icon fa fa-info-circle" aria-hidden="true"></span> <span class="notification-message" aria-describedby="a1fbce5839d24b5a8182e6d003f01fbe-problem-title">Answers are displayed within the problem </span> <div class="notification-btn-wrapper"> <button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button> </div> </div> </div> " data-graded="True"> <p class="loading-spinner"> <i class="fa fa-spinner fa-pulse fa-2x fa-fw"></i> <span class="sr">Loading…</span> </p> </div> </div> </div> <div class="vert vert-7" data-id="block-v1:MITx+15.053x+3T2016+type@problem+block@4ed4e868d2264c9d9202885104d8993a"> <div class="xblock xblock-public_view xblock-public_view-problem xmodule_display xmodule_ProblemBlock" data-usage-id="block-v1:MITx+15.053x+3T2016+type@problem+block@4ed4e868d2264c9d9202885104d8993a" data-block-type="problem" data-graded="True" data-course-id="course-v1:MITx+15.053x+3T2016" data-has-score="True" data-request-token="a7efc0db852911ef8f57023e4242adeb" data-init="XBlockToXModuleShim" data-runtime-class="LmsRuntime" data-runtime-version="1"> <script type="json/xblock-args" class="xblock-json-init-args"> {"xmodule-type": "Problem"} </script> <div id="problem_4ed4e868d2264c9d9202885104d8993a" class="problems-wrapper" role="group" aria-labelledby="4ed4e868d2264c9d9202885104d8993a-problem-title" data-problem-id="block-v1:MITx+15.053x+3T2016+type@problem+block@4ed4e868d2264c9d9202885104d8993a" data-url="/courses/course-v1:MITx+15.053x+3T2016/xblock/block-v1:MITx+15.053x+3T2016+type@problem+block@4ed4e868d2264c9d9202885104d8993a/handler/xmodule_handler" data-problem-score="0.0" data-problem-total-possible="1.0" data-attempts-used="0" data-content=" <h3 class="hd hd-3 problem-header" id="4ed4e868d2264c9d9202885104d8993a-problem-title" aria-describedby="block-v1:MITx+15.053x+3T2016+type@problem+block@4ed4e868d2264c9d9202885104d8993a-problem-progress" tabindex="-1"> PART F II </h3> <div class="problem-progress" id="block-v1:MITx+15.053x+3T2016+type@problem+block@4ed4e868d2264c9d9202885104d8993a-problem-progress"></div> <div class="problem"> <div> <p>Solve the linear problem, and include the constraints from part E. Remove the integrality constraints. What is the optimal objective function value?</p> <div class="wrapper-problem-response" tabindex="-1" aria-label="Question 1" role="group"><div id="formulaequationinput_4ed4e868d2264c9d9202885104d8993a_2_1" class="inputtype formulaequationinput"> <div class="unanswered"> <input type="text" name="input_4ed4e868d2264c9d9202885104d8993a_2_1" id="input_4ed4e868d2264c9d9202885104d8993a_2_1" data-input-id="4ed4e868d2264c9d9202885104d8993a_2_1" value="" aria-describedby="status_4ed4e868d2264c9d9202885104d8993a_2_1" size="20"/> <span class="trailing_text" id="trailing_text_4ed4e868d2264c9d9202885104d8993a_2_1"/> <span class="status unanswered" id="status_4ed4e868d2264c9d9202885104d8993a_2_1" data-tooltip="Not yet answered."> <span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/> </span> <p id="answer_4ed4e868d2264c9d9202885104d8993a_2_1" class="answer"/> <div id="input_4ed4e868d2264c9d9202885104d8993a_2_1_preview" class="equation">  <img src="/static/images/spinner.bc34f953403f.gif" class="loading" alt="Loading"/> </div> </div> <div class="script_placeholder" data-src="/static/js/capa/src/formula_equation_preview.b1967ab28c31.js"/> </div></div> <div class="solution-span"> <span id="solution_4ed4e868d2264c9d9202885104d8993a_solution_1"/> </div></div> <div class="action"> <input type="hidden" name="problem_id" value="PART F II" /> <div class="submit-attempt-container"> <button type="button" class="submit btn-brand" data-submitting="Submitting" data-value="Submit" data-should-enable-submit-button="True" aria-describedby="submission_feedback_4ed4e868d2264c9d9202885104d8993a" > <span class="submit-label">Submit</span> </button> <div class="submission-feedback" id="submission_feedback_4ed4e868d2264c9d9202885104d8993a"> <span class="sr">Some problems have options such as save, reset, hints, or show answer. These options follow the Submit button.</span> </div> </div> <div class="problem-action-buttons-wrapper"> </div> </div> <div class="notification warning notification-gentle-alert is-hidden" tabindex="-1"> <span class="icon fa fa-exclamation-circle" aria-hidden="true"></span> <span class="notification-message" aria-describedby="4ed4e868d2264c9d9202885104d8993a-problem-title"> </span> <div class="notification-btn-wrapper"> <button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button> </div> </div> <div class="notification warning notification-save is-hidden" tabindex="-1"> <span class="icon fa fa-save" aria-hidden="true"></span> <span class="notification-message" aria-describedby="4ed4e868d2264c9d9202885104d8993a-problem-title">None </span> <div class="notification-btn-wrapper"> <button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button> </div> </div> <div class="notification general notification-show-answer is-hidden" tabindex="-1"> <span class="icon fa fa-info-circle" aria-hidden="true"></span> <span class="notification-message" aria-describedby="4ed4e868d2264c9d9202885104d8993a-problem-title">Answers are displayed within the problem </span> <div class="notification-btn-wrapper"> <button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button> </div> </div> </div> " data-graded="True"> <p class="loading-spinner"> <i class="fa fa-spinner fa-pulse fa-2x fa-fw"></i> <span class="sr">Loading…</span> </p> </div> </div> </div> <div class="vert vert-8" data-id="block-v1:MITx+15.053x+3T2016+type@problem+block@b2bc692864b749ca8dbd2a6945d26e74"> <div class="xblock xblock-public_view xblock-public_view-problem xmodule_display xmodule_ProblemBlock" data-usage-id="block-v1:MITx+15.053x+3T2016+type@problem+block@b2bc692864b749ca8dbd2a6945d26e74" data-block-type="problem" data-graded="True" data-course-id="course-v1:MITx+15.053x+3T2016" data-has-score="True" data-request-token="a7efc0db852911ef8f57023e4242adeb" data-init="XBlockToXModuleShim" data-runtime-class="LmsRuntime" data-runtime-version="1"> <script type="json/xblock-args" class="xblock-json-init-args"> {"xmodule-type": "Problem"} </script> <div id="problem_b2bc692864b749ca8dbd2a6945d26e74" class="problems-wrapper" role="group" aria-labelledby="b2bc692864b749ca8dbd2a6945d26e74-problem-title" data-problem-id="block-v1:MITx+15.053x+3T2016+type@problem+block@b2bc692864b749ca8dbd2a6945d26e74" data-url="/courses/course-v1:MITx+15.053x+3T2016/xblock/block-v1:MITx+15.053x+3T2016+type@problem+block@b2bc692864b749ca8dbd2a6945d26e74/handler/xmodule_handler" data-problem-score="0.0" data-problem-total-possible="1.0" data-attempts-used="0" data-content=" <h3 class="hd hd-3 problem-header" id="b2bc692864b749ca8dbd2a6945d26e74-problem-title" aria-describedby="block-v1:MITx+15.053x+3T2016+type@problem+block@b2bc692864b749ca8dbd2a6945d26e74-problem-progress" tabindex="-1"> PART G </h3> <div class="problem-progress" id="block-v1:MITx+15.053x+3T2016+type@problem+block@b2bc692864b749ca8dbd2a6945d26e74-problem-progress"></div> <div class="problem"> <div> <p> Suppose we have n men and n women. Denote $c_{ij}$ as the compatibility score between man i and woman j. Define appropriate decision variables and write an algebraic integer programming formulation to match pairs that maximizes the total compatibility. Each man (woman) should be matched to exactly one woman (man). </p> <p>Decision variables:</p> <ul> <li>$x_{ij} \in \{0,1\}$, indicator variable. $ x_{ij}=1 $ is man $i$ is matched with woman $j$; 0 if man $i$ is not matched with woman $j$ </li> </ul> <p>Formulation:</p> <span> <p class="equation">\[\left.\begin{array}{rrcl} \min &amp; \sum_{i=1}^n \sum_{j=1}^n c_{ij}x_{ij} \\ \text {s.t.:} &amp; &amp; &amp; \\ \text{(1)} &amp; \sum_{j=1}^n x_{ij} = 1, \forall i = 1, \ldots, n\\ \text{(2)} &amp; \sum_{i=1}^n x_{ij} = 1, \forall j = 1, \ldots, n\\ \text{(3)} &amp; x_{ij} \in \{0,1\}, \forall i,j=1,\ldots,n \end{array}\right\}\]</p> </span> <p>You are concerned that some of the inequalities have been reversed. Which of the following is the best response? Select the best answer.</p> <div class="wrapper-problem-response" tabindex="-1" aria-label="Question 1" role="group"><div class="choicegroup capa_inputtype" id="inputtype_b2bc692864b749ca8dbd2a6945d26e74_2_1"> <fieldset aria-describedby="status_b2bc692864b749ca8dbd2a6945d26e74_2_1"> <div class="field"> <input type="checkbox" name="input_b2bc692864b749ca8dbd2a6945d26e74_2_1[]" id="input_b2bc692864b749ca8dbd2a6945d26e74_2_1_choice_0" class="field-input input-checkbox" value="choice_0"/><label id="b2bc692864b749ca8dbd2a6945d26e74_2_1-choice_0-label" for="input_b2bc692864b749ca8dbd2a6945d26e74_2_1_choice_0" class="response-label field-label label-inline" aria-describedby="status_b2bc692864b749ca8dbd2a6945d26e74_2_1"> The linear program is correct </label> </div> <div class="field"> <input type="checkbox" name="input_b2bc692864b749ca8dbd2a6945d26e74_2_1[]" id="input_b2bc692864b749ca8dbd2a6945d26e74_2_1_choice_1" class="field-input input-checkbox" value="choice_1"/><label id="b2bc692864b749ca8dbd2a6945d26e74_2_1-choice_1-label" for="input_b2bc692864b749ca8dbd2a6945d26e74_2_1_choice_1" class="response-label field-label label-inline" aria-describedby="status_b2bc692864b749ca8dbd2a6945d26e74_2_1"> The objective should be maximized </label> </div> <div class="field"> <input type="checkbox" name="input_b2bc692864b749ca8dbd2a6945d26e74_2_1[]" id="input_b2bc692864b749ca8dbd2a6945d26e74_2_1_choice_2" class="field-input input-checkbox" value="choice_2"/><label id="b2bc692864b749ca8dbd2a6945d26e74_2_1-choice_2-label" for="input_b2bc692864b749ca8dbd2a6945d26e74_2_1_choice_2" class="response-label field-label label-inline" aria-describedby="status_b2bc692864b749ca8dbd2a6945d26e74_2_1"> Constraints (1), (2) should have $ \leq $ inequalities </label> </div> <div class="field"> <input type="checkbox" name="input_b2bc692864b749ca8dbd2a6945d26e74_2_1[]" id="input_b2bc692864b749ca8dbd2a6945d26e74_2_1_choice_3" class="field-input input-checkbox" value="choice_3"/><label id="b2bc692864b749ca8dbd2a6945d26e74_2_1-choice_3-label" for="input_b2bc692864b749ca8dbd2a6945d26e74_2_1_choice_3" class="response-label field-label label-inline" aria-describedby="status_b2bc692864b749ca8dbd2a6945d26e74_2_1"> Constraints (1), (2) should have $ \geq $ inequalities </label> </div> <div class="field"> <input type="checkbox" name="input_b2bc692864b749ca8dbd2a6945d26e74_2_1[]" id="input_b2bc692864b749ca8dbd2a6945d26e74_2_1_choice_4" class="field-input input-checkbox" value="choice_4"/><label id="b2bc692864b749ca8dbd2a6945d26e74_2_1-choice_4-label" for="input_b2bc692864b749ca8dbd2a6945d26e74_2_1_choice_4" class="response-label field-label label-inline" aria-describedby="status_b2bc692864b749ca8dbd2a6945d26e74_2_1"> The objective should be maximized and constraints (1), (2) should have $ \leq $ inequalities </label> </div> <div class="field"> <input type="checkbox" name="input_b2bc692864b749ca8dbd2a6945d26e74_2_1[]" id="input_b2bc692864b749ca8dbd2a6945d26e74_2_1_choice_5" class="field-input input-checkbox" value="choice_5"/><label id="b2bc692864b749ca8dbd2a6945d26e74_2_1-choice_5-label" for="input_b2bc692864b749ca8dbd2a6945d26e74_2_1_choice_5" class="response-label field-label label-inline" aria-describedby="status_b2bc692864b749ca8dbd2a6945d26e74_2_1"> The objective should be maximized and constraints (1), (2) should have $ \geq $ inequalities </label> </div> <span id="answer_b2bc692864b749ca8dbd2a6945d26e74_2_1"/> </fieldset> <div class="indicator-container"> <span class="status unanswered" id="status_b2bc692864b749ca8dbd2a6945d26e74_2_1" data-tooltip="Not yet answered."> <span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/> </span> </div> </div></div> <div class="solution-span"> <span id="solution_b2bc692864b749ca8dbd2a6945d26e74_solution_1"/> </div></div> <div class="action"> <input type="hidden" name="problem_id" value="PART G" /> <div class="submit-attempt-container"> <button type="button" class="submit btn-brand" data-submitting="Submitting" data-value="Submit" data-should-enable-submit-button="True" aria-describedby="submission_feedback_b2bc692864b749ca8dbd2a6945d26e74" > <span class="submit-label">Submit</span> </button> <div class="submission-feedback" id="submission_feedback_b2bc692864b749ca8dbd2a6945d26e74"> <span class="sr">Some problems have options such as save, reset, hints, or show answer. These options follow the Submit button.</span> </div> </div> <div class="problem-action-buttons-wrapper"> </div> </div> <div class="notification warning notification-gentle-alert is-hidden" tabindex="-1"> <span class="icon fa fa-exclamation-circle" aria-hidden="true"></span> <span class="notification-message" aria-describedby="b2bc692864b749ca8dbd2a6945d26e74-problem-title"> </span> <div class="notification-btn-wrapper"> <button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button> </div> </div> <div class="notification warning notification-save is-hidden" tabindex="-1"> <span class="icon fa fa-save" aria-hidden="true"></span> <span class="notification-message" aria-describedby="b2bc692864b749ca8dbd2a6945d26e74-problem-title">None </span> <div class="notification-btn-wrapper"> <button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button> </div> </div> <div class="notification general notification-show-answer is-hidden" tabindex="-1"> <span class="icon fa fa-info-circle" aria-hidden="true"></span> <span class="notification-message" aria-describedby="b2bc692864b749ca8dbd2a6945d26e74-problem-title">Answers are displayed within the problem </span> <div class="notification-btn-wrapper"> <button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button> </div> </div> </div> " data-graded="True"> <p class="loading-spinner"> <i class="fa fa-spinner fa-pulse fa-2x fa-fw"></i> <span class="sr">Loading…</span> </p> </div> </div> </div> <div class="vert vert-9" data-id="block-v1:MITx+15.053x+3T2016+type@problem+block@65cb8bcece004073a799454056e1f784"> <div class="xblock xblock-public_view xblock-public_view-problem xmodule_display xmodule_ProblemBlock" data-usage-id="block-v1:MITx+15.053x+3T2016+type@problem+block@65cb8bcece004073a799454056e1f784" data-block-type="problem" data-graded="True" data-course-id="course-v1:MITx+15.053x+3T2016" data-has-score="True" data-request-token="a7efc0db852911ef8f57023e4242adeb" data-init="XBlockToXModuleShim" data-runtime-class="LmsRuntime" data-runtime-version="1"> <script type="json/xblock-args" class="xblock-json-init-args"> {"xmodule-type": "Problem"} </script> <div id="problem_65cb8bcece004073a799454056e1f784" class="problems-wrapper" role="group" aria-labelledby="65cb8bcece004073a799454056e1f784-problem-title" data-problem-id="block-v1:MITx+15.053x+3T2016+type@problem+block@65cb8bcece004073a799454056e1f784" data-url="/courses/course-v1:MITx+15.053x+3T2016/xblock/block-v1:MITx+15.053x+3T2016+type@problem+block@65cb8bcece004073a799454056e1f784/handler/xmodule_handler" data-problem-score="0" data-problem-total-possible="0" data-attempts-used="0" data-content=" <h3 class="hd hd-3 problem-header" id="65cb8bcece004073a799454056e1f784-problem-title" aria-describedby="block-v1:MITx+15.053x+3T2016+type@problem+block@65cb8bcece004073a799454056e1f784-problem-progress" tabindex="-1"> PART H. This part is optional. </h3> <div class="problem-progress" id="block-v1:MITx+15.053x+3T2016+type@problem+block@65cb8bcece004073a799454056e1f784-problem-progress"></div> <div class="problem"> <div> <p> This problem and the following are optional. If you are interested in using Julia and JuMP in practice, we encourage you to try it out. This exercise and the following one are similar to PART D and PART D II. Instead of solving a problem using a 3 x 3 matrix, this problem includes a 1000 x 1000 matrix. If you solve the problem, you can honestly say that you have solved a million variable integer program. </p> <p> Till now, eHarmony has 33 million members. Spreadsheet optimization is too cumbersome to use for day-to-day operations. Instead they need to rely on "modeling languages." In this part, we are going to use Julia/JuMP to solve a large-scale matching problem for eHarmony. In the material of problem set 3, you will find a csv (comma-separated values) file <a class="modal-content" href="/assets/courseware/v1/c5dbb469e204229e2f34ef810a33d424/asset-v1:MITx+15.053x+3T2016+type@asset+block/compatibility_score_integers.zip"> compatibility_score_integers.csv</a>, which represents compatibility score among 1000 men and 1000 women. The numbers in "compatibility_score.csv" constitutes a 1000 x 1000 matrix, where each row corresponds to a man, each column corresponds to a woman. Your task here is to solve this 1000 x 1000 matching problem based on the integer programming formulation in PART G using Julia/JuMP. The "readcsv" function in Julia will be helpful. We also provide a smaller data set 20 x 20 <a class="modal-content" href="/assets/courseware/v1/46437bdee89ffcfb07925892bf99fae8/asset-v1:MITx+15.053x+3T2016+type@asset+block/compatibility_score_debug_integers.csv"> compatibility_score_debug_integers.csv </a> in the problem set materials. You may debug your model with this smaller data set first before try the 1000 x 1000 version. Any bug in the 1000 x 1000 version could possibly take an absurdly long time to fix. (If you have correctly solved the 1000 x 1000 instance of this problem, then you have solved your first linear (integer) program with 1 million variables.)</p> <p>What is the optimal (integral) objective value? Error checking hint: the optimal value is between 99970 and 99989.</p> <div class="wrapper-problem-response" tabindex="-1" aria-label="Question 1" role="group"><div id="formulaequationinput_65cb8bcece004073a799454056e1f784_2_1" class="inputtype formulaequationinput"> <div class="unanswered"> <input type="text" name="input_65cb8bcece004073a799454056e1f784_2_1" id="input_65cb8bcece004073a799454056e1f784_2_1" data-input-id="65cb8bcece004073a799454056e1f784_2_1" value="" aria-describedby="status_65cb8bcece004073a799454056e1f784_2_1" size="20"/> <span class="trailing_text" id="trailing_text_65cb8bcece004073a799454056e1f784_2_1"/> <span class="status unanswered" id="status_65cb8bcece004073a799454056e1f784_2_1" data-tooltip="Not yet answered."> <span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/> </span> <p id="answer_65cb8bcece004073a799454056e1f784_2_1" class="answer"/> <div id="input_65cb8bcece004073a799454056e1f784_2_1_preview" class="equation">  <img src="/static/images/spinner.bc34f953403f.gif" class="loading" alt="Loading"/> </div> </div> <div class="script_placeholder" data-src="/static/js/capa/src/formula_equation_preview.b1967ab28c31.js"/> </div></div> <div class="solution-span"> <span id="solution_65cb8bcece004073a799454056e1f784_solution_1"/> </div></div> <div class="action"> <input type="hidden" name="problem_id" value="PART H. This part is optional." /> <div class="submit-attempt-container"> <button type="button" class="submit btn-brand" data-submitting="Submitting" data-value="Submit" data-should-enable-submit-button="True" aria-describedby="submission_feedback_65cb8bcece004073a799454056e1f784" > <span class="submit-label">Submit</span> </button> <div class="submission-feedback" id="submission_feedback_65cb8bcece004073a799454056e1f784"> <span class="sr">Some problems have options such as save, reset, hints, or show answer. These options follow the Submit button.</span> </div> </div> <div class="problem-action-buttons-wrapper"> </div> </div> <div class="notification warning notification-gentle-alert is-hidden" tabindex="-1"> <span class="icon fa fa-exclamation-circle" aria-hidden="true"></span> <span class="notification-message" aria-describedby="65cb8bcece004073a799454056e1f784-problem-title"> </span> <div class="notification-btn-wrapper"> <button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button> </div> </div> <div class="notification warning notification-save is-hidden" tabindex="-1"> <span class="icon fa fa-save" aria-hidden="true"></span> <span class="notification-message" aria-describedby="65cb8bcece004073a799454056e1f784-problem-title">None </span> <div class="notification-btn-wrapper"> <button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button> </div> </div> <div class="notification general notification-show-answer is-hidden" tabindex="-1"> <span class="icon fa fa-info-circle" aria-hidden="true"></span> <span class="notification-message" aria-describedby="65cb8bcece004073a799454056e1f784-problem-title">Answers are displayed within the problem </span> <div class="notification-btn-wrapper"> <button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button> </div> </div> </div> " data-graded="True"> <p class="loading-spinner"> <i class="fa fa-spinner fa-pulse fa-2x fa-fw"></i> <span class="sr">Loading…</span> </p> </div> </div> </div> <div class="vert vert-10" data-id="block-v1:MITx+15.053x+3T2016+type@problem+block@5205b1185e21471983001677b7e0f790"> <div class="xblock xblock-public_view xblock-public_view-problem xmodule_display xmodule_ProblemBlock" data-usage-id="block-v1:MITx+15.053x+3T2016+type@problem+block@5205b1185e21471983001677b7e0f790" data-block-type="problem" data-graded="True" data-course-id="course-v1:MITx+15.053x+3T2016" data-has-score="True" data-request-token="a7efc0db852911ef8f57023e4242adeb" data-init="XBlockToXModuleShim" data-runtime-class="LmsRuntime" data-runtime-version="1"> <script type="json/xblock-args" class="xblock-json-init-args"> {"xmodule-type": "Problem"} </script> <div id="problem_5205b1185e21471983001677b7e0f790" class="problems-wrapper" role="group" aria-labelledby="5205b1185e21471983001677b7e0f790-problem-title" data-problem-id="block-v1:MITx+15.053x+3T2016+type@problem+block@5205b1185e21471983001677b7e0f790" data-url="/courses/course-v1:MITx+15.053x+3T2016/xblock/block-v1:MITx+15.053x+3T2016+type@problem+block@5205b1185e21471983001677b7e0f790/handler/xmodule_handler" data-problem-score="0" data-problem-total-possible="0" data-attempts-used="0" data-content=" <h3 class="hd hd-3 problem-header" id="5205b1185e21471983001677b7e0f790-problem-title" aria-describedby="block-v1:MITx+15.053x+3T2016+type@problem+block@5205b1185e21471983001677b7e0f790-problem-progress" tabindex="-1"> PART I. This part is optional. </h3> <div class="problem-progress" id="block-v1:MITx+15.053x+3T2016+type@problem+block@5205b1185e21471983001677b7e0f790-problem-progress"></div> <div class="problem"> <div> <p>Solve the problem from PART H without integral constraints (i.e. replacing $x_{ij} \in \{0,1\} $ with $0 \le x_{ij} \le 1, \forall i, j =1, \ldots, n$) using data in "compatibility_score_integers.csv". What is the optimal objective value in the output? HINT: It should be the same as for the integer program. </p> <div class="wrapper-problem-response" tabindex="-1" aria-label="Question 1" role="group"><div id="formulaequationinput_5205b1185e21471983001677b7e0f790_2_1" class="inputtype formulaequationinput"> <div class="unanswered"> <input type="text" name="input_5205b1185e21471983001677b7e0f790_2_1" id="input_5205b1185e21471983001677b7e0f790_2_1" data-input-id="5205b1185e21471983001677b7e0f790_2_1" value="" aria-describedby="status_5205b1185e21471983001677b7e0f790_2_1" size="20"/> <span class="trailing_text" id="trailing_text_5205b1185e21471983001677b7e0f790_2_1"/> <span class="status unanswered" id="status_5205b1185e21471983001677b7e0f790_2_1" data-tooltip="Not yet answered."> <span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/> </span> <p id="answer_5205b1185e21471983001677b7e0f790_2_1" class="answer"/> <div id="input_5205b1185e21471983001677b7e0f790_2_1_preview" class="equation">  <img src="/static/images/spinner.bc34f953403f.gif" class="loading" alt="Loading"/> </div> </div> <div class="script_placeholder" data-src="/static/js/capa/src/formula_equation_preview.b1967ab28c31.js"/> </div></div> <div class="solution-span"> <span id="solution_5205b1185e21471983001677b7e0f790_solution_1"/> </div></div> <div class="action"> <input type="hidden" name="problem_id" value="PART I. This part is optional." /> <div class="submit-attempt-container"> <button type="button" class="submit btn-brand" data-submitting="Submitting" data-value="Submit" data-should-enable-submit-button="True" aria-describedby="submission_feedback_5205b1185e21471983001677b7e0f790" > <span class="submit-label">Submit</span> </button> <div class="submission-feedback" id="submission_feedback_5205b1185e21471983001677b7e0f790"> <span class="sr">Some problems have options such as save, reset, hints, or show answer. These options follow the Submit button.</span> </div> </div> <div class="problem-action-buttons-wrapper"> <span class="problem-action-button-wrapper"> <button type="button" class="save problem-action-btn btn-default btn-small" data-value="Save"> <span class="icon fa fa-floppy-o" aria-hidden="true"></span> <span aria-hidden="true">Save</span> <span class="sr">Save your answer</span> </button> </span> </div> </div> <div class="notification warning notification-gentle-alert is-hidden" tabindex="-1"> <span class="icon fa fa-exclamation-circle" aria-hidden="true"></span> <span class="notification-message" aria-describedby="5205b1185e21471983001677b7e0f790-problem-title"> </span> <div class="notification-btn-wrapper"> <button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button> </div> </div> <div class="notification warning notification-save is-hidden" tabindex="-1"> <span class="icon fa fa-save" aria-hidden="true"></span> <span class="notification-message" aria-describedby="5205b1185e21471983001677b7e0f790-problem-title">None </span> <div class="notification-btn-wrapper"> <button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button> </div> </div> <div class="notification general notification-show-answer is-hidden" tabindex="-1"> <span class="icon fa fa-info-circle" aria-hidden="true"></span> <span class="notification-message" aria-describedby="5205b1185e21471983001677b7e0f790-problem-title">Answers are displayed within the problem </span> <div class="notification-btn-wrapper"> <button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button> </div> </div> </div> " data-graded="True"> <p class="loading-spinner"> <i class="fa fa-spinner fa-pulse fa-2x fa-fw"></i> <span class="sr">Loading…</span> </p> </div> </div> </div> </div> </div>

<div class="xblock xblock-public_view xblock-public_view-vertical" data-usage-id="block-v1:MITx+15.053x+3T2016+type@vertical+block@29d4e542f5cb418da208c6540cd8194c" data-block-type="vertical" data-graded="True" data-course-id="course-v1:MITx+15.053x+3T2016" data-has-score="False" data-request-token="a7efc0db852911ef8f57023e4242adeb" data-init="VerticalStudentView" data-runtime-class="LmsRuntime" data-runtime-version="1"> <h2 class="hd hd-2 unit-title">Problem 3</h2> <div class="vert-mod"> <div class="vert vert-0" data-id="block-v1:MITx+15.053x+3T2016+type@problem+block@c6082407ea22473984ba87ca88d40496"> <div class="xblock xblock-public_view xblock-public_view-problem xmodule_display xmodule_ProblemBlock" data-usage-id="block-v1:MITx+15.053x+3T2016+type@problem+block@c6082407ea22473984ba87ca88d40496" data-block-type="problem" data-graded="True" data-course-id="course-v1:MITx+15.053x+3T2016" data-has-score="True" data-request-token="a7efc0db852911ef8f57023e4242adeb" data-init="XBlockToXModuleShim" data-runtime-class="LmsRuntime" data-runtime-version="1"> <script type="json/xblock-args" class="xblock-json-init-args"> {"xmodule-type": "Problem"} </script> <div id="problem_c6082407ea22473984ba87ca88d40496" class="problems-wrapper" role="group" aria-labelledby="c6082407ea22473984ba87ca88d40496-problem-title" data-problem-id="block-v1:MITx+15.053x+3T2016+type@problem+block@c6082407ea22473984ba87ca88d40496" data-url="/courses/course-v1:MITx+15.053x+3T2016/xblock/block-v1:MITx+15.053x+3T2016+type@problem+block@c6082407ea22473984ba87ca88d40496/handler/xmodule_handler" data-problem-score="0.0" data-problem-total-possible="1.0" data-attempts-used="0" data-content=" <h3 class="hd hd-3 problem-header" id="c6082407ea22473984ba87ca88d40496-problem-title" aria-describedby="block-v1:MITx+15.053x+3T2016+type@problem+block@c6082407ea22473984ba87ca88d40496-problem-progress" tabindex="-1"> PART A </h3> <div class="problem-progress" id="block-v1:MITx+15.053x+3T2016+type@problem+block@c6082407ea22473984ba87ca88d40496-problem-progress"></div> <div class="problem"> <div> <p>A <i>combinatorial auction</i> is an auction in which participants can place bids on sets of items, instead of placing bids on individual items. A combinatorial auction is useful in many situations. For example, consider the problem of an airline company buying takeoff and landing slots at an airport: clearly, the value of a single slot may be small if the slot is taken by itself, but the value may be much larger if several slots can be bought at the same time, allowing the company to setup flight routes according to the desired timetable. Thus, the airport wants to sell its available slots to airline companies maximizing its own profit (i.e. the total value at which the slots are sold), allowing airlines to bid on sets of items and choosing the most profitable combination of bids among the received ones. Many other examples exist. In this problem, we study a simple formulation for a combinatorial auction. </p> <p>Consider a set composed by 5 items, labeled for simplicity: $\{1, 2, 3, 4, 5\}$. We auction off these items and receive the following bids, where each bid is placed on a subset of the items and assigns a value to the whole subset: </p> <ul> <li>Bid 1: subset $\{1, 5\}$ valued at 10.</li> <li>Bid 2: subset $\{1, 2, 4\}$ valued at 20.</li> <li>Bid 3: subset $\{3\}$ valued at 8.</li> <li>Bid 4: subset $\{5\}$ valued at 4.</li> <li>Bid 5: subset $\{2, 4\}$ valued at 15.</li> <li>Bid 6: subset $\{2, 3, 4, 5\}$ valued at 30.</li> <li>Bid 7: subset $\{1, 2, 3\}$ valued at 18.</li> </ul> <p>Let $x_j$ be 1 if the j-th bid is accepted, 0 if it is not. These are all the variables we need.</p> <p>Formulate an integer program to choose the subset of bids that maximizes profit for the auctioneer, i.e., the total value for which the items are sold is maximum. We remark that each item can be sold at most once, and that bids cannot be split; that is: a bid for items $\{1, 2\}$ can only be accepted if both item 1 and 2 are available. Which integer program below properly models the situation? </p> <div class="wrapper-problem-response" tabindex="-1" aria-label="Question 1" role="group"><div class="choicegroup capa_inputtype" id="inputtype_c6082407ea22473984ba87ca88d40496_2_1"> <fieldset aria-describedby="status_c6082407ea22473984ba87ca88d40496_2_1"> <div class="field"> <input type="radio" name="input_c6082407ea22473984ba87ca88d40496_2_1" id="input_c6082407ea22473984ba87ca88d40496_2_1_choice_0" class="field-input input-radio" value="choice_0"/><label id="c6082407ea22473984ba87ca88d40496_2_1-choice_0-label" for="input_c6082407ea22473984ba87ca88d40496_2_1_choice_0" class="response-label field-label label-inline" aria-describedby="status_c6082407ea22473984ba87ca88d40496_2_1"> <text> <p class="equation">\[\left.\begin{array}{rrcl} \max &amp; 10x_1 + 20x_2 + 8x_3 + 4x_4 + 15x_5 + 30x_6 + 18x_7 \\ \text {s.t.:} &amp; &amp; &amp; \\ &amp; x_1 + x_2 + x_7 \leq 1 \\ &amp; x_2 + x_5 + x_6 + x_7 \leq 1 \\ &amp; x_3 + x_6 + x_7 \leq 1 \\ &amp; x_2 + x_5 + x_6 \leq 1 \\ &amp; x_1 + x_4 + x_6 \leq 1 \\ &amp; x_1, x_2, x_3, x_4, x_5, x_6, x_7\in \{0,1\} \end{array}\right\}\]</p> </text> </label> </div> <div class="field"> <input type="radio" name="input_c6082407ea22473984ba87ca88d40496_2_1" id="input_c6082407ea22473984ba87ca88d40496_2_1_choice_1" class="field-input input-radio" value="choice_1"/><label id="c6082407ea22473984ba87ca88d40496_2_1-choice_1-label" for="input_c6082407ea22473984ba87ca88d40496_2_1_choice_1" class="response-label field-label label-inline" aria-describedby="status_c6082407ea22473984ba87ca88d40496_2_1"> <text> <p class="equation">\[\left.\begin{array}{rrcl} \max &amp; 10x_1 + 20x_2 + 8x_3 + 4x_4 + 15x_5 + 30x_6 + 18x_7 \\ \text {s.t.:} &amp; &amp; &amp; \\ &amp; x_1 + x_2 + x_7 \geq 1 \\ &amp; x_2 + x_5 + x_6 + x_7 \geq 1 \\ &amp; x_3 + x_6 + x_7 \geq 1 \\ &amp; x_2 + x_5 + x_6 \geq 1 \\ &amp; x_1 + x_4 + x_6 \geq 1 \\ &amp; x_1, x_2, x_3, x_4, x_5, x_6, x_7\in \{0,1\} \end{array}\right\}\]</p> </text> </label> </div> <div class="field"> <input type="radio" name="input_c6082407ea22473984ba87ca88d40496_2_1" id="input_c6082407ea22473984ba87ca88d40496_2_1_choice_2" class="field-input input-radio" value="choice_2"/><label id="c6082407ea22473984ba87ca88d40496_2_1-choice_2-label" for="input_c6082407ea22473984ba87ca88d40496_2_1_choice_2" class="response-label field-label label-inline" aria-describedby="status_c6082407ea22473984ba87ca88d40496_2_1"> <text> <p class="equation">\[\left.\begin{array}{rrcl} \max &amp; 10x_1 + 20x_2 + 8x_3 + 4x_4 + 15x_5 + 30x_6 + 18x_7 \\ \text {s.t.:} &amp; &amp; &amp; \\ &amp; x_1 + x_5 \leq 1 \\ &amp; x_1 + x_2 + x_4 \leq 1 \\ &amp; x_3 \leq 1 \\ &amp; x_5 \leq 1 \\ &amp; x_2 + x_4 \leq 1 \\ &amp; x_1, x_2, x_3, x_4, x_5, x_6, x_7\in \{0,1\} \end{array}\right\}\]</p> </text> </label> </div> <span id="answer_c6082407ea22473984ba87ca88d40496_2_1"/> </fieldset> <div class="indicator-container"> <span class="status unanswered" id="status_c6082407ea22473984ba87ca88d40496_2_1" data-tooltip="Not yet answered."> <span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/> </span> </div> </div></div> <div class="solution-span"> <span id="solution_c6082407ea22473984ba87ca88d40496_solution_1"/> </div></div> <div class="action"> <input type="hidden" name="problem_id" value="PART A" /> <div class="submit-attempt-container"> <button type="button" class="submit btn-brand" data-submitting="Submitting" data-value="Submit" data-should-enable-submit-button="True" aria-describedby="submission_feedback_c6082407ea22473984ba87ca88d40496" > <span class="submit-label">Submit</span> </button> <div class="submission-feedback" id="submission_feedback_c6082407ea22473984ba87ca88d40496"> <span class="sr">Some problems have options such as save, reset, hints, or show answer. These options follow the Submit button.</span> </div> </div> <div class="problem-action-buttons-wrapper"> </div> </div> <div class="notification warning notification-gentle-alert is-hidden" tabindex="-1"> <span class="icon fa fa-exclamation-circle" aria-hidden="true"></span> <span class="notification-message" aria-describedby="c6082407ea22473984ba87ca88d40496-problem-title"> </span> <div class="notification-btn-wrapper"> <button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button> </div> </div> <div class="notification warning notification-save is-hidden" tabindex="-1"> <span class="icon fa fa-save" aria-hidden="true"></span> <span class="notification-message" aria-describedby="c6082407ea22473984ba87ca88d40496-problem-title">None </span> <div class="notification-btn-wrapper"> <button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button> </div> </div> <div class="notification general notification-show-answer is-hidden" tabindex="-1"> <span class="icon fa fa-info-circle" aria-hidden="true"></span> <span class="notification-message" aria-describedby="c6082407ea22473984ba87ca88d40496-problem-title">Answers are displayed within the problem </span> <div class="notification-btn-wrapper"> <button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button> </div> </div> </div> " data-graded="True"> <p class="loading-spinner"> <i class="fa fa-spinner fa-pulse fa-2x fa-fw"></i> <span class="sr">Loading…</span> </p> </div> </div> </div> <div class="vert vert-1" data-id="block-v1:MITx+15.053x+3T2016+type@problem+block@d158487541c5448ab114641d9e4fd358"> <div class="xblock xblock-public_view xblock-public_view-problem xmodule_display xmodule_ProblemBlock" data-usage-id="block-v1:MITx+15.053x+3T2016+type@problem+block@d158487541c5448ab114641d9e4fd358" data-block-type="problem" data-graded="True" data-course-id="course-v1:MITx+15.053x+3T2016" data-has-score="True" data-request-token="a7efc0db852911ef8f57023e4242adeb" data-init="XBlockToXModuleShim" data-runtime-class="LmsRuntime" data-runtime-version="1"> <script type="json/xblock-args" class="xblock-json-init-args"> {"xmodule-type": "Problem"} </script> <div id="problem_d158487541c5448ab114641d9e4fd358" class="problems-wrapper" role="group" aria-labelledby="d158487541c5448ab114641d9e4fd358-problem-title" data-problem-id="block-v1:MITx+15.053x+3T2016+type@problem+block@d158487541c5448ab114641d9e4fd358" data-url="/courses/course-v1:MITx+15.053x+3T2016/xblock/block-v1:MITx+15.053x+3T2016+type@problem+block@d158487541c5448ab114641d9e4fd358/handler/xmodule_handler" data-problem-score="0.0" data-problem-total-possible="1.0" data-attempts-used="0" data-content=" <h3 class="hd hd-3 problem-header" id="d158487541c5448ab114641d9e4fd358-problem-title" aria-describedby="block-v1:MITx+15.053x+3T2016+type@problem+block@d158487541c5448ab114641d9e4fd358-problem-progress" tabindex="-1"> PART B </h3> <div class="problem-progress" id="block-v1:MITx+15.053x+3T2016+type@problem+block@d158487541c5448ab114641d9e4fd358-problem-progress"></div> <div class="problem"> <div> <p>Suppose now that we are still auctioning off the set of items $\{1, 2, 3, 4, 5\}$, but now we have two copies each of items 1, 2, 3. In other words, the set of items for auctions looks like this: $\{1, 1, 2, 2, 3, 3, 4, 5\}$. The set of received bids does not change, and each bid can only be accepted at most once. Which IP properly models the situation? </p> <div class="wrapper-problem-response" tabindex="-1" aria-label="Question 1" role="group"><div class="choicegroup capa_inputtype" id="inputtype_d158487541c5448ab114641d9e4fd358_2_1"> <fieldset aria-describedby="status_d158487541c5448ab114641d9e4fd358_2_1"> <div class="field"> <input type="radio" name="input_d158487541c5448ab114641d9e4fd358_2_1" id="input_d158487541c5448ab114641d9e4fd358_2_1_choice_0" class="field-input input-radio" value="choice_0"/><label id="d158487541c5448ab114641d9e4fd358_2_1-choice_0-label" for="input_d158487541c5448ab114641d9e4fd358_2_1_choice_0" class="response-label field-label label-inline" aria-describedby="status_d158487541c5448ab114641d9e4fd358_2_1"> <text> <p class="equation">\[\left.\begin{array}{rrcl} \max &amp; 10x_1 + 20x_2 + 8x_3 + 4x_4 + 15x_5 + 30x_6 + 18x_7 \\ \text {s.t.:} &amp; &amp; &amp; \\ &amp; x_1 + x_2 + x_7 \geq 2 \\ &amp; x_2 + x_5 + x_6 + x_7 \geq 2 \\ &amp; x_3 + x_6 + x_7 \leq 1 \\ &amp; x_2 + x_5 + x_6 \leq 1 \\ &amp; x_1 + x_4 + x_6 \leq 1 \\ &amp; x_1, x_2, x_3, x_4, x_5, x_6, x_7\in \{0,1\} \end{array}\right\}\]</p> </text> </label> </div> <div class="field"> <input type="radio" name="input_d158487541c5448ab114641d9e4fd358_2_1" id="input_d158487541c5448ab114641d9e4fd358_2_1_choice_1" class="field-input input-radio" value="choice_1"/><label id="d158487541c5448ab114641d9e4fd358_2_1-choice_1-label" for="input_d158487541c5448ab114641d9e4fd358_2_1_choice_1" class="response-label field-label label-inline" aria-describedby="status_d158487541c5448ab114641d9e4fd358_2_1"> <text> <p class="equation">\[\left.\begin{array}{rrcl} \max &amp; 10x_1 + 20x_2 + 8x_3 + 4x_4 + 15x_5 + 30x_6 + 18x_7 \\ \text {s.t.:} &amp; &amp; &amp; \\ &amp; x_1 + x_2 + x_7 \leq 2 \\ &amp; x_2 + x_5 + x_6 + x_7 \leq 2 \\ &amp; x_3 + x_6 + x_7 \leq 2 \\ &amp; x_2 + x_5 + x_6 \leq 1 \\ &amp; x_1 + x_4 + x_6 \leq 1 \\ &amp; x_1, x_2, x_3, x_4, x_5, x_6, x_7\in \{0,1\} \end{array}\right\}\]</p> </text> </label> </div> <div class="field"> <input type="radio" name="input_d158487541c5448ab114641d9e4fd358_2_1" id="input_d158487541c5448ab114641d9e4fd358_2_1_choice_2" class="field-input input-radio" value="choice_2"/><label id="d158487541c5448ab114641d9e4fd358_2_1-choice_2-label" for="input_d158487541c5448ab114641d9e4fd358_2_1_choice_2" class="response-label field-label label-inline" aria-describedby="status_d158487541c5448ab114641d9e4fd358_2_1"> <text> <p class="equation">\[\left.\begin{array}{rrcl} \max &amp; 10x_1 + 20x_2 + 8x_3 + 4x_4 + 15x_5 + 30x_6 + 18x_7 \\ \text {s.t.:} &amp; &amp; &amp; \\ &amp; x_1 + x_2 + x_7 \leq 2 \\ &amp; x_2 + x_3 + x_4 + x_7 \leq 1 \\ &amp; x_3 + x_6 + x_7 \leq 1 \\ &amp; x_2 + x_5 + x_7 \leq 2 \\ &amp; x_1 + x_4 + x_6 \leq 2 \\ &amp; x_1, x_2, x_3, x_4, x_5, x_6, x_7\in \{0,1\} \end{array}\right\}\]</p> </text> </label> </div> <div class="field"> <input type="radio" name="input_d158487541c5448ab114641d9e4fd358_2_1" id="input_d158487541c5448ab114641d9e4fd358_2_1_choice_3" class="field-input input-radio" value="choice_3"/><label id="d158487541c5448ab114641d9e4fd358_2_1-choice_3-label" for="input_d158487541c5448ab114641d9e4fd358_2_1_choice_3" class="response-label field-label label-inline" aria-describedby="status_d158487541c5448ab114641d9e4fd358_2_1"> <text> <p class="equation">\[\left.\begin{array}{rrcl} \max &amp; 10x_1 - 20x_2 - 8x_3 - 4x_4 - 15x_5 - 30x_6 - 18x_7 \\ \text {s.t.:} &amp; &amp; &amp; \\ &amp; x_1 + x_5 \leq 2 \\ &amp; x_1 + x_2 + x_4 \leq 2 \\ &amp; x_3 \leq 2 \\ &amp; x_5 \leq 1 \\ &amp; x_2 + x_4 \leq 1 \\ &amp; x_1, x_2, x_3, x_4, x_5, x_6, x_7\in \{0,1\} \end{array}\right\}\]</p> </text> </label> </div> <span id="answer_d158487541c5448ab114641d9e4fd358_2_1"/> </fieldset> <div class="indicator-container"> <span class="status unanswered" id="status_d158487541c5448ab114641d9e4fd358_2_1" data-tooltip="Not yet answered."> <span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/> </span> </div> </div></div> <div class="solution-span"> <span id="solution_d158487541c5448ab114641d9e4fd358_solution_1"/> </div></div> <div class="action"> <input type="hidden" name="problem_id" value="PART B" /> <div class="submit-attempt-container"> <button type="button" class="submit btn-brand" data-submitting="Submitting" data-value="Submit" data-should-enable-submit-button="True" aria-describedby="submission_feedback_d158487541c5448ab114641d9e4fd358" > <span class="submit-label">Submit</span> </button> <div class="submission-feedback" id="submission_feedback_d158487541c5448ab114641d9e4fd358"> <span class="sr">Some problems have options such as save, reset, hints, or show answer. These options follow the Submit button.</span> </div> </div> <div class="problem-action-buttons-wrapper"> </div> </div> <div class="notification warning notification-gentle-alert is-hidden" tabindex="-1"> <span class="icon fa fa-exclamation-circle" aria-hidden="true"></span> <span class="notification-message" aria-describedby="d158487541c5448ab114641d9e4fd358-problem-title"> </span> <div class="notification-btn-wrapper"> <button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button> </div> </div> <div class="notification warning notification-save is-hidden" tabindex="-1"> <span class="icon fa fa-save" aria-hidden="true"></span> <span class="notification-message" aria-describedby="d158487541c5448ab114641d9e4fd358-problem-title">None </span> <div class="notification-btn-wrapper"> <button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button> </div> </div> <div class="notification general notification-show-answer is-hidden" tabindex="-1"> <span class="icon fa fa-info-circle" aria-hidden="true"></span> <span class="notification-message" aria-describedby="d158487541c5448ab114641d9e4fd358-problem-title">Answers are displayed within the problem </span> <div class="notification-btn-wrapper"> <button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button> </div> </div> </div> " data-graded="True"> <p class="loading-spinner"> <i class="fa fa-spinner fa-pulse fa-2x fa-fw"></i> <span class="sr">Loading…</span> </p> </div> </div> </div> <div class="vert vert-2" data-id="block-v1:MITx+15.053x+3T2016+type@problem+block@04821b72e71e46a3a8964a833578967f"> <div class="xblock xblock-public_view xblock-public_view-problem xmodule_display xmodule_ProblemBlock" data-usage-id="block-v1:MITx+15.053x+3T2016+type@problem+block@04821b72e71e46a3a8964a833578967f" data-block-type="problem" data-graded="True" data-course-id="course-v1:MITx+15.053x+3T2016" data-has-score="True" data-request-token="a7efc0db852911ef8f57023e4242adeb" data-init="XBlockToXModuleShim" data-runtime-class="LmsRuntime" data-runtime-version="1"> <script type="json/xblock-args" class="xblock-json-init-args"> {"xmodule-type": "Problem"} </script> <div id="problem_04821b72e71e46a3a8964a833578967f" class="problems-wrapper" role="group" aria-labelledby="04821b72e71e46a3a8964a833578967f-problem-title" data-problem-id="block-v1:MITx+15.053x+3T2016+type@problem+block@04821b72e71e46a3a8964a833578967f" data-url="/courses/course-v1:MITx+15.053x+3T2016/xblock/block-v1:MITx+15.053x+3T2016+type@problem+block@04821b72e71e46a3a8964a833578967f/handler/xmodule_handler" data-problem-score="0.0" data-problem-total-possible="1.0" data-attempts-used="0" data-content=" <h3 class="hd hd-3 problem-header" id="04821b72e71e46a3a8964a833578967f-problem-title" aria-describedby="block-v1:MITx+15.053x+3T2016+type@problem+block@04821b72e71e46a3a8964a833578967f-problem-progress" tabindex="-1"> PART C </h3> <div class="problem-progress" id="block-v1:MITx+15.053x+3T2016+type@problem+block@04821b72e71e46a3a8964a833578967f-problem-progress"></div> <div class="problem"> <div> <p>Write an algebraic formulation for the problem of maximizing profit of the auctioneer, using the following notation: $N = \{1, . . . , n\}$ is the set of auctioned items, each item is available with multiplicity $\lambda_i \geq 1$ (i.e., there are $\lambda_i$ copies of item $i, i = 1, . . . , n)$, and we received $b$ bids, where each bid consists of a subset $S_j \subseteq N$ and a corresponding value $p_j, j = 1,\ldots, b$. Which LP choice properly models the situation? </p> <p>Recall that ":" means such that</p> <div class="wrapper-problem-response" tabindex="-1" aria-label="Question 1" role="group"><div class="choicegroup capa_inputtype" id="inputtype_04821b72e71e46a3a8964a833578967f_2_1"> <fieldset aria-describedby="status_04821b72e71e46a3a8964a833578967f_2_1"> <div class="field"> <input type="radio" name="input_04821b72e71e46a3a8964a833578967f_2_1" id="input_04821b72e71e46a3a8964a833578967f_2_1_choice_0" class="field-input input-radio" value="choice_0"/><label id="04821b72e71e46a3a8964a833578967f_2_1-choice_0-label" for="input_04821b72e71e46a3a8964a833578967f_2_1_choice_0" class="response-label field-label label-inline" aria-describedby="status_04821b72e71e46a3a8964a833578967f_2_1"> <text> <p class="equation">\[\left.\begin{array}{rrcl} \max &amp; \sum_{j=1}^b S_jx_j \\ \text {s.t.:} &amp; &amp; &amp; \\ &amp; \sum_{j: i \in S_j} x_j \leq \lambda_i, \forall i = 1, \ldots, n\\ &amp; x_j \in \{0,1\}, \forall j=1,\ldots,b \end{array}\right\}\]</p> </text> </label> </div> <div class="field"> <input type="radio" name="input_04821b72e71e46a3a8964a833578967f_2_1" id="input_04821b72e71e46a3a8964a833578967f_2_1_choice_1" class="field-input input-radio" value="choice_1"/><label id="04821b72e71e46a3a8964a833578967f_2_1-choice_1-label" for="input_04821b72e71e46a3a8964a833578967f_2_1_choice_1" class="response-label field-label label-inline" aria-describedby="status_04821b72e71e46a3a8964a833578967f_2_1"> <text> <p class="equation">\[\left.\begin{array}{rrcl} \max &amp; \sum_{j=1}^b p_jx_j \\ \text {s.t.:} &amp; &amp; &amp; \\ &amp; \sum_{j: i \in b} x_j \leq \lambda_i, \forall i = 1, \ldots, n\\ &amp; x_j \in \{0,1\}, \forall j=1,\ldots,b \end{array}\right\}\]</p> </text> </label> </div> <div class="field"> <input type="radio" name="input_04821b72e71e46a3a8964a833578967f_2_1" id="input_04821b72e71e46a3a8964a833578967f_2_1_choice_2" class="field-input input-radio" value="choice_2"/><label id="04821b72e71e46a3a8964a833578967f_2_1-choice_2-label" for="input_04821b72e71e46a3a8964a833578967f_2_1_choice_2" class="response-label field-label label-inline" aria-describedby="status_04821b72e71e46a3a8964a833578967f_2_1"> <text> <p class="equation">\[\left.\begin{array}{rrcl} \max &amp; \sum_{j=1}^b p_jx_j \\ \text {s.t.:} &amp; &amp; &amp; \\ &amp; \sum_{j: i \in S_j} p_j \leq \lambda_i, \forall i = 1, \ldots, n\\ &amp; x_j \in \{0,1\}, \forall j=1,\ldots,b \end{array}\right\}\]</p> </text> </label> </div> <div class="field"> <input type="radio" name="input_04821b72e71e46a3a8964a833578967f_2_1" id="input_04821b72e71e46a3a8964a833578967f_2_1_choice_3" class="field-input input-radio" value="choice_3"/><label id="04821b72e71e46a3a8964a833578967f_2_1-choice_3-label" for="input_04821b72e71e46a3a8964a833578967f_2_1_choice_3" class="response-label field-label label-inline" aria-describedby="status_04821b72e71e46a3a8964a833578967f_2_1"> <text> <p class="equation">\[\left.\begin{array}{rrcl} \max &amp; \sum_{j=1}^b p_jx_j \\ \text {s.t.:} &amp; &amp; &amp; \\ &amp; \sum_{j: i \in S_j} x_j \leq \lambda_i, \forall i = 1, \ldots, n\\ &amp; x_j \in \{0,1\}, \forall j=1,\ldots,b \end{array}\right\}\]</p> </text> </label> </div> <span id="answer_04821b72e71e46a3a8964a833578967f_2_1"/> </fieldset> <div class="indicator-container"> <span class="status unanswered" id="status_04821b72e71e46a3a8964a833578967f_2_1" data-tooltip="Not yet answered."> <span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/> </span> </div> </div></div> <div class="solution-span"> <span id="solution_04821b72e71e46a3a8964a833578967f_solution_1"/> </div></div> <div class="action"> <input type="hidden" name="problem_id" value="PART C" /> <div class="submit-attempt-container"> <button type="button" class="submit btn-brand" data-submitting="Submitting" data-value="Submit" data-should-enable-submit-button="True" aria-describedby="submission_feedback_04821b72e71e46a3a8964a833578967f" > <span class="submit-label">Submit</span> </button> <div class="submission-feedback" id="submission_feedback_04821b72e71e46a3a8964a833578967f"> <span class="sr">Some problems have options such as save, reset, hints, or show answer. These options follow the Submit button.</span> </div> </div> <div class="problem-action-buttons-wrapper"> </div> </div> <div class="notification warning notification-gentle-alert is-hidden" tabindex="-1"> <span class="icon fa fa-exclamation-circle" aria-hidden="true"></span> <span class="notification-message" aria-describedby="04821b72e71e46a3a8964a833578967f-problem-title"> </span> <div class="notification-btn-wrapper"> <button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button> </div> </div> <div class="notification warning notification-save is-hidden" tabindex="-1"> <span class="icon fa fa-save" aria-hidden="true"></span> <span class="notification-message" aria-describedby="04821b72e71e46a3a8964a833578967f-problem-title">None </span> <div class="notification-btn-wrapper"> <button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button> </div> </div> <div class="notification general notification-show-answer is-hidden" tabindex="-1"> <span class="icon fa fa-info-circle" aria-hidden="true"></span> <span class="notification-message" aria-describedby="04821b72e71e46a3a8964a833578967f-problem-title">Answers are displayed within the problem </span> <div class="notification-btn-wrapper"> <button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button> </div> </div> </div> " data-graded="True"> <p class="loading-spinner"> <i class="fa fa-spinner fa-pulse fa-2x fa-fw"></i> <span class="sr">Loading…</span> </p> </div> </div> </div> <div class="vert vert-3" data-id="block-v1:MITx+15.053x+3T2016+type@problem+block@3460843a39b341e1a763981895f93a2d"> <div class="xblock xblock-public_view xblock-public_view-problem xmodule_display xmodule_ProblemBlock" data-usage-id="block-v1:MITx+15.053x+3T2016+type@problem+block@3460843a39b341e1a763981895f93a2d" data-block-type="problem" data-graded="True" data-course-id="course-v1:MITx+15.053x+3T2016" data-has-score="True" data-request-token="a7efc0db852911ef8f57023e4242adeb" data-init="XBlockToXModuleShim" data-runtime-class="LmsRuntime" data-runtime-version="1"> <script type="json/xblock-args" class="xblock-json-init-args"> {"xmodule-type": "Problem"} </script> <div id="problem_3460843a39b341e1a763981895f93a2d" class="problems-wrapper" role="group" aria-labelledby="3460843a39b341e1a763981895f93a2d-problem-title" data-problem-id="block-v1:MITx+15.053x+3T2016+type@problem+block@3460843a39b341e1a763981895f93a2d" data-url="/courses/course-v1:MITx+15.053x+3T2016/xblock/block-v1:MITx+15.053x+3T2016+type@problem+block@3460843a39b341e1a763981895f93a2d/handler/xmodule_handler" data-problem-score="0.0" data-problem-total-possible="1.0" data-attempts-used="0" data-content=" <h3 class="hd hd-3 problem-header" id="3460843a39b341e1a763981895f93a2d-problem-title" aria-describedby="block-v1:MITx+15.053x+3T2016+type@problem+block@3460843a39b341e1a763981895f93a2d-problem-progress" tabindex="-1"> PART D </h3> <div class="problem-progress" id="block-v1:MITx+15.053x+3T2016+type@problem+block@3460843a39b341e1a763981895f93a2d-problem-progress"></div> <div class="problem"> <div> <p>Using the data provided in <a class="modal-content" href="/assets/courseware/v1/db4bd88e0e2425bc3db38dc3b3692bfc/asset-v1:MITx+15.053x+3T2016+type@asset+block/pset3_p3.xlsx"> pset3_p3.xlsx</a>, solve the combinatorial auction problem.</p> <p>What is the optimal revenue? Error checking hint: the optimal value is between 85 and 95.</p> <div class="wrapper-problem-response" tabindex="-1" aria-label="Question 1" role="group"><div id="formulaequationinput_3460843a39b341e1a763981895f93a2d_2_1" class="inputtype formulaequationinput"> <div class="unanswered"> <input type="text" name="input_3460843a39b341e1a763981895f93a2d_2_1" id="input_3460843a39b341e1a763981895f93a2d_2_1" data-input-id="3460843a39b341e1a763981895f93a2d_2_1" value="" aria-describedby="status_3460843a39b341e1a763981895f93a2d_2_1" size="20"/> <span class="trailing_text" id="trailing_text_3460843a39b341e1a763981895f93a2d_2_1"/> <span class="status unanswered" id="status_3460843a39b341e1a763981895f93a2d_2_1" data-tooltip="Not yet answered."> <span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/> </span> <p id="answer_3460843a39b341e1a763981895f93a2d_2_1" class="answer"/> <div id="input_3460843a39b341e1a763981895f93a2d_2_1_preview" class="equation">  <img src="/static/images/spinner.bc34f953403f.gif" class="loading" alt="Loading"/> </div> </div> <div class="script_placeholder" data-src="/static/js/capa/src/formula_equation_preview.b1967ab28c31.js"/> </div></div> <div class="solution-span"> <span id="solution_3460843a39b341e1a763981895f93a2d_solution_1"/> </div></div> <div class="action"> <input type="hidden" name="problem_id" value="PART D" /> <div class="submit-attempt-container"> <button type="button" class="submit btn-brand" data-submitting="Submitting" data-value="Submit" data-should-enable-submit-button="True" aria-describedby="submission_feedback_3460843a39b341e1a763981895f93a2d" > <span class="submit-label">Submit</span> </button> <div class="submission-feedback" id="submission_feedback_3460843a39b341e1a763981895f93a2d"> <span class="sr">Some problems have options such as save, reset, hints, or show answer. These options follow the Submit button.</span> </div> </div> <div class="problem-action-buttons-wrapper"> </div> </div> <div class="notification warning notification-gentle-alert is-hidden" tabindex="-1"> <span class="icon fa fa-exclamation-circle" aria-hidden="true"></span> <span class="notification-message" aria-describedby="3460843a39b341e1a763981895f93a2d-problem-title"> </span> <div class="notification-btn-wrapper"> <button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button> </div> </div> <div class="notification warning notification-save is-hidden" tabindex="-1"> <span class="icon fa fa-save" aria-hidden="true"></span> <span class="notification-message" aria-describedby="3460843a39b341e1a763981895f93a2d-problem-title">None </span> <div class="notification-btn-wrapper"> <button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button> </div> </div> <div class="notification general notification-show-answer is-hidden" tabindex="-1"> <span class="icon fa fa-info-circle" aria-hidden="true"></span> <span class="notification-message" aria-describedby="3460843a39b341e1a763981895f93a2d-problem-title">Answers are displayed within the problem </span> <div class="notification-btn-wrapper"> <button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button> </div> </div> </div> " data-graded="True"> <p class="loading-spinner"> <i class="fa fa-spinner fa-pulse fa-2x fa-fw"></i> <span class="sr">Loading…</span> </p> </div> </div> </div> </div> </div>

<div class="xblock xblock-public_view xblock-public_view-vertical" data-usage-id="block-v1:MITx+15.053x+3T2016+type@vertical+block@b2805e5d25a0422b9dffabff89f12255" data-block-type="vertical" data-graded="True" data-course-id="course-v1:MITx+15.053x+3T2016" data-has-score="False" data-request-token="a7efc0db852911ef8f57023e4242adeb" data-init="VerticalStudentView" data-runtime-class="LmsRuntime" data-runtime-version="1"> <h2 class="hd hd-2 unit-title">Problem 4</h2> <div class="vert-mod"> <div class="vert vert-0" data-id="block-v1:MITx+15.053x+3T2016+type@problem+block@ef07e78f3798485686b0fbad436fd5c5"> <div class="xblock xblock-public_view xblock-public_view-problem xmodule_display xmodule_ProblemBlock" data-usage-id="block-v1:MITx+15.053x+3T2016+type@problem+block@ef07e78f3798485686b0fbad436fd5c5" data-block-type="problem" data-graded="True" data-course-id="course-v1:MITx+15.053x+3T2016" data-has-score="True" data-request-token="a7efc0db852911ef8f57023e4242adeb" data-init="XBlockToXModuleShim" data-runtime-class="LmsRuntime" data-runtime-version="1"> <script type="json/xblock-args" class="xblock-json-init-args"> {"xmodule-type": "Problem"} </script> <div id="problem_ef07e78f3798485686b0fbad436fd5c5" class="problems-wrapper" role="group" aria-labelledby="ef07e78f3798485686b0fbad436fd5c5-problem-title" data-problem-id="block-v1:MITx+15.053x+3T2016+type@problem+block@ef07e78f3798485686b0fbad436fd5c5" data-url="/courses/course-v1:MITx+15.053x+3T2016/xblock/block-v1:MITx+15.053x+3T2016+type@problem+block@ef07e78f3798485686b0fbad436fd5c5/handler/xmodule_handler" data-problem-score="0.0" data-problem-total-possible="1.0" data-attempts-used="0" data-content=" <h3 class="hd hd-3 problem-header" id="ef07e78f3798485686b0fbad436fd5c5-problem-title" aria-describedby="block-v1:MITx+15.053x+3T2016+type@problem+block@ef07e78f3798485686b0fbad436fd5c5-problem-progress" tabindex="-1"> PART A </h3> <div class="problem-progress" id="block-v1:MITx+15.053x+3T2016+type@problem+block@ef07e78f3798485686b0fbad436fd5c5-problem-progress"></div> <div class="problem"> <div> <p>The local post office requires full-time employees to meet demands that vary from day to day. The number of full-time employees required on each day is given in Table 1. Each full-time employee must work five consecutive days and then receive two days off. For example, an employee who works Monday to Friday must be off on Saturday and Sunday. This schedule for employees repeats every week. We want to formulate an integer program that the post office can use to minimize the number of full-time employees who must be hired.</p> <center> <table> <tbody> <tr> <th scope="col" style="text-align: center; border: 1px solid black; padding: 10px;"/> <th scope="col" style="text-align: center; border: 1px solid black; padding: 10px;">Number of full time employees required</th> </tr> <tr> <th scope="row" style="text-align: center; border: 1px solid black; padding: 10px;">1=Monday</th> <td style="text-align: center; border: 1px solid black; padding: 10px;">17</td> </tr> <tr> <th scope="row" style="text-align: center; border: 1px solid black; padding: 10px;">2=Tuesday</th> <td style="text-align: center; border: 1px solid black; padding: 10px;">13</td> </tr> <tr> <th scope="row" style="text-align: center; border: 1px solid black; padding: 10px;">3=Wednesday</th> <td style="text-align: center; border: 1px solid black; padding: 10px;">15</td> </tr> <tr> <th scope="row" style="text-align: center; border: 1px solid black; padding: 10px;">4=Thursday</th> <td style="text-align: center; border: 1px solid black; padding: 10px;">19</td> </tr> <tr> <th scope="row" style="text-align: center; border: 1px solid black; padding: 10px;">5=Friday</th> <td style="text-align: center; border: 1px solid black; padding: 10px;">14</td> </tr> <tr> <th scope="row" style="text-align: center; border: 1px solid black; padding: 10px;">6=Saturday</th> <td style="text-align: center; border: 1px solid black; padding: 10px;">16</td> </tr> <tr> <th scope="row" style="text-align: center; border: 1px solid black; padding: 10px;">7=Sunday</th> <td style="text-align: center; border: 1px solid black; padding: 10px;">11</td> </tr> </tbody> <caption>Table 1: Requirements for the local post office</caption> </table> </center> <p/> <p>We define the decision variables as follows:</p> <ul> <li>Let $x_1$ be the number of full-time employees who work Monday to Friday</li> <li>Let $x_2$ be the number of full-time employees who work Tuesday to Saturday</li> <li>$\ldots $</li> <li>Let $x_7$ be the number of full-time employees who work Sunday to Thursday</li> </ul> <p>Then the integer program to minimize the number of total employees is given as follows:</p> <span> <p class="equation">\[\left.\begin{array}{rrcl} \min &amp; z=x_1 + x_2 + x_3 + x_4 + x_5 + x_6 + x_7 \\ \text {s.t.:} &amp; &amp; &amp; \\ &amp; x_1 + x_4 + x_5 + x_6 + x_7 \geq 17 &amp; \text{(1)}\\ &amp; x_1 + x_2 + x_5 + x_6 + x_7 \geq 13 &amp; \text{(2)}\\ &amp; x_1 + x_2 + x_3 + x_6 + x_7 \geq 15 &amp; \text{(3)}\\ &amp; x_1 + x_2 + x_3 + x_4 + x_7 \geq 19 &amp; \text{(4)}\\ &amp; x_1 + x_2 + x_3 + x_4 + x_5 \geq 14 &amp; \text{(5)}\\ &amp; x_2 + x_3 + x_4 + x_5 + x_6 \geq 16 &amp; \text{(6)}\\ &amp; x_3 + x_4 + x_5 + x_6 + x_7 \geq 11 &amp; \text{(7)}\\ &amp; x_1, x_2, x_3, x_4, x_5, x_6, x_7 \in Z^+ \end{array}\right\}\]</p> </span> <p>Constraints (1) &#8211; (7) represents that the number of employees who work on Monday to Sunday respectively should satisfy the requirement stated in Table 1. The objective function is the total number of employees required.</p> <p>The following parts are INDEPENDENT from each other. They are all based on the formulation above.</p> <p>Use the spreadsheet <a class="modal-content" href="/assets/courseware/v1/f1881475b89ae62cc7f462e005be2e28/asset-v1:MITx+15.053x+3T2016+type@asset+block/pset3_p4.xlsx"> pset3_p4.xlsx</a> to solve the above integer program. What is the minimum workers that the post office needs?</p> <div class="wrapper-problem-response" tabindex="-1" aria-label="Question 1" role="group"><div id="formulaequationinput_ef07e78f3798485686b0fbad436fd5c5_2_1" class="inputtype formulaequationinput"> <div class="unanswered"> <input type="text" name="input_ef07e78f3798485686b0fbad436fd5c5_2_1" id="input_ef07e78f3798485686b0fbad436fd5c5_2_1" data-input-id="ef07e78f3798485686b0fbad436fd5c5_2_1" value="" aria-describedby="status_ef07e78f3798485686b0fbad436fd5c5_2_1" size="20"/> <span class="trailing_text" id="trailing_text_ef07e78f3798485686b0fbad436fd5c5_2_1"/> <span class="status unanswered" id="status_ef07e78f3798485686b0fbad436fd5c5_2_1" data-tooltip="Not yet answered."> <span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/> </span> <p id="answer_ef07e78f3798485686b0fbad436fd5c5_2_1" class="answer"/> <div id="input_ef07e78f3798485686b0fbad436fd5c5_2_1_preview" class="equation">  <img src="/static/images/spinner.bc34f953403f.gif" class="loading" alt="Loading"/> </div> </div> <div class="script_placeholder" data-src="/static/js/capa/src/formula_equation_preview.b1967ab28c31.js"/> </div></div> <div class="solution-span"> <span id="solution_ef07e78f3798485686b0fbad436fd5c5_solution_1"/> </div></div> <div class="action"> <input type="hidden" name="problem_id" value="PART A" /> <div class="submit-attempt-container"> <button type="button" class="submit btn-brand" data-submitting="Submitting" data-value="Submit" data-should-enable-submit-button="True" aria-describedby="submission_feedback_ef07e78f3798485686b0fbad436fd5c5" > <span class="submit-label">Submit</span> </button> <div class="submission-feedback" id="submission_feedback_ef07e78f3798485686b0fbad436fd5c5"> <span class="sr">Some problems have options such as save, reset, hints, or show answer. These options follow the Submit button.</span> </div> </div> <div class="problem-action-buttons-wrapper"> </div> </div> <div class="notification warning notification-gentle-alert is-hidden" tabindex="-1"> <span class="icon fa fa-exclamation-circle" aria-hidden="true"></span> <span class="notification-message" aria-describedby="ef07e78f3798485686b0fbad436fd5c5-problem-title"> </span> <div class="notification-btn-wrapper"> <button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button> </div> </div> <div class="notification warning notification-save is-hidden" tabindex="-1"> <span class="icon fa fa-save" aria-hidden="true"></span> <span class="notification-message" aria-describedby="ef07e78f3798485686b0fbad436fd5c5-problem-title">None </span> <div class="notification-btn-wrapper"> <button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button> </div> </div> <div class="notification general notification-show-answer is-hidden" tabindex="-1"> <span class="icon fa fa-info-circle" aria-hidden="true"></span> <span class="notification-message" aria-describedby="ef07e78f3798485686b0fbad436fd5c5-problem-title">Answers are displayed within the problem </span> <div class="notification-btn-wrapper"> <button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button> </div> </div> </div> " data-graded="True"> <p class="loading-spinner"> <i class="fa fa-spinner fa-pulse fa-2x fa-fw"></i> <span class="sr">Loading…</span> </p> </div> </div> </div> <div class="vert vert-1" data-id="block-v1:MITx+15.053x+3T2016+type@problem+block@d85185bf4f0d417f834ef38d26263d9e"> <div class="xblock xblock-public_view xblock-public_view-problem xmodule_display xmodule_ProblemBlock" data-usage-id="block-v1:MITx+15.053x+3T2016+type@problem+block@d85185bf4f0d417f834ef38d26263d9e" data-block-type="problem" data-graded="True" data-course-id="course-v1:MITx+15.053x+3T2016" data-has-score="True" data-request-token="a7efc0db852911ef8f57023e4242adeb" data-init="XBlockToXModuleShim" data-runtime-class="LmsRuntime" data-runtime-version="1"> <script type="json/xblock-args" class="xblock-json-init-args"> {"xmodule-type": "Problem"} </script> <div id="problem_d85185bf4f0d417f834ef38d26263d9e" class="problems-wrapper" role="group" aria-labelledby="d85185bf4f0d417f834ef38d26263d9e-problem-title" data-problem-id="block-v1:MITx+15.053x+3T2016+type@problem+block@d85185bf4f0d417f834ef38d26263d9e" data-url="/courses/course-v1:MITx+15.053x+3T2016/xblock/block-v1:MITx+15.053x+3T2016+type@problem+block@d85185bf4f0d417f834ef38d26263d9e/handler/xmodule_handler" data-problem-score="0.0" data-problem-total-possible="1.0" data-attempts-used="0" data-content=" <h3 class="hd hd-3 problem-header" id="d85185bf4f0d417f834ef38d26263d9e-problem-title" aria-describedby="block-v1:MITx+15.053x+3T2016+type@problem+block@d85185bf4f0d417f834ef38d26263d9e-problem-progress" tabindex="-1"> PART B </h3> <div class="problem-progress" id="block-v1:MITx+15.053x+3T2016+type@problem+block@d85185bf4f0d417f834ef38d26263d9e-problem-progress"></div> <div class="problem"> <div> <p>Let $s_2, s_5, \text{ and } s_7$ (assume integers) denote the surplus number of workers on Tuesday, Friday, and Sunday. For example, if there are 18 workers on Tuesday, then the $ s_2=5 $. Suppose that the current objective is to minimize $z=max \{s_2,s_5,s_7 \}$. Reformulate that as an IP. Include all constraints that contain $s_2, s_5 \text{ or } s_7$, other than the non-negativity and integrality constraints, as well as any other changes from the original formulation. Which of the following are necessary changes to the original integer program? Select 6 of the constraints. </p> <div class="wrapper-problem-response" tabindex="-1" aria-label="Question 1" role="group"><div class="choicegroup capa_inputtype" id="inputtype_d85185bf4f0d417f834ef38d26263d9e_2_1"> <fieldset aria-describedby="status_d85185bf4f0d417f834ef38d26263d9e_2_1"> <div class="field"> <input type="checkbox" name="input_d85185bf4f0d417f834ef38d26263d9e_2_1[]" id="input_d85185bf4f0d417f834ef38d26263d9e_2_1_choice_0" class="field-input input-checkbox" value="choice_0"/><label id="d85185bf4f0d417f834ef38d26263d9e_2_1-choice_0-label" for="input_d85185bf4f0d417f834ef38d26263d9e_2_1_choice_0" class="response-label field-label label-inline" aria-describedby="status_d85185bf4f0d417f834ef38d26263d9e_2_1"> $z \leq s_2$ (new constraint) </label> </div> <div class="field"> <input type="checkbox" name="input_d85185bf4f0d417f834ef38d26263d9e_2_1[]" id="input_d85185bf4f0d417f834ef38d26263d9e_2_1_choice_1" class="field-input input-checkbox" value="choice_1"/><label id="d85185bf4f0d417f834ef38d26263d9e_2_1-choice_1-label" for="input_d85185bf4f0d417f834ef38d26263d9e_2_1_choice_1" class="response-label field-label label-inline" aria-describedby="status_d85185bf4f0d417f834ef38d26263d9e_2_1"> $z \geq s_2$ (new constraint) </label> </div> <div class="field"> <input type="checkbox" name="input_d85185bf4f0d417f834ef38d26263d9e_2_1[]" id="input_d85185bf4f0d417f834ef38d26263d9e_2_1_choice_2" class="field-input input-checkbox" value="choice_2"/><label id="d85185bf4f0d417f834ef38d26263d9e_2_1-choice_2-label" for="input_d85185bf4f0d417f834ef38d26263d9e_2_1_choice_2" class="response-label field-label label-inline" aria-describedby="status_d85185bf4f0d417f834ef38d26263d9e_2_1"> $z \leq s_5$ (new constraint) </label> </div> <div class="field"> <input type="checkbox" name="input_d85185bf4f0d417f834ef38d26263d9e_2_1[]" id="input_d85185bf4f0d417f834ef38d26263d9e_2_1_choice_3" class="field-input input-checkbox" value="choice_3"/><label id="d85185bf4f0d417f834ef38d26263d9e_2_1-choice_3-label" for="input_d85185bf4f0d417f834ef38d26263d9e_2_1_choice_3" class="response-label field-label label-inline" aria-describedby="status_d85185bf4f0d417f834ef38d26263d9e_2_1"> $z \geq s_5$ (new constraint) </label> </div> <div class="field"> <input type="checkbox" name="input_d85185bf4f0d417f834ef38d26263d9e_2_1[]" id="input_d85185bf4f0d417f834ef38d26263d9e_2_1_choice_4" class="field-input input-checkbox" value="choice_4"/><label id="d85185bf4f0d417f834ef38d26263d9e_2_1-choice_4-label" for="input_d85185bf4f0d417f834ef38d26263d9e_2_1_choice_4" class="response-label field-label label-inline" aria-describedby="status_d85185bf4f0d417f834ef38d26263d9e_2_1"> $z \leq s_7$ (new constraint) </label> </div> <div class="field"> <input type="checkbox" name="input_d85185bf4f0d417f834ef38d26263d9e_2_1[]" id="input_d85185bf4f0d417f834ef38d26263d9e_2_1_choice_5" class="field-input input-checkbox" value="choice_5"/><label id="d85185bf4f0d417f834ef38d26263d9e_2_1-choice_5-label" for="input_d85185bf4f0d417f834ef38d26263d9e_2_1_choice_5" class="response-label field-label label-inline" aria-describedby="status_d85185bf4f0d417f834ef38d26263d9e_2_1"> $z \geq s_7$ (new constraint) </label> </div> <div class="field"> <input type="checkbox" name="input_d85185bf4f0d417f834ef38d26263d9e_2_1[]" id="input_d85185bf4f0d417f834ef38d26263d9e_2_1_choice_6" class="field-input input-checkbox" value="choice_6"/><label id="d85185bf4f0d417f834ef38d26263d9e_2_1-choice_6-label" for="input_d85185bf4f0d417f834ef38d26263d9e_2_1_choice_6" class="response-label field-label label-inline" aria-describedby="status_d85185bf4f0d417f834ef38d26263d9e_2_1"> $x_1 + x_2 + x_5 + x_6 + x_7 + s_2 = 13$ (replace constraint 2) </label> </div> <div class="field"> <input type="checkbox" name="input_d85185bf4f0d417f834ef38d26263d9e_2_1[]" id="input_d85185bf4f0d417f834ef38d26263d9e_2_1_choice_7" class="field-input input-checkbox" value="choice_7"/><label id="d85185bf4f0d417f834ef38d26263d9e_2_1-choice_7-label" for="input_d85185bf4f0d417f834ef38d26263d9e_2_1_choice_7" class="response-label field-label label-inline" aria-describedby="status_d85185bf4f0d417f834ef38d26263d9e_2_1"> $x_1 + x_2 + x_5 + x_6 + x_7 - s_2 = 13$ (replace constraint 2) </label> </div> <div class="field"> <input type="checkbox" name="input_d85185bf4f0d417f834ef38d26263d9e_2_1[]" id="input_d85185bf4f0d417f834ef38d26263d9e_2_1_choice_8" class="field-input input-checkbox" value="choice_8"/><label id="d85185bf4f0d417f834ef38d26263d9e_2_1-choice_8-label" for="input_d85185bf4f0d417f834ef38d26263d9e_2_1_choice_8" class="response-label field-label label-inline" aria-describedby="status_d85185bf4f0d417f834ef38d26263d9e_2_1"> $x_1 + x_2 + x_3 + x_4 + x_5 + s_5 = 14$ (replace constraint 5) </label> </div> <div class="field"> <input type="checkbox" name="input_d85185bf4f0d417f834ef38d26263d9e_2_1[]" id="input_d85185bf4f0d417f834ef38d26263d9e_2_1_choice_9" class="field-input input-checkbox" value="choice_9"/><label id="d85185bf4f0d417f834ef38d26263d9e_2_1-choice_9-label" for="input_d85185bf4f0d417f834ef38d26263d9e_2_1_choice_9" class="response-label field-label label-inline" aria-describedby="status_d85185bf4f0d417f834ef38d26263d9e_2_1"> $x_1 + x_2 + x_3 + x_4 + x_5 - s_5 = 14$ (replace constraint 5) </label> </div> <div class="field"> <input type="checkbox" name="input_d85185bf4f0d417f834ef38d26263d9e_2_1[]" id="input_d85185bf4f0d417f834ef38d26263d9e_2_1_choice_10" class="field-input input-checkbox" value="choice_10"/><label id="d85185bf4f0d417f834ef38d26263d9e_2_1-choice_10-label" for="input_d85185bf4f0d417f834ef38d26263d9e_2_1_choice_10" class="response-label field-label label-inline" aria-describedby="status_d85185bf4f0d417f834ef38d26263d9e_2_1"> $x_3 + x_4 + x_5 + x_6 + x_7 + s_7 = 11$ (replace constraint 7) </label> </div> <div class="field"> <input type="checkbox" name="input_d85185bf4f0d417f834ef38d26263d9e_2_1[]" id="input_d85185bf4f0d417f834ef38d26263d9e_2_1_choice_11" class="field-input input-checkbox" value="choice_11"/><label id="d85185bf4f0d417f834ef38d26263d9e_2_1-choice_11-label" for="input_d85185bf4f0d417f834ef38d26263d9e_2_1_choice_11" class="response-label field-label label-inline" aria-describedby="status_d85185bf4f0d417f834ef38d26263d9e_2_1"> $x_3 + x_4 + x_5 + x_6 + x_7 - s_7 = 11$ (replace constraint 7) </label> </div> <span id="answer_d85185bf4f0d417f834ef38d26263d9e_2_1"/> </fieldset> <div class="indicator-container"> <span class="status unanswered" id="status_d85185bf4f0d417f834ef38d26263d9e_2_1" data-tooltip="Not yet answered."> <span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/> </span> </div> </div></div> <div class="solution-span"> <span id="solution_d85185bf4f0d417f834ef38d26263d9e_solution_1"/> </div></div> <div class="action"> <input type="hidden" name="problem_id" value="PART B" /> <div class="submit-attempt-container"> <button type="button" class="submit btn-brand" data-submitting="Submitting" data-value="Submit" data-should-enable-submit-button="True" aria-describedby="submission_feedback_d85185bf4f0d417f834ef38d26263d9e" > <span class="submit-label">Submit</span> </button> <div class="submission-feedback" id="submission_feedback_d85185bf4f0d417f834ef38d26263d9e"> <span class="sr">Some problems have options such as save, reset, hints, or show answer. These options follow the Submit button.</span> </div> </div> <div class="problem-action-buttons-wrapper"> </div> </div> <div class="notification warning notification-gentle-alert is-hidden" tabindex="-1"> <span class="icon fa fa-exclamation-circle" aria-hidden="true"></span> <span class="notification-message" aria-describedby="d85185bf4f0d417f834ef38d26263d9e-problem-title"> </span> <div class="notification-btn-wrapper"> <button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button> </div> </div> <div class="notification warning notification-save is-hidden" tabindex="-1"> <span class="icon fa fa-save" aria-hidden="true"></span> <span class="notification-message" aria-describedby="d85185bf4f0d417f834ef38d26263d9e-problem-title">None </span> <div class="notification-btn-wrapper"> <button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button> </div> </div> <div class="notification general notification-show-answer is-hidden" tabindex="-1"> <span class="icon fa fa-info-circle" aria-hidden="true"></span> <span class="notification-message" aria-describedby="d85185bf4f0d417f834ef38d26263d9e-problem-title">Answers are displayed within the problem </span> <div class="notification-btn-wrapper"> <button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button> </div> </div> </div> " data-graded="True"> <p class="loading-spinner"> <i class="fa fa-spinner fa-pulse fa-2x fa-fw"></i> <span class="sr">Loading…</span> </p> </div> </div> </div> <div class="vert vert-2" data-id="block-v1:MITx+15.053x+3T2016+type@problem+block@829bad51a1a4494c9cc1d30f2a815a40"> <div class="xblock xblock-public_view xblock-public_view-problem xmodule_display xmodule_ProblemBlock" data-usage-id="block-v1:MITx+15.053x+3T2016+type@problem+block@829bad51a1a4494c9cc1d30f2a815a40" data-block-type="problem" data-graded="True" data-course-id="course-v1:MITx+15.053x+3T2016" data-has-score="True" data-request-token="a7efc0db852911ef8f57023e4242adeb" data-init="XBlockToXModuleShim" data-runtime-class="LmsRuntime" data-runtime-version="1"> <script type="json/xblock-args" class="xblock-json-init-args"> {"xmodule-type": "Problem"} </script> <div id="problem_829bad51a1a4494c9cc1d30f2a815a40" class="problems-wrapper" role="group" aria-labelledby="829bad51a1a4494c9cc1d30f2a815a40-problem-title" data-problem-id="block-v1:MITx+15.053x+3T2016+type@problem+block@829bad51a1a4494c9cc1d30f2a815a40" data-url="/courses/course-v1:MITx+15.053x+3T2016/xblock/block-v1:MITx+15.053x+3T2016+type@problem+block@829bad51a1a4494c9cc1d30f2a815a40/handler/xmodule_handler" data-problem-score="0.0" data-problem-total-possible="1.0" data-attempts-used="0" data-content=" <h3 class="hd hd-3 problem-header" id="829bad51a1a4494c9cc1d30f2a815a40-problem-title" aria-describedby="block-v1:MITx+15.053x+3T2016+type@problem+block@829bad51a1a4494c9cc1d30f2a815a40-problem-progress" tabindex="-1"> PART C </h3> <div class="problem-progress" id="block-v1:MITx+15.053x+3T2016+type@problem+block@829bad51a1a4494c9cc1d30f2a815a40-problem-progress"></div> <div class="problem"> <div> <p> Let $ s_1 $ be the number of excess workers on Monday. Suppose that there is a penalty for having too many workers on Monday. The linear penalty due to $s_1 $ is 0.1. That is, there is no penalty for having 17 workers; there is a penalty of 0.1 for having 18 workers; there is a penalty of 0.2 for having 19 workers (0.1 for both the 18th and 19th workers). The penalty increases if there are more than 19 workers. Here the linear penalty is .25 per worker. For example, if there are 20 workers, the total penalty is .45, which includes a penalty of .25 for the 20th worker. The objective function is to minimize the penalty cost for extra workers on Monday. Let $s_1^{'} $ be the surplus for the first 2 extra workers and $s_1^{''}$ be the surplus for extra workers more than two. Thus $s_1=s_1^{'}+s_1{''}$.</p> <div class="wrapper-problem-response" tabindex="-1" aria-label="Question 1" role="group"><div class="choicegroup capa_inputtype" id="inputtype_829bad51a1a4494c9cc1d30f2a815a40_2_1"> <fieldset aria-describedby="status_829bad51a1a4494c9cc1d30f2a815a40_2_1"> <legend id="829bad51a1a4494c9cc1d30f2a815a40_2_1-legend" class="response-fieldset-legend field-group-hd">What would the new objective function be?</legend> <div class="field"> <input type="checkbox" name="input_829bad51a1a4494c9cc1d30f2a815a40_2_1[]" id="input_829bad51a1a4494c9cc1d30f2a815a40_2_1_choice_0" class="field-input input-checkbox" value="choice_0"/><label id="829bad51a1a4494c9cc1d30f2a815a40_2_1-choice_0-label" for="input_829bad51a1a4494c9cc1d30f2a815a40_2_1_choice_0" class="response-label field-label label-inline" aria-describedby="status_829bad51a1a4494c9cc1d30f2a815a40_2_1"> $\text{MIN } 0.1s_1{'} + 0.25s_1^{''}$ </label> </div> <div class="field"> <input type="checkbox" name="input_829bad51a1a4494c9cc1d30f2a815a40_2_1[]" id="input_829bad51a1a4494c9cc1d30f2a815a40_2_1_choice_1" class="field-input input-checkbox" value="choice_1"/><label id="829bad51a1a4494c9cc1d30f2a815a40_2_1-choice_1-label" for="input_829bad51a1a4494c9cc1d30f2a815a40_2_1_choice_1" class="response-label field-label label-inline" aria-describedby="status_829bad51a1a4494c9cc1d30f2a815a40_2_1"> $\text{MIN } 0.25s_1{'} + 0.1s_1^{''}$ </label> </div> <div class="field"> <input type="checkbox" name="input_829bad51a1a4494c9cc1d30f2a815a40_2_1[]" id="input_829bad51a1a4494c9cc1d30f2a815a40_2_1_choice_2" class="field-input input-checkbox" value="choice_2"/><label id="829bad51a1a4494c9cc1d30f2a815a40_2_1-choice_2-label" for="input_829bad51a1a4494c9cc1d30f2a815a40_2_1_choice_2" class="response-label field-label label-inline" aria-describedby="status_829bad51a1a4494c9cc1d30f2a815a40_2_1"> $\text{MIN } 0.1s_1{'} + 0.1s_1^{''}$ </label> </div> <span id="answer_829bad51a1a4494c9cc1d30f2a815a40_2_1"/> </fieldset> <div class="indicator-container"> <span class="status unanswered" id="status_829bad51a1a4494c9cc1d30f2a815a40_2_1" data-tooltip="Not yet answered."> <span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/> </span> </div> </div></div> <div class="solution-span"> <span id="solution_829bad51a1a4494c9cc1d30f2a815a40_solution_1"/> </div></div> <div class="action"> <input type="hidden" name="problem_id" value="PART C" /> <div class="submit-attempt-container"> <button type="button" class="submit btn-brand" data-submitting="Submitting" data-value="Submit" data-should-enable-submit-button="True" aria-describedby="submission_feedback_829bad51a1a4494c9cc1d30f2a815a40" > <span class="submit-label">Submit</span> </button> <div class="submission-feedback" id="submission_feedback_829bad51a1a4494c9cc1d30f2a815a40"> <span class="sr">Some problems have options such as save, reset, hints, or show answer. These options follow the Submit button.</span> </div> </div> <div class="problem-action-buttons-wrapper"> </div> </div> <div class="notification warning notification-gentle-alert is-hidden" tabindex="-1"> <span class="icon fa fa-exclamation-circle" aria-hidden="true"></span> <span class="notification-message" aria-describedby="829bad51a1a4494c9cc1d30f2a815a40-problem-title"> </span> <div class="notification-btn-wrapper"> <button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button> </div> </div> <div class="notification warning notification-save is-hidden" tabindex="-1"> <span class="icon fa fa-save" aria-hidden="true"></span> <span class="notification-message" aria-describedby="829bad51a1a4494c9cc1d30f2a815a40-problem-title">None </span> <div class="notification-btn-wrapper"> <button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button> </div> </div> <div class="notification general notification-show-answer is-hidden" tabindex="-1"> <span class="icon fa fa-info-circle" aria-hidden="true"></span> <span class="notification-message" aria-describedby="829bad51a1a4494c9cc1d30f2a815a40-problem-title">Answers are displayed within the problem </span> <div class="notification-btn-wrapper"> <button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button> </div> </div> </div> " data-graded="True"> <p class="loading-spinner"> <i class="fa fa-spinner fa-pulse fa-2x fa-fw"></i> <span class="sr">Loading…</span> </p> </div> </div> </div> <div class="vert vert-3" data-id="block-v1:MITx+15.053x+3T2016+type@problem+block@5a8b4e65773a4444a1ad5f77654fc5ba"> <div class="xblock xblock-public_view xblock-public_view-problem xmodule_display xmodule_ProblemBlock" data-usage-id="block-v1:MITx+15.053x+3T2016+type@problem+block@5a8b4e65773a4444a1ad5f77654fc5ba" data-block-type="problem" data-graded="True" data-course-id="course-v1:MITx+15.053x+3T2016" data-has-score="True" data-request-token="a7efc0db852911ef8f57023e4242adeb" data-init="XBlockToXModuleShim" data-runtime-class="LmsRuntime" data-runtime-version="1"> <script type="json/xblock-args" class="xblock-json-init-args"> {"xmodule-type": "Problem"} </script> <div id="problem_5a8b4e65773a4444a1ad5f77654fc5ba" class="problems-wrapper" role="group" aria-labelledby="5a8b4e65773a4444a1ad5f77654fc5ba-problem-title" data-problem-id="block-v1:MITx+15.053x+3T2016+type@problem+block@5a8b4e65773a4444a1ad5f77654fc5ba" data-url="/courses/course-v1:MITx+15.053x+3T2016/xblock/block-v1:MITx+15.053x+3T2016+type@problem+block@5a8b4e65773a4444a1ad5f77654fc5ba/handler/xmodule_handler" data-problem-score="0.0" data-problem-total-possible="1.0" data-attempts-used="0" data-content=" <h3 class="hd hd-3 problem-header" id="5a8b4e65773a4444a1ad5f77654fc5ba-problem-title" aria-describedby="block-v1:MITx+15.053x+3T2016+type@problem+block@5a8b4e65773a4444a1ad5f77654fc5ba-problem-progress" tabindex="-1"> PART D </h3> <div class="problem-progress" id="block-v1:MITx+15.053x+3T2016+type@problem+block@5a8b4e65773a4444a1ad5f77654fc5ba-problem-progress"></div> <div class="problem"> <div> <p>In order to incorporate the requirement in the previous part, what modifications should be made to the Monday constraint (constraint 1)? Select three of the following.</p> <div class="wrapper-problem-response" tabindex="-1" aria-label="Question 1" role="group"><div class="choicegroup capa_inputtype" id="inputtype_5a8b4e65773a4444a1ad5f77654fc5ba_2_1"> <fieldset aria-describedby="status_5a8b4e65773a4444a1ad5f77654fc5ba_2_1"> <div class="field"> <input type="checkbox" name="input_5a8b4e65773a4444a1ad5f77654fc5ba_2_1[]" id="input_5a8b4e65773a4444a1ad5f77654fc5ba_2_1_choice_0" class="field-input input-checkbox" value="choice_0"/><label id="5a8b4e65773a4444a1ad5f77654fc5ba_2_1-choice_0-label" for="input_5a8b4e65773a4444a1ad5f77654fc5ba_2_1_choice_0" class="response-label field-label label-inline" aria-describedby="status_5a8b4e65773a4444a1ad5f77654fc5ba_2_1"> $x_1 + x_4 + x_5 + x_6 + x_7 - s_1^{'} - s_1^{''} = 17$ </label> </div> <div class="field"> <input type="checkbox" name="input_5a8b4e65773a4444a1ad5f77654fc5ba_2_1[]" id="input_5a8b4e65773a4444a1ad5f77654fc5ba_2_1_choice_1" class="field-input input-checkbox" value="choice_1"/><label id="5a8b4e65773a4444a1ad5f77654fc5ba_2_1-choice_1-label" for="input_5a8b4e65773a4444a1ad5f77654fc5ba_2_1_choice_1" class="response-label field-label label-inline" aria-describedby="status_5a8b4e65773a4444a1ad5f77654fc5ba_2_1"> $x_1 + x_4 + x_5 + x_6 + x_7 - s_1^{'} = 17$ </label> </div> <div class="field"> <input type="checkbox" name="input_5a8b4e65773a4444a1ad5f77654fc5ba_2_1[]" id="input_5a8b4e65773a4444a1ad5f77654fc5ba_2_1_choice_2" class="field-input input-checkbox" value="choice_2"/><label id="5a8b4e65773a4444a1ad5f77654fc5ba_2_1-choice_2-label" for="input_5a8b4e65773a4444a1ad5f77654fc5ba_2_1_choice_2" class="response-label field-label label-inline" aria-describedby="status_5a8b4e65773a4444a1ad5f77654fc5ba_2_1"> $x_1 + x_4 + x_5 + x_6 + x_7 - s_1^{''} = 17$ </label> </div> <div class="field"> <input type="checkbox" name="input_5a8b4e65773a4444a1ad5f77654fc5ba_2_1[]" id="input_5a8b4e65773a4444a1ad5f77654fc5ba_2_1_choice_3" class="field-input input-checkbox" value="choice_3"/><label id="5a8b4e65773a4444a1ad5f77654fc5ba_2_1-choice_3-label" for="input_5a8b4e65773a4444a1ad5f77654fc5ba_2_1_choice_3" class="response-label field-label label-inline" aria-describedby="status_5a8b4e65773a4444a1ad5f77654fc5ba_2_1"> $x_1 + x_4 + x_5 + x_6 + x_7 + s_1^{'} + s_1^{''} = 17$ </label> </div> <div class="field"> <input type="checkbox" name="input_5a8b4e65773a4444a1ad5f77654fc5ba_2_1[]" id="input_5a8b4e65773a4444a1ad5f77654fc5ba_2_1_choice_4" class="field-input input-checkbox" value="choice_4"/><label id="5a8b4e65773a4444a1ad5f77654fc5ba_2_1-choice_4-label" for="input_5a8b4e65773a4444a1ad5f77654fc5ba_2_1_choice_4" class="response-label field-label label-inline" aria-describedby="status_5a8b4e65773a4444a1ad5f77654fc5ba_2_1"> $x_1 + x_4 + x_5 + x_6 + x_7 + s_1^{'} = 17$ </label> </div> <div class="field"> <input type="checkbox" name="input_5a8b4e65773a4444a1ad5f77654fc5ba_2_1[]" id="input_5a8b4e65773a4444a1ad5f77654fc5ba_2_1_choice_5" class="field-input input-checkbox" value="choice_5"/><label id="5a8b4e65773a4444a1ad5f77654fc5ba_2_1-choice_5-label" for="input_5a8b4e65773a4444a1ad5f77654fc5ba_2_1_choice_5" class="response-label field-label label-inline" aria-describedby="status_5a8b4e65773a4444a1ad5f77654fc5ba_2_1"> $x_1 + x_4 + x_5 + x_6 + x_7 + s_1^{''} = 17$ </label> </div> <div class="field"> <input type="checkbox" name="input_5a8b4e65773a4444a1ad5f77654fc5ba_2_1[]" id="input_5a8b4e65773a4444a1ad5f77654fc5ba_2_1_choice_6" class="field-input input-checkbox" value="choice_6"/><label id="5a8b4e65773a4444a1ad5f77654fc5ba_2_1-choice_6-label" for="input_5a8b4e65773a4444a1ad5f77654fc5ba_2_1_choice_6" class="response-label field-label label-inline" aria-describedby="status_5a8b4e65773a4444a1ad5f77654fc5ba_2_1"> $0 \leq s_1^{'} \leq 2$ </label> </div> <div class="field"> <input type="checkbox" name="input_5a8b4e65773a4444a1ad5f77654fc5ba_2_1[]" id="input_5a8b4e65773a4444a1ad5f77654fc5ba_2_1_choice_7" class="field-input input-checkbox" value="choice_7"/><label id="5a8b4e65773a4444a1ad5f77654fc5ba_2_1-choice_7-label" for="input_5a8b4e65773a4444a1ad5f77654fc5ba_2_1_choice_7" class="response-label field-label label-inline" aria-describedby="status_5a8b4e65773a4444a1ad5f77654fc5ba_2_1"> $s_1^{''} \geq 0$ </label> </div> <div class="field"> <input type="checkbox" name="input_5a8b4e65773a4444a1ad5f77654fc5ba_2_1[]" id="input_5a8b4e65773a4444a1ad5f77654fc5ba_2_1_choice_8" class="field-input input-checkbox" value="choice_8"/><label id="5a8b4e65773a4444a1ad5f77654fc5ba_2_1-choice_8-label" for="input_5a8b4e65773a4444a1ad5f77654fc5ba_2_1_choice_8" class="response-label field-label label-inline" aria-describedby="status_5a8b4e65773a4444a1ad5f77654fc5ba_2_1"> $s_1^{''} \geq 2$ </label> </div> <span id="answer_5a8b4e65773a4444a1ad5f77654fc5ba_2_1"/> </fieldset> <div class="indicator-container"> <span class="status unanswered" id="status_5a8b4e65773a4444a1ad5f77654fc5ba_2_1" data-tooltip="Not yet answered."> <span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/> </span> </div> </div></div> <div class="solution-span"> <span id="solution_5a8b4e65773a4444a1ad5f77654fc5ba_solution_1"/> </div></div> <div class="action"> <input type="hidden" name="problem_id" value="PART D" /> <div class="submit-attempt-container"> <button type="button" class="submit btn-brand" data-submitting="Submitting" data-value="Submit" data-should-enable-submit-button="True" aria-describedby="submission_feedback_5a8b4e65773a4444a1ad5f77654fc5ba" > <span class="submit-label">Submit</span> </button> <div class="submission-feedback" id="submission_feedback_5a8b4e65773a4444a1ad5f77654fc5ba"> <span class="sr">Some problems have options such as save, reset, hints, or show answer. These options follow the Submit button.</span> </div> </div> <div class="problem-action-buttons-wrapper"> </div> </div> <div class="notification warning notification-gentle-alert is-hidden" tabindex="-1"> <span class="icon fa fa-exclamation-circle" aria-hidden="true"></span> <span class="notification-message" aria-describedby="5a8b4e65773a4444a1ad5f77654fc5ba-problem-title"> </span> <div class="notification-btn-wrapper"> <button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button> </div> </div> <div class="notification warning notification-save is-hidden" tabindex="-1"> <span class="icon fa fa-save" aria-hidden="true"></span> <span class="notification-message" aria-describedby="5a8b4e65773a4444a1ad5f77654fc5ba-problem-title">None </span> <div class="notification-btn-wrapper"> <button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button> </div> </div> <div class="notification general notification-show-answer is-hidden" tabindex="-1"> <span class="icon fa fa-info-circle" aria-hidden="true"></span> <span class="notification-message" aria-describedby="5a8b4e65773a4444a1ad5f77654fc5ba-problem-title">Answers are displayed within the problem </span> <div class="notification-btn-wrapper"> <button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button> </div> </div> </div> " data-graded="True"> <p class="loading-spinner"> <i class="fa fa-spinner fa-pulse fa-2x fa-fw"></i> <span class="sr">Loading…</span> </p> </div> </div> </div> <div class="vert vert-4" data-id="block-v1:MITx+15.053x+3T2016+type@problem+block@12580561c0344dc5ba6403855054842c"> <div class="xblock xblock-public_view xblock-public_view-problem xmodule_display xmodule_ProblemBlock" data-usage-id="block-v1:MITx+15.053x+3T2016+type@problem+block@12580561c0344dc5ba6403855054842c" data-block-type="problem" data-graded="True" data-course-id="course-v1:MITx+15.053x+3T2016" data-has-score="True" data-request-token="a7efc0db852911ef8f57023e4242adeb" data-init="XBlockToXModuleShim" data-runtime-class="LmsRuntime" data-runtime-version="1"> <script type="json/xblock-args" class="xblock-json-init-args"> {"xmodule-type": "Problem"} </script> <div id="problem_12580561c0344dc5ba6403855054842c" class="problems-wrapper" role="group" aria-labelledby="12580561c0344dc5ba6403855054842c-problem-title" data-problem-id="block-v1:MITx+15.053x+3T2016+type@problem+block@12580561c0344dc5ba6403855054842c" data-url="/courses/course-v1:MITx+15.053x+3T2016/xblock/block-v1:MITx+15.053x+3T2016+type@problem+block@12580561c0344dc5ba6403855054842c/handler/xmodule_handler" data-problem-score="0.0" data-problem-total-possible="1.0" data-attempts-used="0" data-content=" <h3 class="hd hd-3 problem-header" id="12580561c0344dc5ba6403855054842c-problem-title" aria-describedby="block-v1:MITx+15.053x+3T2016+type@problem+block@12580561c0344dc5ba6403855054842c-problem-progress" tabindex="-1"> PART E </h3> <div class="problem-progress" id="block-v1:MITx+15.053x+3T2016+type@problem+block@12580561c0344dc5ba6403855054842c-problem-progress"></div> <div class="problem"> <div> <p>Suppose we want to minimize the absolute difference between the number of workers who start on Saturday $(x_6)$ and the number of workers who start on Tuesday $(x_2)$. Let $ z $ be the new objective. Which of the following are necessary changes to the original integer program?</p> <div class="wrapper-problem-response" tabindex="-1" aria-label="Question 1" role="group"><div class="choicegroup capa_inputtype" id="inputtype_12580561c0344dc5ba6403855054842c_2_1"> <fieldset aria-describedby="status_12580561c0344dc5ba6403855054842c_2_1"> <div class="field"> <input type="checkbox" name="input_12580561c0344dc5ba6403855054842c_2_1[]" id="input_12580561c0344dc5ba6403855054842c_2_1_choice_0" class="field-input input-checkbox" value="choice_0"/><label id="12580561c0344dc5ba6403855054842c_2_1-choice_0-label" for="input_12580561c0344dc5ba6403855054842c_2_1_choice_0" class="response-label field-label label-inline" aria-describedby="status_12580561c0344dc5ba6403855054842c_2_1"> <text> <td class="equation">\[\left.\begin{array}{rrcl} \min &amp; z \text{ (new objective)}\\ \text {s.t.:} &amp; &amp; &amp; \\ &amp; z \geq x_2 - x_6 \text{ (new constraint)}\\ &amp; z \geq x_6 - x_2 \text{ (new constraint)} \end{array}\right\}\]</td> </text> </label> </div> <div class="field"> <input type="checkbox" name="input_12580561c0344dc5ba6403855054842c_2_1[]" id="input_12580561c0344dc5ba6403855054842c_2_1_choice_1" class="field-input input-checkbox" value="choice_1"/><label id="12580561c0344dc5ba6403855054842c_2_1-choice_1-label" for="input_12580561c0344dc5ba6403855054842c_2_1_choice_1" class="response-label field-label label-inline" aria-describedby="status_12580561c0344dc5ba6403855054842c_2_1"> <text> <td class="equation">\[\left.\begin{array}{rrcl} \max &amp; z \text{ (new objective)}\\ \text {s.t.:} &amp; &amp; &amp; \\ &amp; z \leq x_2 - x_6 \text{ (new constraint)}\\ &amp; z \leq x_6 - x_2 \text{ (new constraint)} \end{array}\right\}\]</td> </text> </label> </div> <div class="field"> <input type="checkbox" name="input_12580561c0344dc5ba6403855054842c_2_1[]" id="input_12580561c0344dc5ba6403855054842c_2_1_choice_2" class="field-input input-checkbox" value="choice_2"/><label id="12580561c0344dc5ba6403855054842c_2_1-choice_2-label" for="input_12580561c0344dc5ba6403855054842c_2_1_choice_2" class="response-label field-label label-inline" aria-describedby="status_12580561c0344dc5ba6403855054842c_2_1"> <text> <td class="equation">\[\left.\begin{array}{rrcl} \min &amp; z \text{ (new objective)}\\ \text {s.t.:} &amp; &amp; &amp; \\ &amp; z \leq x_2 - x_6 \text{ (new constraint)}\\ &amp; z \leq x_6 - x_2 \text{ (new constraint)} \end{array}\right\}\]</td> </text> </label> </div> <div class="field"> <input type="checkbox" name="input_12580561c0344dc5ba6403855054842c_2_1[]" id="input_12580561c0344dc5ba6403855054842c_2_1_choice_3" class="field-input input-checkbox" value="choice_3"/><label id="12580561c0344dc5ba6403855054842c_2_1-choice_3-label" for="input_12580561c0344dc5ba6403855054842c_2_1_choice_3" class="response-label field-label label-inline" aria-describedby="status_12580561c0344dc5ba6403855054842c_2_1"> <text> <td class="equation">\[\left.\begin{array}{rrcl} \max &amp; z \text{ (new objective)}\\ \text {s.t.:} &amp; &amp; &amp; \\ &amp; z \geq x_2 - x_6 \text{ (new constraint)}\\ &amp; z \geq x_6 - x_2 \text{ (new constraint)} \end{array}\right\}\]</td> </text> </label> </div> <span id="answer_12580561c0344dc5ba6403855054842c_2_1"/> </fieldset> <div class="indicator-container"> <span class="status unanswered" id="status_12580561c0344dc5ba6403855054842c_2_1" data-tooltip="Not yet answered."> <span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/> </span> </div> </div></div> <div class="solution-span"> <span id="solution_12580561c0344dc5ba6403855054842c_solution_1"/> </div></div> <div class="action"> <input type="hidden" name="problem_id" value="PART E" /> <div class="submit-attempt-container"> <button type="button" class="submit btn-brand" data-submitting="Submitting" data-value="Submit" data-should-enable-submit-button="True" aria-describedby="submission_feedback_12580561c0344dc5ba6403855054842c" > <span class="submit-label">Submit</span> </button> <div class="submission-feedback" id="submission_feedback_12580561c0344dc5ba6403855054842c"> <span class="sr">Some problems have options such as save, reset, hints, or show answer. These options follow the Submit button.</span> </div> </div> <div class="problem-action-buttons-wrapper"> </div> </div> <div class="notification warning notification-gentle-alert is-hidden" tabindex="-1"> <span class="icon fa fa-exclamation-circle" aria-hidden="true"></span> <span class="notification-message" aria-describedby="12580561c0344dc5ba6403855054842c-problem-title"> </span> <div class="notification-btn-wrapper"> <button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button> </div> </div> <div class="notification warning notification-save is-hidden" tabindex="-1"> <span class="icon fa fa-save" aria-hidden="true"></span> <span class="notification-message" aria-describedby="12580561c0344dc5ba6403855054842c-problem-title">None </span> <div class="notification-btn-wrapper"> <button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button> </div> </div> <div class="notification general notification-show-answer is-hidden" tabindex="-1"> <span class="icon fa fa-info-circle" aria-hidden="true"></span> <span class="notification-message" aria-describedby="12580561c0344dc5ba6403855054842c-problem-title">Answers are displayed within the problem </span> <div class="notification-btn-wrapper"> <button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button> </div> </div> </div> " data-graded="True"> <p class="loading-spinner"> <i class="fa fa-spinner fa-pulse fa-2x fa-fw"></i> <span class="sr">Loading…</span> </p> </div> </div> </div> <div class="vert vert-5" data-id="block-v1:MITx+15.053x+3T2016+type@problem+block@5ed51dc91d5641d8ad0f81824f28d746"> <div class="xblock xblock-public_view xblock-public_view-problem xmodule_display xmodule_ProblemBlock" data-usage-id="block-v1:MITx+15.053x+3T2016+type@problem+block@5ed51dc91d5641d8ad0f81824f28d746" data-block-type="problem" data-graded="True" data-course-id="course-v1:MITx+15.053x+3T2016" data-has-score="True" data-request-token="a7efc0db852911ef8f57023e4242adeb" data-init="XBlockToXModuleShim" data-runtime-class="LmsRuntime" data-runtime-version="1"> <script type="json/xblock-args" class="xblock-json-init-args"> {"xmodule-type": "Problem"} </script> <div id="problem_5ed51dc91d5641d8ad0f81824f28d746" class="problems-wrapper" role="group" aria-labelledby="5ed51dc91d5641d8ad0f81824f28d746-problem-title" data-problem-id="block-v1:MITx+15.053x+3T2016+type@problem+block@5ed51dc91d5641d8ad0f81824f28d746" data-url="/courses/course-v1:MITx+15.053x+3T2016/xblock/block-v1:MITx+15.053x+3T2016+type@problem+block@5ed51dc91d5641d8ad0f81824f28d746/handler/xmodule_handler" data-problem-score="0.0" data-problem-total-possible="1.0" data-attempts-used="0" data-content=" <h3 class="hd hd-3 problem-header" id="5ed51dc91d5641d8ad0f81824f28d746-problem-title" aria-describedby="block-v1:MITx+15.053x+3T2016+type@problem+block@5ed51dc91d5641d8ad0f81824f28d746-problem-progress" tabindex="-1"> PART F </h3> <div class="problem-progress" id="block-v1:MITx+15.053x+3T2016+type@problem+block@5ed51dc91d5641d8ad0f81824f28d746-problem-progress"></div> <div class="problem"> <div> <p>Suppose that we added the constraint that $ x_i \leq 19 $ for each $i=1,\ldots,7$. </p> <p>Would this change the feasible region?</p> <p>Hint: You'll need to check the original formulation.</p> <div class="wrapper-problem-response" tabindex="-1" aria-label="Question 1" role="group"><div class="choicegroup capa_inputtype" id="inputtype_5ed51dc91d5641d8ad0f81824f28d746_2_1"> <fieldset aria-describedby="status_5ed51dc91d5641d8ad0f81824f28d746_2_1"> <div class="field"> <input type="radio" name="input_5ed51dc91d5641d8ad0f81824f28d746_2_1" id="input_5ed51dc91d5641d8ad0f81824f28d746_2_1_choice_3eaB" class="field-input input-radio" value="choice_3eaB"/><label id="5ed51dc91d5641d8ad0f81824f28d746_2_1-choice_3eaB-label" for="input_5ed51dc91d5641d8ad0f81824f28d746_2_1_choice_3eaB" class="response-label field-label label-inline" aria-describedby="status_5ed51dc91d5641d8ad0f81824f28d746_2_1"> No </label> </div> <div class="field"> <input type="radio" name="input_5ed51dc91d5641d8ad0f81824f28d746_2_1" id="input_5ed51dc91d5641d8ad0f81824f28d746_2_1_choice_3eaA" class="field-input input-radio" value="choice_3eaA"/><label id="5ed51dc91d5641d8ad0f81824f28d746_2_1-choice_3eaA-label" for="input_5ed51dc91d5641d8ad0f81824f28d746_2_1_choice_3eaA" class="response-label field-label label-inline" aria-describedby="status_5ed51dc91d5641d8ad0f81824f28d746_2_1"> Yes </label> </div> <span id="answer_5ed51dc91d5641d8ad0f81824f28d746_2_1"/> </fieldset> <div class="indicator-container"> <span class="status unanswered" id="status_5ed51dc91d5641d8ad0f81824f28d746_2_1" data-tooltip="Not yet answered."> <span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/> </span> </div> </div></div> <div class="solution-span"> <span id="solution_5ed51dc91d5641d8ad0f81824f28d746_solution_1"/> </div></div> <div class="action"> <input type="hidden" name="problem_id" value="PART F" /> <div class="submit-attempt-container"> <button type="button" class="submit btn-brand" data-submitting="Submitting" data-value="Submit" data-should-enable-submit-button="True" aria-describedby="submission_feedback_5ed51dc91d5641d8ad0f81824f28d746" > <span class="submit-label">Submit</span> </button> <div class="submission-feedback" id="submission_feedback_5ed51dc91d5641d8ad0f81824f28d746"> <span class="sr">Some problems have options such as save, reset, hints, or show answer. These options follow the Submit button.</span> </div> </div> <div class="problem-action-buttons-wrapper"> </div> </div> <div class="notification warning notification-gentle-alert is-hidden" tabindex="-1"> <span class="icon fa fa-exclamation-circle" aria-hidden="true"></span> <span class="notification-message" aria-describedby="5ed51dc91d5641d8ad0f81824f28d746-problem-title"> </span> <div class="notification-btn-wrapper"> <button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button> </div> </div> <div class="notification warning notification-save is-hidden" tabindex="-1"> <span class="icon fa fa-save" aria-hidden="true"></span> <span class="notification-message" aria-describedby="5ed51dc91d5641d8ad0f81824f28d746-problem-title">None </span> <div class="notification-btn-wrapper"> <button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button> </div> </div> <div class="notification general notification-show-answer is-hidden" tabindex="-1"> <span class="icon fa fa-info-circle" aria-hidden="true"></span> <span class="notification-message" aria-describedby="5ed51dc91d5641d8ad0f81824f28d746-problem-title">Answers are displayed within the problem </span> <div class="notification-btn-wrapper"> <button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button> </div> </div> </div> " data-graded="True"> <p class="loading-spinner"> <i class="fa fa-spinner fa-pulse fa-2x fa-fw"></i> <span class="sr">Loading…</span> </p> </div> </div> </div> <div class="vert vert-6" data-id="block-v1:MITx+15.053x+3T2016+type@problem+block@7c66b4b5ed33426db47113165505634e"> <div class="xblock xblock-public_view xblock-public_view-problem xmodule_display xmodule_ProblemBlock" data-usage-id="block-v1:MITx+15.053x+3T2016+type@problem+block@7c66b4b5ed33426db47113165505634e" data-block-type="problem" data-graded="True" data-course-id="course-v1:MITx+15.053x+3T2016" data-has-score="True" data-request-token="a7efc0db852911ef8f57023e4242adeb" data-init="XBlockToXModuleShim" data-runtime-class="LmsRuntime" data-runtime-version="1"> <script type="json/xblock-args" class="xblock-json-init-args"> {"xmodule-type": "Problem"} </script> <div id="problem_7c66b4b5ed33426db47113165505634e" class="problems-wrapper" role="group" aria-labelledby="7c66b4b5ed33426db47113165505634e-problem-title" data-problem-id="block-v1:MITx+15.053x+3T2016+type@problem+block@7c66b4b5ed33426db47113165505634e" data-url="/courses/course-v1:MITx+15.053x+3T2016/xblock/block-v1:MITx+15.053x+3T2016+type@problem+block@7c66b4b5ed33426db47113165505634e/handler/xmodule_handler" data-problem-score="0.0" data-problem-total-possible="1.0" data-attempts-used="0" data-content=" <h3 class="hd hd-3 problem-header" id="7c66b4b5ed33426db47113165505634e-problem-title" aria-describedby="block-v1:MITx+15.053x+3T2016+type@problem+block@7c66b4b5ed33426db47113165505634e-problem-progress" tabindex="-1"> PART G </h3> <div class="problem-progress" id="block-v1:MITx+15.053x+3T2016+type@problem+block@7c66b4b5ed33426db47113165505634e-problem-progress"></div> <div class="problem"> <div> <p>Would this change the optimal solution?</p> <div class="wrapper-problem-response" tabindex="-1" aria-label="Question 1" role="group"><div class="choicegroup capa_inputtype" id="inputtype_7c66b4b5ed33426db47113165505634e_2_1"> <fieldset aria-describedby="status_7c66b4b5ed33426db47113165505634e_2_1"> <div class="field"> <input type="radio" name="input_7c66b4b5ed33426db47113165505634e_2_1" id="input_7c66b4b5ed33426db47113165505634e_2_1_choice_3ebB" class="field-input input-radio" value="choice_3ebB"/><label id="7c66b4b5ed33426db47113165505634e_2_1-choice_3ebB-label" for="input_7c66b4b5ed33426db47113165505634e_2_1_choice_3ebB" class="response-label field-label label-inline" aria-describedby="status_7c66b4b5ed33426db47113165505634e_2_1"> No </label> </div> <div class="field"> <input type="radio" name="input_7c66b4b5ed33426db47113165505634e_2_1" id="input_7c66b4b5ed33426db47113165505634e_2_1_choice_3ebA" class="field-input input-radio" value="choice_3ebA"/><label id="7c66b4b5ed33426db47113165505634e_2_1-choice_3ebA-label" for="input_7c66b4b5ed33426db47113165505634e_2_1_choice_3ebA" class="response-label field-label label-inline" aria-describedby="status_7c66b4b5ed33426db47113165505634e_2_1"> Yes </label> </div> <span id="answer_7c66b4b5ed33426db47113165505634e_2_1"/> </fieldset> <div class="indicator-container"> <span class="status unanswered" id="status_7c66b4b5ed33426db47113165505634e_2_1" data-tooltip="Not yet answered."> <span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/> </span> </div> </div></div> <div class="solution-span"> <span id="solution_7c66b4b5ed33426db47113165505634e_solution_1"/> </div></div> <div class="action"> <input type="hidden" name="problem_id" value="PART G" /> <div class="submit-attempt-container"> <button type="button" class="submit btn-brand" data-submitting="Submitting" data-value="Submit" data-should-enable-submit-button="True" aria-describedby="submission_feedback_7c66b4b5ed33426db47113165505634e" > <span class="submit-label">Submit</span> </button> <div class="submission-feedback" id="submission_feedback_7c66b4b5ed33426db47113165505634e"> <span class="sr">Some problems have options such as save, reset, hints, or show answer. These options follow the Submit button.</span> </div> </div> <div class="problem-action-buttons-wrapper"> </div> </div> <div class="notification warning notification-gentle-alert is-hidden" tabindex="-1"> <span class="icon fa fa-exclamation-circle" aria-hidden="true"></span> <span class="notification-message" aria-describedby="7c66b4b5ed33426db47113165505634e-problem-title"> </span> <div class="notification-btn-wrapper"> <button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button> </div> </div> <div class="notification warning notification-save is-hidden" tabindex="-1"> <span class="icon fa fa-save" aria-hidden="true"></span> <span class="notification-message" aria-describedby="7c66b4b5ed33426db47113165505634e-problem-title">None </span> <div class="notification-btn-wrapper"> <button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button> </div> </div> <div class="notification general notification-show-answer is-hidden" tabindex="-1"> <span class="icon fa fa-info-circle" aria-hidden="true"></span> <span class="notification-message" aria-describedby="7c66b4b5ed33426db47113165505634e-problem-title">Answers are displayed within the problem </span> <div class="notification-btn-wrapper"> <button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button> </div> </div> </div> " data-graded="True"> <p class="loading-spinner"> <i class="fa fa-spinner fa-pulse fa-2x fa-fw"></i> <span class="sr">Loading…</span> </p> </div> </div> </div> </div> </div>

<div class="xblock xblock-public_view xblock-public_view-vertical" data-usage-id="block-v1:MITx+15.053x+3T2016+type@vertical+block@8518b7d56a7e47919465a1c53bdcf21a" data-block-type="vertical" data-graded="True" data-course-id="course-v1:MITx+15.053x+3T2016" data-has-score="False" data-request-token="a7efc0db852911ef8f57023e4242adeb" data-init="VerticalStudentView" data-runtime-class="LmsRuntime" data-runtime-version="1"> <h2 class="hd hd-2 unit-title">Problem 5</h2> <div class="vert-mod"> <div class="vert vert-0" data-id="block-v1:MITx+15.053x+3T2016+type@problem+block@b4a7f2b8827a469ebd6a36d9aa64a158"> <div class="xblock xblock-public_view xblock-public_view-problem xmodule_display xmodule_ProblemBlock" data-usage-id="block-v1:MITx+15.053x+3T2016+type@problem+block@b4a7f2b8827a469ebd6a36d9aa64a158" data-block-type="problem" data-graded="True" data-course-id="course-v1:MITx+15.053x+3T2016" data-has-score="True" data-request-token="a7efc0db852911ef8f57023e4242adeb" data-init="XBlockToXModuleShim" data-runtime-class="LmsRuntime" data-runtime-version="1"> <script type="json/xblock-args" class="xblock-json-init-args"> {"xmodule-type": "Problem"} </script> <div id="problem_b4a7f2b8827a469ebd6a36d9aa64a158" class="problems-wrapper" role="group" aria-labelledby="b4a7f2b8827a469ebd6a36d9aa64a158-problem-title" data-problem-id="block-v1:MITx+15.053x+3T2016+type@problem+block@b4a7f2b8827a469ebd6a36d9aa64a158" data-url="/courses/course-v1:MITx+15.053x+3T2016/xblock/block-v1:MITx+15.053x+3T2016+type@problem+block@b4a7f2b8827a469ebd6a36d9aa64a158/handler/xmodule_handler" data-problem-score="0.0" data-problem-total-possible="1.0" data-attempts-used="0" data-content=" <h3 class="hd hd-3 problem-header" id="b4a7f2b8827a469ebd6a36d9aa64a158-problem-title" aria-describedby="block-v1:MITx+15.053x+3T2016+type@problem+block@b4a7f2b8827a469ebd6a36d9aa64a158-problem-progress" tabindex="-1"> PART A </h3> <div class="problem-progress" id="block-v1:MITx+15.053x+3T2016+type@problem+block@b4a7f2b8827a469ebd6a36d9aa64a158-problem-progress"></div> <div class="problem"> <div> <p>This problem will be based on the game of Fiver. It is also sometimes called called Lights Out and you can try your hand at the game <a target="_blank" class="modal-content" href="http://www.logicgamesonline.com/lightsout/"> here </a> and for more details check out the Wikipedia page <a target="_blank" class="modal-content" href="https://en.wikipedia.org/wiki/Lights_Out_(game)"> here. </a></p> <p>Assume we have a 5x5 grid that initially consists of all white blocks. When we click on a block, it flips its color (from white to black or from black to white) and that of adjacent (vertical and horizontal) blocks. Can you make all of the blocks black? The game is illustrated in this figure. For a documented illustration, click <a target="_blank" class="modal-content" href="/assets/courseware/v1/6bc0701a6d5b7bdb610b5b80a6551ddd/asset-v1:MITx+15.053x+3T2016+type@asset+block/Fiver_picture.pdf"> here. </a></p> <p>We wish to write an optimization problem whose solution solves the problem in the fewest moves.</p> <p>We will model it is an integer program. Let $x(i,j)\geq 0$ denote the number of times we click on the block in row $i$ and column $j$.</p> <p>Consider the element in row 3, column 2. Write a constraint that guarantees it turns black.</p> <p> <i>Hint: Consider the outcome when a square is selected $1,2 \text{ or } 3 $ times. </i> </p> <div class="wrapper-problem-response" tabindex="-1" aria-label="Question 1" role="group"><div class="choicegroup capa_inputtype" id="inputtype_b4a7f2b8827a469ebd6a36d9aa64a158_2_1"> <fieldset aria-describedby="status_b4a7f2b8827a469ebd6a36d9aa64a158_2_1"> <div class="field"> <input type="radio" name="input_b4a7f2b8827a469ebd6a36d9aa64a158_2_1" id="input_b4a7f2b8827a469ebd6a36d9aa64a158_2_1_choice_3eaA" class="field-input input-radio" value="choice_3eaA"/><label id="b4a7f2b8827a469ebd6a36d9aa64a158_2_1-choice_3eaA-label" for="input_b4a7f2b8827a469ebd6a36d9aa64a158_2_1_choice_3eaA" class="response-label field-label label-inline" aria-describedby="status_b4a7f2b8827a469ebd6a36d9aa64a158_2_1"> $ x(2,2) + x(3,1) + x(3,2) + x(3,3) + x(4,2) $ is odd </label> </div> <div class="field"> <input type="radio" name="input_b4a7f2b8827a469ebd6a36d9aa64a158_2_1" id="input_b4a7f2b8827a469ebd6a36d9aa64a158_2_1_choice_3eaB" class="field-input input-radio" value="choice_3eaB"/><label id="b4a7f2b8827a469ebd6a36d9aa64a158_2_1-choice_3eaB-label" for="input_b4a7f2b8827a469ebd6a36d9aa64a158_2_1_choice_3eaB" class="response-label field-label label-inline" aria-describedby="status_b4a7f2b8827a469ebd6a36d9aa64a158_2_1"> $ x(2,2) + x(3,1) + x(3,3) + x(4,2) $ is odd </label> </div> <div class="field"> <input type="radio" name="input_b4a7f2b8827a469ebd6a36d9aa64a158_2_1" id="input_b4a7f2b8827a469ebd6a36d9aa64a158_2_1_choice_3eaB" class="field-input input-radio" value="choice_3eaB"/><label id="b4a7f2b8827a469ebd6a36d9aa64a158_2_1-choice_3eaB-label" for="input_b4a7f2b8827a469ebd6a36d9aa64a158_2_1_choice_3eaB" class="response-label field-label label-inline" aria-describedby="status_b4a7f2b8827a469ebd6a36d9aa64a158_2_1"> $ x(2,2) + x(3,1) + x(3,2) + x(3,3) + x(4,2) $ is even </label> </div> <div class="field"> <input type="radio" name="input_b4a7f2b8827a469ebd6a36d9aa64a158_2_1" id="input_b4a7f2b8827a469ebd6a36d9aa64a158_2_1_choice_3eaB" class="field-input input-radio" value="choice_3eaB"/><label id="b4a7f2b8827a469ebd6a36d9aa64a158_2_1-choice_3eaB-label" for="input_b4a7f2b8827a469ebd6a36d9aa64a158_2_1_choice_3eaB" class="response-label field-label label-inline" aria-describedby="status_b4a7f2b8827a469ebd6a36d9aa64a158_2_1"> $ x(2,2) + x(3,1) + x(3,3) + x(4,2) $ is even </label> </div> <span id="answer_b4a7f2b8827a469ebd6a36d9aa64a158_2_1"/> </fieldset> <div class="indicator-container"> <span class="status unanswered" id="status_b4a7f2b8827a469ebd6a36d9aa64a158_2_1" data-tooltip="Not yet answered."> <span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/> </span> </div> </div></div> <div class="solution-span"> <span id="solution_b4a7f2b8827a469ebd6a36d9aa64a158_solution_1"/> </div></div> <div class="action"> <input type="hidden" name="problem_id" value="PART A" /> <div class="submit-attempt-container"> <button type="button" class="submit btn-brand" data-submitting="Submitting" data-value="Submit" data-should-enable-submit-button="True" aria-describedby="submission_feedback_b4a7f2b8827a469ebd6a36d9aa64a158" > <span class="submit-label">Submit</span> </button> <div class="submission-feedback" id="submission_feedback_b4a7f2b8827a469ebd6a36d9aa64a158"> <span class="sr">Some problems have options such as save, reset, hints, or show answer. These options follow the Submit button.</span> </div> </div> <div class="problem-action-buttons-wrapper"> </div> </div> <div class="notification warning notification-gentle-alert is-hidden" tabindex="-1"> <span class="icon fa fa-exclamation-circle" aria-hidden="true"></span> <span class="notification-message" aria-describedby="b4a7f2b8827a469ebd6a36d9aa64a158-problem-title"> </span> <div class="notification-btn-wrapper"> <button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button> </div> </div> <div class="notification warning notification-save is-hidden" tabindex="-1"> <span class="icon fa fa-save" aria-hidden="true"></span> <span class="notification-message" aria-describedby="b4a7f2b8827a469ebd6a36d9aa64a158-problem-title">None </span> <div class="notification-btn-wrapper"> <button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button> </div> </div> <div class="notification general notification-show-answer is-hidden" tabindex="-1"> <span class="icon fa fa-info-circle" aria-hidden="true"></span> <span class="notification-message" aria-describedby="b4a7f2b8827a469ebd6a36d9aa64a158-problem-title">Answers are displayed within the problem </span> <div class="notification-btn-wrapper"> <button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button> </div> </div> </div> " data-graded="True"> <p class="loading-spinner"> <i class="fa fa-spinner fa-pulse fa-2x fa-fw"></i> <span class="sr">Loading…</span> </p> </div> </div> </div> <div class="vert vert-1" data-id="block-v1:MITx+15.053x+3T2016+type@problem+block@c69b29ec4be747babf9f05a0da7a438e"> <div class="xblock xblock-public_view xblock-public_view-problem xmodule_display xmodule_ProblemBlock" data-usage-id="block-v1:MITx+15.053x+3T2016+type@problem+block@c69b29ec4be747babf9f05a0da7a438e" data-block-type="problem" data-graded="True" data-course-id="course-v1:MITx+15.053x+3T2016" data-has-score="True" data-request-token="a7efc0db852911ef8f57023e4242adeb" data-init="XBlockToXModuleShim" data-runtime-class="LmsRuntime" data-runtime-version="1"> <script type="json/xblock-args" class="xblock-json-init-args"> {"xmodule-type": "Problem"} </script> <div id="problem_c69b29ec4be747babf9f05a0da7a438e" class="problems-wrapper" role="group" aria-labelledby="c69b29ec4be747babf9f05a0da7a438e-problem-title" data-problem-id="block-v1:MITx+15.053x+3T2016+type@problem+block@c69b29ec4be747babf9f05a0da7a438e" data-url="/courses/course-v1:MITx+15.053x+3T2016/xblock/block-v1:MITx+15.053x+3T2016+type@problem+block@c69b29ec4be747babf9f05a0da7a438e/handler/xmodule_handler" data-problem-score="0.0" data-problem-total-possible="1.0" data-attempts-used="0" data-content=" <h3 class="hd hd-3 problem-header" id="c69b29ec4be747babf9f05a0da7a438e-problem-title" aria-describedby="block-v1:MITx+15.053x+3T2016+type@problem+block@c69b29ec4be747babf9f05a0da7a438e-problem-progress" tabindex="-1"> PART B </h3> <div class="problem-progress" id="block-v1:MITx+15.053x+3T2016+type@problem+block@c69b29ec4be747babf9f05a0da7a438e-problem-progress"></div> <div class="problem"> <div> <p>Transform the following constraint into integer linear constraints.</p> <p>$x \text{ is odd }, x \geq 0, x \text{ integer }$</p> <div class="wrapper-problem-response" tabindex="-1" aria-label="Question 1" role="group"><div class="choicegroup capa_inputtype" id="inputtype_c69b29ec4be747babf9f05a0da7a438e_2_1"> <fieldset aria-describedby="status_c69b29ec4be747babf9f05a0da7a438e_2_1"> <div class="field"> <input type="radio" name="input_c69b29ec4be747babf9f05a0da7a438e_2_1" id="input_c69b29ec4be747babf9f05a0da7a438e_2_1_choice_3eaA" class="field-input input-radio" value="choice_3eaA"/><label id="c69b29ec4be747babf9f05a0da7a438e_2_1-choice_3eaA-label" for="input_c69b29ec4be747babf9f05a0da7a438e_2_1_choice_3eaA" class="response-label field-label label-inline" aria-describedby="status_c69b29ec4be747babf9f05a0da7a438e_2_1"> $ x-y=1, x,y \geq 0; x,y \text{ integer } $ </label> </div> <div class="field"> <input type="radio" name="input_c69b29ec4be747babf9f05a0da7a438e_2_1" id="input_c69b29ec4be747babf9f05a0da7a438e_2_1_choice_3eaAB" class="field-input input-radio" value="choice_3eaAB"/><label id="c69b29ec4be747babf9f05a0da7a438e_2_1-choice_3eaAB-label" for="input_c69b29ec4be747babf9f05a0da7a438e_2_1_choice_3eaAB" class="response-label field-label label-inline" aria-describedby="status_c69b29ec4be747babf9f05a0da7a438e_2_1"> $ x-2y=1, x,y \geq 0; x,y \text{ integer } $ </label> </div> <div class="field"> <input type="radio" name="input_c69b29ec4be747babf9f05a0da7a438e_2_1" id="input_c69b29ec4be747babf9f05a0da7a438e_2_1_choice_3eaB" class="field-input input-radio" value="choice_3eaB"/><label id="c69b29ec4be747babf9f05a0da7a438e_2_1-choice_3eaB-label" for="input_c69b29ec4be747babf9f05a0da7a438e_2_1_choice_3eaB" class="response-label field-label label-inline" aria-describedby="status_c69b29ec4be747babf9f05a0da7a438e_2_1"> $ 2x-y=1, x,y \geq 0; x,y \text{ integer } $ </label> </div> <div class="field"> <input type="radio" name="input_c69b29ec4be747babf9f05a0da7a438e_2_1" id="input_c69b29ec4be747babf9f05a0da7a438e_2_1_choice_3eaB" class="field-input input-radio" value="choice_3eaB"/><label id="c69b29ec4be747babf9f05a0da7a438e_2_1-choice_3eaB-label" for="input_c69b29ec4be747babf9f05a0da7a438e_2_1_choice_3eaB" class="response-label field-label label-inline" aria-describedby="status_c69b29ec4be747babf9f05a0da7a438e_2_1"> $ x-2y=1, y \geq x \geq 0; x,y \text{ integer } $ </label> </div> <span id="answer_c69b29ec4be747babf9f05a0da7a438e_2_1"/> </fieldset> <div class="indicator-container"> <span class="status unanswered" id="status_c69b29ec4be747babf9f05a0da7a438e_2_1" data-tooltip="Not yet answered."> <span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/> </span> </div> </div></div> <div class="solution-span"> <span id="solution_c69b29ec4be747babf9f05a0da7a438e_solution_1"/> </div></div> <div class="action"> <input type="hidden" name="problem_id" value="PART B" /> <div class="submit-attempt-container"> <button type="button" class="submit btn-brand" data-submitting="Submitting" data-value="Submit" data-should-enable-submit-button="True" aria-describedby="submission_feedback_c69b29ec4be747babf9f05a0da7a438e" > <span class="submit-label">Submit</span> </button> <div class="submission-feedback" id="submission_feedback_c69b29ec4be747babf9f05a0da7a438e"> <span class="sr">Some problems have options such as save, reset, hints, or show answer. These options follow the Submit button.</span> </div> </div> <div class="problem-action-buttons-wrapper"> </div> </div> <div class="notification warning notification-gentle-alert is-hidden" tabindex="-1"> <span class="icon fa fa-exclamation-circle" aria-hidden="true"></span> <span class="notification-message" aria-describedby="c69b29ec4be747babf9f05a0da7a438e-problem-title"> </span> <div class="notification-btn-wrapper"> <button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button> </div> </div> <div class="notification warning notification-save is-hidden" tabindex="-1"> <span class="icon fa fa-save" aria-hidden="true"></span> <span class="notification-message" aria-describedby="c69b29ec4be747babf9f05a0da7a438e-problem-title">None </span> <div class="notification-btn-wrapper"> <button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button> </div> </div> <div class="notification general notification-show-answer is-hidden" tabindex="-1"> <span class="icon fa fa-info-circle" aria-hidden="true"></span> <span class="notification-message" aria-describedby="c69b29ec4be747babf9f05a0da7a438e-problem-title">Answers are displayed within the problem </span> <div class="notification-btn-wrapper"> <button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button> </div> </div> </div> " data-graded="True"> <p class="loading-spinner"> <i class="fa fa-spinner fa-pulse fa-2x fa-fw"></i> <span class="sr">Loading…</span> </p> </div> </div> </div> <div class="vert vert-2" data-id="block-v1:MITx+15.053x+3T2016+type@problem+block@0413029130384c4ea31b6327e774ef42"> <div class="xblock xblock-public_view xblock-public_view-problem xmodule_display xmodule_ProblemBlock" data-usage-id="block-v1:MITx+15.053x+3T2016+type@problem+block@0413029130384c4ea31b6327e774ef42" data-block-type="problem" data-graded="True" data-course-id="course-v1:MITx+15.053x+3T2016" data-has-score="True" data-request-token="a7efc0db852911ef8f57023e4242adeb" data-init="XBlockToXModuleShim" data-runtime-class="LmsRuntime" data-runtime-version="1"> <script type="json/xblock-args" class="xblock-json-init-args"> {"xmodule-type": "Problem"} </script> <div id="problem_0413029130384c4ea31b6327e774ef42" class="problems-wrapper" role="group" aria-labelledby="0413029130384c4ea31b6327e774ef42-problem-title" data-problem-id="block-v1:MITx+15.053x+3T2016+type@problem+block@0413029130384c4ea31b6327e774ef42" data-url="/courses/course-v1:MITx+15.053x+3T2016/xblock/block-v1:MITx+15.053x+3T2016+type@problem+block@0413029130384c4ea31b6327e774ef42/handler/xmodule_handler" data-problem-score="0.0" data-problem-total-possible="1.0" data-attempts-used="0" data-content=" <h3 class="hd hd-3 problem-header" id="0413029130384c4ea31b6327e774ef42-problem-title" aria-describedby="block-v1:MITx+15.053x+3T2016+type@problem+block@0413029130384c4ea31b6327e774ef42-problem-progress" tabindex="-1"> PART C </h3> <div class="problem-progress" id="block-v1:MITx+15.053x+3T2016+type@problem+block@0413029130384c4ea31b6327e774ef42-problem-progress"></div> <div class="problem"> <div> <p>Is it always true that in an optimal answer each of the variables $x(i, j)$ will be binary?</p> <div class="wrapper-problem-response" tabindex="-1" aria-label="Question 1" role="group"><div class="choicegroup capa_inputtype" id="inputtype_0413029130384c4ea31b6327e774ef42_2_1"> <fieldset aria-describedby="status_0413029130384c4ea31b6327e774ef42_2_1"> <div class="field"> <input type="radio" name="input_0413029130384c4ea31b6327e774ef42_2_1" id="input_0413029130384c4ea31b6327e774ef42_2_1_choice_3eaA" class="field-input input-radio" value="choice_3eaA"/><label id="0413029130384c4ea31b6327e774ef42_2_1-choice_3eaA-label" for="input_0413029130384c4ea31b6327e774ef42_2_1_choice_3eaA" class="response-label field-label label-inline" aria-describedby="status_0413029130384c4ea31b6327e774ef42_2_1"> False </label> </div> <div class="field"> <input type="radio" name="input_0413029130384c4ea31b6327e774ef42_2_1" id="input_0413029130384c4ea31b6327e774ef42_2_1_choice_3eaAB" class="field-input input-radio" value="choice_3eaAB"/><label id="0413029130384c4ea31b6327e774ef42_2_1-choice_3eaAB-label" for="input_0413029130384c4ea31b6327e774ef42_2_1_choice_3eaAB" class="response-label field-label label-inline" aria-describedby="status_0413029130384c4ea31b6327e774ef42_2_1"> True </label> </div> <span id="answer_0413029130384c4ea31b6327e774ef42_2_1"/> </fieldset> <div class="indicator-container"> <span class="status unanswered" id="status_0413029130384c4ea31b6327e774ef42_2_1" data-tooltip="Not yet answered."> <span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/> </span> </div> </div></div> <div class="solution-span"> <span id="solution_0413029130384c4ea31b6327e774ef42_solution_1"/> </div></div> <div class="action"> <input type="hidden" name="problem_id" value="PART C" /> <div class="submit-attempt-container"> <button type="button" class="submit btn-brand" data-submitting="Submitting" data-value="Submit" data-should-enable-submit-button="True" aria-describedby="submission_feedback_0413029130384c4ea31b6327e774ef42" > <span class="submit-label">Submit</span> </button> <div class="submission-feedback" id="submission_feedback_0413029130384c4ea31b6327e774ef42"> <span class="sr">Some problems have options such as save, reset, hints, or show answer. These options follow the Submit button.</span> </div> </div> <div class="problem-action-buttons-wrapper"> </div> </div> <div class="notification warning notification-gentle-alert is-hidden" tabindex="-1"> <span class="icon fa fa-exclamation-circle" aria-hidden="true"></span> <span class="notification-message" aria-describedby="0413029130384c4ea31b6327e774ef42-problem-title"> </span> <div class="notification-btn-wrapper"> <button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button> </div> </div> <div class="notification warning notification-save is-hidden" tabindex="-1"> <span class="icon fa fa-save" aria-hidden="true"></span> <span class="notification-message" aria-describedby="0413029130384c4ea31b6327e774ef42-problem-title">None </span> <div class="notification-btn-wrapper"> <button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button> </div> </div> <div class="notification general notification-show-answer is-hidden" tabindex="-1"> <span class="icon fa fa-info-circle" aria-hidden="true"></span> <span class="notification-message" aria-describedby="0413029130384c4ea31b6327e774ef42-problem-title">Answers are displayed within the problem </span> <div class="notification-btn-wrapper"> <button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button> </div> </div> </div> " data-graded="True"> <p class="loading-spinner"> <i class="fa fa-spinner fa-pulse fa-2x fa-fw"></i> <span class="sr">Loading…</span> </p> </div> </div> </div> <div class="vert vert-3" data-id="block-v1:MITx+15.053x+3T2016+type@problem+block@7e62fe99d7214e03862c8678a7e74349"> <div class="xblock xblock-public_view xblock-public_view-problem xmodule_display xmodule_ProblemBlock" data-usage-id="block-v1:MITx+15.053x+3T2016+type@problem+block@7e62fe99d7214e03862c8678a7e74349" data-block-type="problem" data-graded="True" data-course-id="course-v1:MITx+15.053x+3T2016" data-has-score="True" data-request-token="a7efc0db852911ef8f57023e4242adeb" data-init="XBlockToXModuleShim" data-runtime-class="LmsRuntime" data-runtime-version="1"> <script type="json/xblock-args" class="xblock-json-init-args"> {"xmodule-type": "Problem"} </script> <div id="problem_7e62fe99d7214e03862c8678a7e74349" class="problems-wrapper" role="group" aria-labelledby="7e62fe99d7214e03862c8678a7e74349-problem-title" data-problem-id="block-v1:MITx+15.053x+3T2016+type@problem+block@7e62fe99d7214e03862c8678a7e74349" data-url="/courses/course-v1:MITx+15.053x+3T2016/xblock/block-v1:MITx+15.053x+3T2016+type@problem+block@7e62fe99d7214e03862c8678a7e74349/handler/xmodule_handler" data-problem-score="0.0" data-problem-total-possible="1.0" data-attempts-used="0" data-content=" <h3 class="hd hd-3 problem-header" id="7e62fe99d7214e03862c8678a7e74349-problem-title" aria-describedby="block-v1:MITx+15.053x+3T2016+type@problem+block@7e62fe99d7214e03862c8678a7e74349-problem-progress" tabindex="-1"> PART D </h3> <div class="problem-progress" id="block-v1:MITx+15.053x+3T2016+type@problem+block@7e62fe99d7214e03862c8678a7e74349-problem-progress"></div> <div class="problem"> <div> <p>Consider the element in row 3, column 2 again. Using the results from PARTS A, B, and C, write a constraint that guarantees it turns black. For the answers, assume that there is a constraint \[x(i,j) + x(i,j-1) + x(i,j+1) + x(i-1,j) + x(i+1,j) = w(i, j) \] Assume also that $ x(i', j') $ is binary for all $ i', j' $ and $ y(i, j) \in \{0, 1, 2 \} $ .</p> <div class="wrapper-problem-response" tabindex="-1" aria-label="Question 1" role="group"><div class="choicegroup capa_inputtype" id="inputtype_7e62fe99d7214e03862c8678a7e74349_2_1"> <fieldset aria-describedby="status_7e62fe99d7214e03862c8678a7e74349_2_1"> <div class="field"> <input type="radio" name="input_7e62fe99d7214e03862c8678a7e74349_2_1" id="input_7e62fe99d7214e03862c8678a7e74349_2_1_choice_3eaA" class="field-input input-radio" value="choice_3eaA"/><label id="7e62fe99d7214e03862c8678a7e74349_2_1-choice_3eaA-label" for="input_7e62fe99d7214e03862c8678a7e74349_2_1_choice_3eaA" class="response-label field-label label-inline" aria-describedby="status_7e62fe99d7214e03862c8678a7e74349_2_1"> $w(i, j) +2y(i,j) =1, \text{ for }(i,j)=(3,2)$ </label> </div> <div class="field"> <input type="radio" name="input_7e62fe99d7214e03862c8678a7e74349_2_1" id="input_7e62fe99d7214e03862c8678a7e74349_2_1_choice_3eaA" class="field-input input-radio" value="choice_3eaA"/><label id="7e62fe99d7214e03862c8678a7e74349_2_1-choice_3eaA-label" for="input_7e62fe99d7214e03862c8678a7e74349_2_1_choice_3eaA" class="response-label field-label label-inline" aria-describedby="status_7e62fe99d7214e03862c8678a7e74349_2_1"> $ w(i,j) + 2y(i,j) = -1, \text{ for }(i,j)=(3,2)$. </label> </div> <div class="field"> <input type="radio" name="input_7e62fe99d7214e03862c8678a7e74349_2_1" id="input_7e62fe99d7214e03862c8678a7e74349_2_1_choice_3eaAB" class="field-input input-radio" value="choice_3eaAB"/><label id="7e62fe99d7214e03862c8678a7e74349_2_1-choice_3eaAB-label" for="input_7e62fe99d7214e03862c8678a7e74349_2_1_choice_3eaAB" class="response-label field-label label-inline" aria-describedby="status_7e62fe99d7214e03862c8678a7e74349_2_1"> $ w(i, j) - 2y(i,j) = 1, \text{ for }(i,j)=(3,2)$. </label> </div> <div class="field"> <input type="radio" name="input_7e62fe99d7214e03862c8678a7e74349_2_1" id="input_7e62fe99d7214e03862c8678a7e74349_2_1_choice_3eaA" class="field-input input-radio" value="choice_3eaA"/><label id="7e62fe99d7214e03862c8678a7e74349_2_1-choice_3eaA-label" for="input_7e62fe99d7214e03862c8678a7e74349_2_1_choice_3eaA" class="response-label field-label label-inline" aria-describedby="status_7e62fe99d7214e03862c8678a7e74349_2_1"> $ w(i, j) - 2y(i,j)= -1, \text{ for }(i,j)=(3,2)$. </label> </div> <span id="answer_7e62fe99d7214e03862c8678a7e74349_2_1"/> </fieldset> <div class="indicator-container"> <span class="status unanswered" id="status_7e62fe99d7214e03862c8678a7e74349_2_1" data-tooltip="Not yet answered."> <span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/> </span> </div> </div></div> <div class="solution-span"> <span id="solution_7e62fe99d7214e03862c8678a7e74349_solution_1"/> </div></div> <div class="action"> <input type="hidden" name="problem_id" value="PART D" /> <div class="submit-attempt-container"> <button type="button" class="submit btn-brand" data-submitting="Submitting" data-value="Submit" data-should-enable-submit-button="True" aria-describedby="submission_feedback_7e62fe99d7214e03862c8678a7e74349" > <span class="submit-label">Submit</span> </button> <div class="submission-feedback" id="submission_feedback_7e62fe99d7214e03862c8678a7e74349"> <span class="sr">Some problems have options such as save, reset, hints, or show answer. These options follow the Submit button.</span> </div> </div> <div class="problem-action-buttons-wrapper"> </div> </div> <div class="notification warning notification-gentle-alert is-hidden" tabindex="-1"> <span class="icon fa fa-exclamation-circle" aria-hidden="true"></span> <span class="notification-message" aria-describedby="7e62fe99d7214e03862c8678a7e74349-problem-title"> </span> <div class="notification-btn-wrapper"> <button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button> </div> </div> <div class="notification warning notification-save is-hidden" tabindex="-1"> <span class="icon fa fa-save" aria-hidden="true"></span> <span class="notification-message" aria-describedby="7e62fe99d7214e03862c8678a7e74349-problem-title">None </span> <div class="notification-btn-wrapper"> <button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button> </div> </div> <div class="notification general notification-show-answer is-hidden" tabindex="-1"> <span class="icon fa fa-info-circle" aria-hidden="true"></span> <span class="notification-message" aria-describedby="7e62fe99d7214e03862c8678a7e74349-problem-title">Answers are displayed within the problem </span> <div class="notification-btn-wrapper"> <button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button> </div> </div> </div> " data-graded="True"> <p class="loading-spinner"> <i class="fa fa-spinner fa-pulse fa-2x fa-fw"></i> <span class="sr">Loading…</span> </p> </div> </div> </div> <div class="vert vert-4" data-id="block-v1:MITx+15.053x+3T2016+type@problem+block@178983b0bb4740568d3ca8ca6c03c6be"> <div class="xblock xblock-public_view xblock-public_view-problem xmodule_display xmodule_ProblemBlock" data-usage-id="block-v1:MITx+15.053x+3T2016+type@problem+block@178983b0bb4740568d3ca8ca6c03c6be" data-block-type="problem" data-graded="True" data-course-id="course-v1:MITx+15.053x+3T2016" data-has-score="True" data-request-token="a7efc0db852911ef8f57023e4242adeb" data-init="XBlockToXModuleShim" data-runtime-class="LmsRuntime" data-runtime-version="1"> <script type="json/xblock-args" class="xblock-json-init-args"> {"xmodule-type": "Problem"} </script> <div id="problem_178983b0bb4740568d3ca8ca6c03c6be" class="problems-wrapper" role="group" aria-labelledby="178983b0bb4740568d3ca8ca6c03c6be-problem-title" data-problem-id="block-v1:MITx+15.053x+3T2016+type@problem+block@178983b0bb4740568d3ca8ca6c03c6be" data-url="/courses/course-v1:MITx+15.053x+3T2016/xblock/block-v1:MITx+15.053x+3T2016+type@problem+block@178983b0bb4740568d3ca8ca6c03c6be/handler/xmodule_handler" data-problem-score="0.0" data-problem-total-possible="1.0" data-attempts-used="0" data-content=" <h3 class="hd hd-3 problem-header" id="178983b0bb4740568d3ca8ca6c03c6be-problem-title" aria-describedby="block-v1:MITx+15.053x+3T2016+type@problem+block@178983b0bb4740568d3ca8ca6c03c6be-problem-progress" tabindex="-1"> PART E </h3> <div class="problem-progress" id="block-v1:MITx+15.053x+3T2016+type@problem+block@178983b0bb4740568d3ca8ca6c03c6be-problem-progress"></div> <div class="problem"> <div> <p>Using the formulation suggested by PART A, one can, in principle, write an integer program to optimize the game of fiver. If one did it in the most straightforward manner, there would be 25 different constraints, one for each block. That would take a very long time (and a lot of space) to have to write out in detail. </p> <p> Perhaps one could express it more succinctly in a manner similar to the way that the constraint in PART D is given. Ideally, one would only need to write a constraint for Block$ (i, j) $ and let $ i $ vary from 1 to 5 and let $ j $ vary from 1 to 5. One runs into a difficulty though. The constraint for Blocks (1, 1) includes just three of the $ x $ decision variables. It would be \[ x(1, 1) + x(1, 2) + x(2, 1) - 2y(1, 1) = 1, \] where all four of these variables are binary. (Do you see why $ y(1, 1) $ can be restricted to be binary?) Similarly for Blocks (1, 5), (5, 1) and (5, 5). Other Blocks in which $ i $ or $ j $ = 1 or 5 include 4 decision variables. It would seem difficult to be able to express all 25 constraints very succinctly. However, there is a way to do so. It involves creating "dummy decision variables." How many additional dummy variables do you think are needed? HINT: it is more than 23 and less than 25. (Yes, the previous question was intended as a joke. But now that you know the answer, see if you can figure out a clever way of writing the constraints succinctly if you are allowed the 24 extra dummy variables. This number arises because $ 7^2 - 5^2 = 24 $. The explanation for this exercise will be given when the solutions for the problem set are released.) </p> <div class="wrapper-problem-response" tabindex="-1" aria-label="Question 1" role="group"><div id="formulaequationinput_178983b0bb4740568d3ca8ca6c03c6be_2_1" class="inputtype formulaequationinput"> <div class="unanswered"> <input type="text" name="input_178983b0bb4740568d3ca8ca6c03c6be_2_1" id="input_178983b0bb4740568d3ca8ca6c03c6be_2_1" data-input-id="178983b0bb4740568d3ca8ca6c03c6be_2_1" value="" aria-describedby="status_178983b0bb4740568d3ca8ca6c03c6be_2_1" size="20"/> <span class="trailing_text" id="trailing_text_178983b0bb4740568d3ca8ca6c03c6be_2_1"/> <span class="status unanswered" id="status_178983b0bb4740568d3ca8ca6c03c6be_2_1" data-tooltip="Not yet answered."> <span class="sr">unanswered</span><span class="status-icon" aria-hidden="true"/> </span> <p id="answer_178983b0bb4740568d3ca8ca6c03c6be_2_1" class="answer"/> <div id="input_178983b0bb4740568d3ca8ca6c03c6be_2_1_preview" class="equation">  <img src="/static/images/spinner.bc34f953403f.gif" class="loading" alt="Loading"/> </div> </div> <div class="script_placeholder" data-src="/static/js/capa/src/formula_equation_preview.b1967ab28c31.js"/> </div></div> <div class="solution-span"> <span id="solution_178983b0bb4740568d3ca8ca6c03c6be_solution_1"/> </div></div> <div class="action"> <input type="hidden" name="problem_id" value="PART E" /> <div class="submit-attempt-container"> <button type="button" class="submit btn-brand" data-submitting="Submitting" data-value="Submit" data-should-enable-submit-button="True" aria-describedby="submission_feedback_178983b0bb4740568d3ca8ca6c03c6be" > <span class="submit-label">Submit</span> </button> <div class="submission-feedback" id="submission_feedback_178983b0bb4740568d3ca8ca6c03c6be"> <span class="sr">Some problems have options such as save, reset, hints, or show answer. These options follow the Submit button.</span> </div> </div> <div class="problem-action-buttons-wrapper"> </div> </div> <div class="notification warning notification-gentle-alert is-hidden" tabindex="-1"> <span class="icon fa fa-exclamation-circle" aria-hidden="true"></span> <span class="notification-message" aria-describedby="178983b0bb4740568d3ca8ca6c03c6be-problem-title"> </span> <div class="notification-btn-wrapper"> <button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button> </div> </div> <div class="notification warning notification-save is-hidden" tabindex="-1"> <span class="icon fa fa-save" aria-hidden="true"></span> <span class="notification-message" aria-describedby="178983b0bb4740568d3ca8ca6c03c6be-problem-title">None </span> <div class="notification-btn-wrapper"> <button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button> </div> </div> <div class="notification general notification-show-answer is-hidden" tabindex="-1"> <span class="icon fa fa-info-circle" aria-hidden="true"></span> <span class="notification-message" aria-describedby="178983b0bb4740568d3ca8ca6c03c6be-problem-title">Answers are displayed within the problem </span> <div class="notification-btn-wrapper"> <button type="button" class="btn btn-default btn-small notification-btn review-btn sr">Review</button> </div> </div> </div> " data-graded="True"> <p class="loading-spinner"> <i class="fa fa-spinner fa-pulse fa-2x fa-fw"></i> <span class="sr">Loading…</span> </p> </div> </div> </div> </div> </div>