// Numbas version: exam_results_page_options {"name": "Branch and Bound - Theory", "extensions": [], "custom_part_types": [{"source": {"pk": 1, "author": {"name": "Christian Lawson-Perfect", "pk": 7}, "edit_page": "/part_type/1/edit"}, "name": "Yes/no", "short_name": "yes-no", "description": "

The student is shown two radio choices: \"Yes\" and \"No\". One of them is correct.

", "help_url": "", "input_widget": "radios", "input_options": {"correctAnswer": "if(eval(settings[\"correct_answer_expr\"]), 0, 1)", "hint": {"static": true, "value": ""}, "choices": {"static": true, "value": ["Yes", "No"]}}, "can_be_gap": true, "can_be_step": true, "marking_script": "mark:\nif(studentanswer=correct_answer,\n correct(),\n incorrect()\n)\n\ninterpreted_answer:\nstudentAnswer=0\n\ncorrect_answer:\nif(eval(settings[\"correct_answer_expr\"]),0,1)", "marking_notes": [{"name": "mark", "description": "This is the main marking note. It should award credit and provide feedback based on the student's answer.", "definition": "if(studentanswer=correct_answer,\n correct(),\n incorrect()\n)"}, {"name": "interpreted_answer", "description": "A value representing the student's answer to this part.", "definition": "studentAnswer=0"}, {"name": "correct_answer", "description": "", "definition": "if(eval(settings[\"correct_answer_expr\"]),0,1)"}], "settings": [{"name": "correct_answer_expr", "label": "Is the answer \"Yes\"?", "help_url": "", "hint": "An expression which evaluates to true or false.", "input_type": "mathematical_expression", "default_value": "true", "subvars": false}], "public_availability": "always", "published": true, "extensions": []}], "resources": [], "navigation": {"allowregen": true, "showfrontpage": false, "preventleave": false, "typeendtoleave": false}, "question_groups": [{"pickingStrategy": "all-ordered", "questions": [{"name": "Branch and Bound - Theory", "tags": [], "metadata": {"description": "", "licence": "None specified"}, "statement": "

Branch and bound is an algorithm for solving optimization problems with integer and binary decision variables.

There are two bounds in the branch and bound algorithm, i.e., an upper and lower bound.

", "advice": "", "rulesets": {}, "extensions": [], "builtin_constants": {"e": true, "pi,\u03c0": true, "i": true}, "constants": [], "variables": {"type": {"name": "type", "group": "Ungrouped variables", "definition": "[ \"maximizing\", \"minimizing\" ]", "description": "", "templateType": "list of strings", "can_override": false}}, "variablesTest": {"condition": "", "maxRuns": 100}, "ungrouped_variables": ["type"], "variable_groups": [], "functions": {}, "preamble": {"js": "", "css": ""}, "parts": [{"type": "1_n_2", "useCustomName": false, "customName": "", "marks": 0, "scripts": {}, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "unitTests": [], "showCorrectAnswer": true, "showFeedbackIcon": true, "variableReplacements": [], "variableReplacementStrategy": "originalfirst", "nextParts": [], "suggestGoingBack": false, "adaptiveMarkingPenalty": 0, "exploreObjective": null, "prompt": "

If we are maximizing the objective function, the relaxed solution is used to initialize which bound?

", "minMarks": 0, "maxMarks": 0, "shuffleChoices": false, "displayType": "radiogroup", "displayColumns": 0, "showCellAnswerState": true, "choices": ["Upper bound", "Lower bound"], "matrix": ["1", 0], "distractors": ["", "Any solution will be inferior to the relaxed solution"]}, {"type": "yes-no", "useCustomName": false, "customName": "", "marks": 1, "scripts": {}, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "unitTests": [], "showCorrectAnswer": true, "showFeedbackIcon": true, "variableReplacements": [], "variableReplacementStrategy": "originalfirst", "nextParts": [], "suggestGoingBack": false, "adaptiveMarkingPenalty": 0, "exploreObjective": null, "prompt": "

In an IP/MIP problem with a maximization objective, is it possible to find a solution during the branch and bound algorithm that exceeds the upper bound

", "settings": {"correct_answer_expr": "false"}}, {"type": "yes-no", "useCustomName": false, "customName": "", "marks": 1, "scripts": {}, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "unitTests": [], "showCorrectAnswer": true, "showFeedbackIcon": true, "variableReplacements": [], "variableReplacementStrategy": "originalfirst", "nextParts": [], "suggestGoingBack": false, "adaptiveMarkingPenalty": 0, "exploreObjective": null, "prompt": "

In an IP/MIP problem with a minimization objective, is it possible to find a solution during the branch and bound algorithm that exceeds the upper bound?

", "settings": {"correct_answer_expr": "true"}}, {"type": "1_n_2", "useCustomName": false, "customName": "", "marks": 0, "scripts": {}, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "unitTests": [], "showCorrectAnswer": true, "showFeedbackIcon": true, "variableReplacements": [], "variableReplacementStrategy": "originalfirst", "nextParts": [], "suggestGoingBack": false, "adaptiveMarkingPenalty": 0, "exploreObjective": null, "prompt": "

In an IP/MIP problem with a maximization objective, the best integer solution is recorded by which bound?

", "minMarks": 0, "maxMarks": 0, "shuffleChoices": true, "displayType": "radiogroup", "displayColumns": 0, "showCellAnswerState": true, "choices": ["Lower bound", "Upper bound"], "matrix": ["1", 0], "distractors": ["", "This is used to store the relaxed solution"]}, {"type": "m_n_2", "useCustomName": false, "customName": "", "marks": 0, "scripts": {}, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "unitTests": [], "showCorrectAnswer": true, "showFeedbackIcon": true, "variableReplacements": [], "variableReplacementStrategy": "originalfirst", "nextParts": [], "suggestGoingBack": false, "adaptiveMarkingPenalty": 0, "exploreObjective": null, "prompt": "

During branch and bound, a node is fathomed/pruned under specific circumstances. Which of the following conditions are valid?

The node produces a non-integer solution better than the current best integer solution

", "The node produces a non-integer solution worse than the current best integer solution"], "matrix": [0, "1", "1", 0, "1"], "distractors": ["", "", "", "", ""]}, {"type": "m_n_2", "useCustomName": false, "customName": "", "marks": 0, "scripts": {}, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "unitTests": [], "showCorrectAnswer": true, "showFeedbackIcon": true, "variableReplacements": [], "variableReplacementStrategy": "originalfirst", "nextParts": [], "suggestGoingBack": false, "adaptiveMarkingPenalty": 0, "exploreObjective": null, "prompt": "

Under what circumstances does branch and bound perform poorly?

", "minMarks": 0, "maxMarks": 0, "shuffleChoices": true, "displayType": "checkbox", "displayColumns": 0, "minAnswers": 0, "maxAnswers": 0, "warningType": "none", "showCellAnswerState": true, "markingMethod": "sum ticked cells", "choices": ["The search tree is small", "The search tree is large", "The lower bound is slow to improve", "The upper bound is slow to improve", "The gap between the upper and lower bound is small", "The gap between the upper and lower bound is large"], "matrix": [0, "1", "1", "1", 0, "1"], "distractors": ["", "", "", "", "", ""]}, {"type": "m_n_2", "useCustomName": false, "customName": "", "marks": 0, "scripts": {}, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "unitTests": [], "showCorrectAnswer": true, "showFeedbackIcon": true, "variableReplacements": [], "variableReplacementStrategy": "originalfirst", "nextParts": [], "suggestGoingBack": false, "adaptiveMarkingPenalty": 0, "exploreObjective": null, "prompt": "

A depth first search in branch and bound has several benefits. Which of the following statements are true?

Progress is made on the upper bound in a minimization problem

", "Progress is made on the upper bound in a maximization problem", "Progress is made on the lower bound in a minimization problem"], "matrix": ["1", "1", 0, 0], "distractors": ["", "", "", ""]}, {"type": "m_n_2", "useCustomName": false, "customName": "", "marks": 0, "scripts": {}, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "unitTests": [], "showCorrectAnswer": true, "showFeedbackIcon": true, "variableReplacements": [], "variableReplacementStrategy": "originalfirst", "nextParts": [], "suggestGoingBack": false, "adaptiveMarkingPenalty": 0, "exploreObjective": null, "prompt": "

A breadth first search in branch and bound has several benefits. Which of the following statements are true?

Progress is made on the upper bound in a minimization problem

", "Progress is made on the upper bound in a maximization problem", "Progress is made on the lower bound in a minimization problem"], "matrix": [0, 0, "1", "1"], "distractors": ["", "", "", ""]}], "partsMode": "all", "maxMarks": 0, "objectives": [], "penalties": [], "objectiveVisibility": "always", "penaltyVisibility": "always", "contributors": [{"name": "Paul Corry", "profile_url": "https://numbas.mathcentre.ac.uk/accounts/profile/8910/"}, {"name": "Robert Burdett", "profile_url": "https://numbas.mathcentre.ac.uk/accounts/profile/17952/"}]}]}], "contributors": [{"name": "Paul Corry", "profile_url": "https://numbas.mathcentre.ac.uk/accounts/profile/8910/"}, {"name": "Robert Burdett", "profile_url": "https://numbas.mathcentre.ac.uk/accounts/profile/17952/"}]}