**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 #1A**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 #1B**Due: Wednesday Feb. 22- The
**fixed-path vehicle refueling problem:**Read this handout and examine two problem instances here**.** - For each
of the two cases in the problem instances here, write your AMPL code to
model the problem instance as a linear program and submit to the AMPL
online service to find the optimal refueling policy and the minimal
refueling cost.
**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.**

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

**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**