Sample Response to Discussion Question 3: Model Subsystem
Our last discussion question was to develop an operational concept for
GOAT. For this discussion question, assume that several rounds of
discussion with stakeholders has resulted in agreement on the
operational concept referenced here. Consider Operational Scenario 6, study plan evaluation (also reference supporting Operational Scenario 5, defining goals and constraints).
1. Among the methods we discussed in class, which would be
appropriate for defining this functionality?
The purpose of the model is to support the user’s decision of:
(1) which program of study (major, degree program, certificate, etc.)
to follow; (2) which courses to take among those allowed for the
program of study; and (3) how to schedule the courses.
We define a course instantiation (CI) as a triple (c, s, t), where c is a course, s is a semester, and t is a time slot. We define a fully specified potential plan (FPP) as a finite-length sequence ((c1, s1, t1), ..., (cn, sn, tn)) of course instantiations, and a partially specified potential plan (PPP)
as a set of fully specified potential plans. Our model will be
designed to help the user narrow down an initially very large set of
PPPs under consideration to a much smaller set, and eventually to a
single FPP that satisfies the user's constraints and best achieves her
goals.
It is useful to think of the problem of choosing a good FPP as a
problem in constrained optimization. Constrained optimization methods
try to maximize a utility function (or minimize a loss function) subject to constraints on the set of options. Examples of constraints are:
- The study plan must satisfy the degree requirements for the MSSE degree.
- Prerequisites to a course must be taken prior to the semester in which the course is taken.
- No two different courses can be taken at the same time in the same semester.
The utility function is a mathematical representation of how well a
given option satisfies the user's objectives. Examples of objectives
might include:
- The user prefers not to take classes on Fridays.
- The user would prefer to take SYST 542.
- The user would rather take two courses on the same night than on
different nights, and would prefer the 4:30 time slot if only one
course is being taken on a given night.
Many of the methods we discussed were appropriate for solving
constrained optimization problems. The consensus of the class was
that several of these methods should be combined.
- Multiattribute utility theory could be used to develop a utility function to represent the user's objectives.
- A rule based system or other heuristic search algorithm could be used to narrow the set of PPPs to consider.
- A mathematical programming algorithm could be used to find the
optimum among the remaining PPPs. If the utility function is linear and
the output of the heuristic search is a set defined by linear
constraints, then we can use linear programming to find the optimum.
2. Give a description of the inputs and outputs of a function that
would perform this functionality.
The inputs to the function are:
- Chosen course of study (from scenario 3)
- Course cancellation probabilities (from DSS model)
- Degree requirements (from university database)
- Courses completed by the student (from registrar)
- Waiver approvals (from advisor)
- Prerequisites for necessary courses (from university database)
- User defined goals (from scenario 5)
- Constraints (from scenario 5)
Function outputs are:
- Top 3-5 FPPs depending on user-specified parameters
- Questions to ask user to help refine goals and constraints and narrow down the set of PPP
- Sensitivity analysis
- Automated request for advisor approval
3. How would the function work?
The student has already selected a plan of study in Scenario 3 and
entered goals and constraints in Scenario 5. An algorithm sketch
for step “e” of Scenario 5 follows:
- Initialize parameters to guide the rule-based system's choice of
linearization for the utility function and constraints. Set list
of FPPs to empty list.
- Formulate a linear utility function using the results of Scenario 5, and current linearization parameters.
- Use a rule-based heuristic method for this step.
- It is not immediately clear that we can capture all the
relevant objectives with a linear utility function. See Step 4
below.
- Specify a set of constraints that implicitly defines the PPPs to be considered.
- A rule-based system can do this step heuristically by executing
rules that cut out some parts of the PPP set. For computational
efficiency, we design this system to specify linear constraints.
Some of the constraints may not be linear. In this case, we will
specify an approximate constraint set by linearizing some constraints.
- (An alternate approach was suggested of using a rule-based system to
generate all PPPs without evaluating them, and then applying the
utility function to select the top few PPPs. Except in very
constrained cases, there are likely to be too many for this strategy to
be feasible.)
- Solve the LP to obtain an "optimal" FPP.
- Evaluate the feasibility of the result of Step 3 using the
correct (not linearized) constraints. If infeasible, perform a
heuristic adjustment using a rule-based system to find a feasible
solution. Evalutate utility of solution using correct (not
linearized) utility function. Add to list of FPPs. If
enough FPPs have been generated, go to Step 7; otherwise go to Step 5.
- Decide whether to ask user for additional information to further
constrain or inform search. If yes, go to Scenario 3 to obtain
refined information on goals and constraints.
- Adjust parameters for rule-based constraint and utility function algorithms. Return to Step 1.
- Perform sensitivity analysis.
- A simple and useful sensitivity analysis would display the student’s objectives
and constraints as a series of sliding scales along side the top chosen
FPPs. As they manipulate the importance of various objectives and
constraints the top FPP(s) may change. So they could see the effect of
weighing “no evening classes” more or less versus “graduate in three
years”.
- It is important to have a simple and understandable sensitivity analysis. It will demonstrate to the user that their
preferences give rise to the chosen FPPs. This in turn ensures that
the user sees the system as an extension of mental processes they would
do anyway but easier and more effective. This will be key to user
acceptance and continued use.
Back to SYST 542 homepage