**To the Bottom of the
Page**

Instructor: Dr. Shieu-Hong Lin

Class time: MW 10:30-11:45pm at Grove 4B

Office Hours: M~Th 8:30-10:30 am

Syllabus: compact
version

**Books and references**

********************************************************************************** **

**About the reading
reports:**

· **Effort (2 points):** How much time have you spent in
the reading? What percentage of the contents in the reading do you think you
understand? Have you come to the class this week? **Assessment**: The student is expected to **(i)** have
attended the class this week at least once (0.5 point), and**(ii) have
either **gained a good understanding of **80% or more of the
contents** **or** have spent at least **three hours** in
the reading (1.5 points).

· **Reflection on the reading (2 points)**: Put down 1~2
paragraphs of your thoughts such as notes of new insight you gained,
interesting things encountered, questions of things you don’t understand,
and so forth.** ****Assessment**: the student is expected to show substantial evidence of understanding
or effort of trying to understand the contents in the reading.

********************************************************************************** **

**Week 1: Introduction to Mathematical Programming and
AMPL: Production Models**

**Showcase 1: Optimization
Problems for Vehicle Refueling Planning **

**Showcase 2: Mechanism of a Bidding
Game: Design and Analysis**

**Reading #1**Due Wednesday Feb.8: (i) Introduction and Chapter 1 (production models) of*AMPL: A Modeling Language for Mathematical Programming*(ii) Read this article on linear programming. (iii) Optional: Browse this article on mathematical optimization.

**Enter your report
online under Canvas according to this
format. **

**Lab #1**Due Wednesday Feb.8**Practice**: Visit the online service for mathematical programming using AMPL. First click the submit button. Secondly copy and paste this AMPL sample code on P.5 of Chapter 1 into the input pane of the*model and data*section (the bottom section) of the page. Thirdly solve it for a solution by clicking the*send*button in the*AMPL commands*section.**Submit your work**: Copy and paste the results you got from AMPL into a WORD document and describe any problems you encountered when using AMPL. Upload the WORD document under Canvas.

********************************************************************************** **

**Week 2: More on Linear Programming Using AMPL: Diet
Models**

**Reading #2**Due Wednesday Feb.15- Chapter 1 of
*Strategies and Games: Theory and Practice* - Chapter 2 (diet
models) of
*AMPL: A Modeling Language for Mathematical Programming*

**Lab #2**Due Wednesday Feb.15

·
Explore the continuous
knapsack problem and see an example in 1 about how we can solve
the problem efficiently. As discussed 02/06 in the class, the optimization
problem in the production domain depicted in Chapter 1 of the *AMPL *book can be viewed and
efficiently solved as the continuous knapsack problem without using linear
programming. **Please reflect on how this
and describe how this can be done in your report.**

·
**Show in your report**
how you can apply your understanding of the continuous knapsack problem above to solve the production domain case depicted in the AMPL sample code on P.5 of Chapter 1 without
using linear programming.

**Submit your work**: Upload your report as a WORD document under Canvas.

**Homework #1**Due Wednesday Feb.15**The problem:**Do Exercise 1-1 of*AMPL: A Modeling Language for Mathematical Programming*and submit your work under Canvass as described in the following.**For Part d, the additional constraints there are: at least 2 magazine pages and at most 120 minutes of radios**.**Assignment**: For each part of Exercises 1-1, write down a simple linear program like AMPL sample code on P.5 of Chapter 1 and solve it by submitting your code to the online service for mathematical programming using AMPL as described in Lab#1.**Submission**: Put down all your answers for Exercise 1-1 inside this self-evaluation report (.doc file) and submit the file under Canvas.

**Note:****Examples about the AMPL syntax**: See the original AMPL code here based on diet.mod and diet .dat here. Compare it with the following variants of AMPL code on the diet problem: 1 (in the data section**param amt (tr):**now**param amt:**), 2**j for FOOD, i for NUTR:**changed into**i for FOOD, j for NUTR:**) , 3**and**4 (**index order for param amt[**: in the model section**param amt { NUTR, FOOD}**changed into param amt**{FOOD, NUTR}**so that we use amt[i,j] instead of amt[j,i] in**diet**constraints) .

********************************************************************************** **

**Week 3: More on Linear Programming Using AMPL:
Transportation and Assignment Models**

**Reading #3**Due Wednesday Feb. 22- Chapter 2 of
*Strategies and Games: Theory and Practice* - Chapter 3
(transportation and assignment models) of
*AMPL: A Modeling Language for Mathematical Programming*

**Homework #2**Due: Wednesday Feb. 22 (extended to Saturday 02/25 without penalty)- The
**fixed-path vehicle refueling problem:**Examine two problem instances here and read the general description of the problem in this handout**.** **For each of the two****problem instances**here, write your AMPL code (declare variables and minimize the objective function subject to constraints over the variables in the fashion depicted in Sections 1.1 and 2.1 in the AMPL book) to translate the optimal refueling problem over the problem instance as a linear program. Then submit each linear program to the AMPL online service to find the optimal refueling policy and the minimal refueling cost.**Note that you don’t need to create an AMPL model for this homework.****Just write down plain linear programs in the way depicted in Sections 1.1 and 2.1 in the AMPL book.****Submission**: For each of the problem instances, put down the AMPL code and the optimal refueling policy and the minimal refueling cost determined by the solver inside this self-evaluation report (.doc file) and submit the file under Canvas.

**Notes:****Set cover problem:**The nutrient problem in chapter 2 is related to the set cover problem, which can be viewed as a special case of the nutrient problem where (i) the elements in the universal set*U**S**S*, which corresponds to buying either 1 or r0 package of a particular kind of food, (iv ) finding a minimum number of sets in*U**S*is equivalent to minimize the total food purchasing cost with a uniform price over each package of food.*U***Time complexity**: Read this article on time complexity of algorithms. Download and unzip this C++ project to feel the amount of time taken by O(n), O(n log n), O(n^{2}), and O (n^{5}) algorithms. Try n=1,000,000, n=10,000,000, n=100,000,000, and n=1,000,000,000 and measure the amount of time taken respectively if possible. In practice, the simplex algorithm works well for linear programming**, but the simplex algorithm for linear programming is an exponential-time algorithm in the worst case. There are polynomial-time algorithms (interior-point algorithms) for linear programming.**

********************************************************************************** **

**Week 4: Transportation/Assignment Model + Dominant
Strategies in Strategic Form Games **

**Reading #4**Due Wednesday March 1**Chapter 4****(Building Larger Models)**and**Chapter 5****(Simple Sets and Indexing**) in*AMPL: A Modeling Language for Mathematical Programming*.**Optiona**l: Chapter 3 of*Strategies and Games: Theory and Practice*

·
**Homework #3 **Due:
Wednesday March 8

- Build an AMPL model for the
**fixed-path vehicle refueling problem:**Develop an AMPL model (i.e. something like**prod.mod**in Chapter 1) for solving the**fixed-path vehicle refueling problem. See this template here.**For each of the two cases in the problem instances here, solve the problem instance again by using the AMPL model and specifying the data (in a way like what you see in**prod.dat**in Chapter 1) based on the problem instance. **Note:**It would be an easier task if you**(i)**use a set of numbers 1 to N (with N as a parameter to be specified in the data) to represent the set of fuel stations and**(ii)**explicitly incorporate variables X_{i}, Y_{i}, and Z_{i}in the formulation as mentioned in the handout for the**fixed-path vehicle refueling problem.**Also note that you can use**equality constraints**as well as inequality constraints in your generic model if needed.**Submission**: please put down all your solutions to the two cases above inside this self-evaluation report (updated 03/03/2017) and submit the file under Canvas.

********************************************************************************** **

**Week 5: Dominant Strategies in Strategic Form Games **

**Reading #5**Wednesday March 8- Chapter 3 of
*Strategies and Games: Theory and Practice*. Very carefully read definitions/explanations including 3.1, 3.2, and 3.3 on pages 41~42 on the concepts of “strongly dominant strategies,” “weakly dominant strategies,” and “dominant strategy solutions.” - Read the setting of the first price sealed-bid auction
and the setting of second price
sealed-bid auction.
- Read the linear-time fast algorithm for solving the fixed-path vehicle
refueling problem described in this paper (available under Canvas|File
opf the course): Shieu-Hong
Lin, Nate Gertsch, and Jennifer R. Russell.
*A Linear-time Algorithm for Finding Optimal Vehicle Refueling Policies.*Operations Research Letters, 35:3 (2007), 290-296.

**Homework #4A**due:**Tuesday March 14**(Submission under Canvas**remains open till Wednesday 03/29**with no penalty because of the mission conference)- Review the setting of the first price sealed-bid auction
(version 1) and the setting of second
price sealed-bid auction (version 1) and answer the following
questions:
**(i)**Regarding the first price sealed-bid auction, is there a strategy**for each player**that*i***(weakly or strongly) dominates**(see the definition in Chapter 3 of*Strategies and Games: Theory and Practice*) all other strategies**for player**? If so, describe that strategy and provide a proof that it*i***(weakly or strongly) dominates**all other strategies**for player**. If not, please describe why there is no such strategy.*i***(ii)**Regarding the second price sealed-bid auction, is there a strategy**for each player**that*i***(weakly or strongly) dominates**(see the definition in Chapter 3 of*Strategies and Games: Theory and Practice*) all other strategies**for player**? If so, describe that strategy and provide a proof that it*i***(weakly or strongly) dominates**all other strategies**for player**. If not, please describe why there is no such strategy.*i***(iii)**Is there a**dominant strategy solution**for the auction game under the setting of the first price sealed-bid auction? Is there a**dominant strategy solution**for the auction game under the setting of the second price sealed-bid auction? **Note: 10 points in total.**4, 4, and 2 points for each of the**three questions**above.**Submit your work**: Put down all your answers inside this self-evaluation report (**updated 03/13**) and submit the file under Canvas.

********************************************************************************** **

**Week 6: Dominance Solvability in Strategic Form Games**

**Reading #6**Due Wednesday March 22- Chapter 4 of
*Strategies and Games: Theory and Practice*

**Homework #4B**due: Wednesday**March 29**- Instead of
**version 1**of the first price sealed-bid auction and the second price sealed-bid auction, please consider**version 2**of the first price sealed-bid auction and the second price sealed-bid auction, and answer the same three questions as in**Homework #4A**:**(i)**Regarding the first price sealed-bid auction, is there a strategy**for each player**that*i***(weakly or strongly) dominates**(see the definition in Chapter 3 of*Strategies and Games: Theory and Practice*) all other strategies**for player**? If so, describe that strategy and provide a proof that it*i***(weakly or strongly) dominates**all other strategies**for player**. If not, please describe why there is no such strategy.*i***(ii)**Regarding the second price sealed-bid auction, is there a strategy**for each player**that*i***(weakly or strongly) dominates**(see the definition in Chapter 3 of*Strategies and Games: Theory and Practice*) all other strategies**for player**? If so, describe that strategy and provide a proof that it*i***(weakly or strongly) dominates**all other strategies**for player**. If not, please describe why there is no such strategy.*i***(iii)**Is there a**dominant strategy solution**for the auction game under the setting of the first price sealed-bid auction? Is there a**dominant strategy solution**for the auction game under the setting of the second price sealed-bid auction? **Note: 10 points in total.**4, 4, and 2 points for each of the**three questions**above.**Submit your work**: Put down all your answers inside this self-evaluation report (**updated 03/13**) and submit the file under Canvas.

********************************************************************************** **

**Week 7: Dominance Solvability in Strategic Form Games and
Nash ****Equilibria**

**Reading #7**Due Wednesday**March 29**- Review Chapter 4 of
*Strategies and Games: Theory and Practice***if needed.** - Read Chapter 5 (Nash
equilibria) of
*Strategies and Games: Theory and Practice*.

**Homework #5**Due Wednesday April 5- Answer the questions here regarding the ½
average-guessing game we discussed in the class.
- Put down your answers into
a WORD document ( .doc file) and upload it under Canvas.

**Test #1**: **Wednesday April 12**

******************************************************************************************************* **** **

**Power point class notes** available under **Files** in our Canvas class site.

************************************************************************************

**TA: William Tan.
TA hours in MATH lab: Monday/Wednesday
2:00~3:00pm**

********************************************************************************** **

**To the Top of
the Page**