Department of Computer Engineering

CE 485 | Course Introduction and Application Information

Course Name

Linear and Integer Programming

Code	Semester	Theory (hour/week)	Application/Lab (hour/week)	Local Credits	ECTS
CE 485	FALL	3	0	3	8

Prerequisites	None
Course Language	English
Course Type	ELECTIVE_COURSE
Course Level	First Cycle
Mode of Delivery	Face-To-Face
Teaching Methods and Techniques of the Course	Problem Solving Lecture / Presentation
National Occupational Classification Code	-
Course Coordinator	Prof. Dr. Cem Evrendilek
Course Lecturer(s)	-
Assistant(s)	-

Course Objectives

The primary objective is to develop both an understanding of the formulation techniques, and the algorithms used to solve the class of optimization problems that lend themselves to linear and integer linear programming.

Learning Outcomes

The students who succeeded in this course;

Name	Description	PC Sub	* Contribution Level
Name	Description	PC Sub	1	2	3	4	5
LO1	will be able to create LP formulations to appropriate problems.	2					X
LO2	will be able to apply simplex and dual simplex methods.	1.4					X
LO3	will be able to express the run-time complexity of various algorithms for solving LP problems.	1.4					X
LO4	will be able to formulate Integer LP (ILP) formulations for various combinatorial problems.	2					X
LO5	will be able to employ techniques for relaxation of the ILP models to the corresponding LP formulations.	1.4					X

Course Description

LP Standard Form, Extreme Points and Basic Solutions, Rudimentary Simplex Algorithm, Interior Point Strategies for LP, Formulating Duals, Primal-to-Dual Relationships, LP-Based Branch and Bound, and Rounding.

Related Sustainable Development Goals

Course Category	Core Courses
	Major Area Courses	X
	Supportive Courses
	Media and Managment Skills Courses
	Transferable Skill Courses

WEEKLY SUBJECTS AND RELATED PREPARATION STUDIES

Week	Subjects	Required Materials	Learning Outcome
1	Nature of Linear Programs	Section 2.4	LO1
2	Formulation of Classic LP Model Types	Chapter 4	LO1
3	LP Standard Form, Extreme Points and Basic Solutions, Rudimentary Simplex Algorithm	Section 5.1, Section 5.2, Section 5.3	LO2
4	Two Phase Simplex, Degeneracy, Cycling and Finiteness of Simplex	Section 5.5, Sections 5.6, Section 5.7	LO2
5	Revised Simplex, Lower- and Upper-Bounded Simplex	Section 5.8, Section 5.9	LO2
6	Interior Point Strategies for LP, Affine Scaling of Solutions, Affine Scaling Search	Section 6.1, Section 6.2, Section 6.3	LO3
7	Log Barrier Methods for LP, Primal-Dual Search	Section 6.4, Section 6.5	LO3
8	Midterm		-
9	Activities vs. Resources, Qualititative Sensitivity	Sections 7.1-7.2	LO3
10	Quantitative Sensitivity and Duality, Formulating Duals, Primal-to-Dual Relationships	Section 7.3, Section 7.4, Section 7.5	LO3
11	Solving by Total Enumeration, Elementary Relaxations, Strengthening LP Relaxations	Section 12.1, Section 12.2, Section 12.3	LO5
12	LP-Based Branch and Bound	Section 12.4	LO4
13	Rounding, Parent Bounds, Enumeration Sequences and Stopping Early in Branch and Bound	Section 12.5	LO4
14	Improving Heuristics for Discrete Optimization, Tabu, Simulated Annealing, Genetic Algorithms, Constructive Heuristics for Discrete Optimization	Section 12.6, Section 12.7, Section 12.8	LO4
15	Semester Review		-
16	Final Exam		-

Course Notes/Textbooks	Optimization in Operations Research Ronald L. Rardin Prentice Hall ISBN-10: 0023984155 • ISBN-13: 9780023984150 1998.
Suggested Readings/Materials	-

EVALUATION SYSTEM

Semester Activities	Number	Weighting	LO1	LO2	LO3	LO4	LO5
Homework / Assignments	1	30	X	X	X	X	X
Midterm	1	30	X	X	X
Final Exam	1	40			X	X	X
Total	3	100

ECTS / WORKLOAD TABLE

Semester Activities	Number	Duration (Hours)	Workload
Participation	-	-	-
Theoretical Course Hours	16	3	48
Laboratory / Application Hours	-	-	-
Study Hours Out of Class	14	6	84
Field Work	-	-	-
Quizzes / Studio Critiques	-	-	-
Portfolio	-	-	-
Homework / Assignments	6	10	60
Presentation / Jury	-	-	-
Project	-	-	-
Seminar / Workshop	-	-	-
Oral Exams	-	-	-
Midterms	1	16	16
Final Exam	1	32	32
		Total	240

COURSE LEARNING OUTCOMES AND PROGRAM QUALIFICATIONS RELATIONSHIP

#	PC Sub	Program Competencies/Outcomes	* Contribution Level
#	PC Sub	Program Competencies/Outcomes	1	2	3	4	5
1	Engineering Knowledge: Knowledge of mathematics, science, basic engineering, computation, and related engineering discipline-specific topics; the ability to apply this knowledge to solve complex engineering problems.
	1	Mathematics
	2	Science
	3	Basic Engineering
	4	Computation					LO2 LO3 LO5
	5	Related engineering discipline-specific topics
	6	The ability to apply this knowledge to solve complex engineering problems
2	Problem Analysis: Ability to identify, formulate and analyze complex engineering problems using basic knowledge of science, mathematics and engineering, and considering the UN Sustainable Development Goals relevant to the problem being addressed.						LO1 LO4
3	Engineering Design: The ability to devise creative solutions to complex engineering problems; the ability to design complex systems, processes, devices or products to meet current and future needs, considering realistic constraints and conditions.
	1	Ability to design creative solutions to complex engineering problems
	2	Ability to design complex systems, processes, devices or products to meet current and future needs, considering realistic constraints and conditions
4	Use of Techniques and Tools: Ability to select and use appropriate techniques, resources, and modern engineering and computing tools, including estimation and modeling, for the analysis and solution of complex engineering problems, while recognizing their limitations.
5	Research and Investigation: Ability to use research methods to investigate complex engineering problems, including literature research, designing and conducting experiments, collecting data, and analyzing and interpreting results.
	1	Literature research for the study of complex engineering problems
	2	Designing experiments
	3	Ability to use research methods, including conducting experiments, collecting data. analyzing and interpreting results
6	Global Impact of Engineering Practices: Knowledge of the impacts of engineering practices on society, health and safety, economy, sustainability, and the environment, within the context of the UN Sustainable Development Goals; awareness of the legal implications of engineering solutions.
	1	Knowledge of the impacts of engineering practices on society, health and safety, economy, sustainability, and the environment, within the context of the UN Sustainable Development Goals
	2	Awareness of the legal implications of engineering solutions
7	Ethical Behavior: Acting in accordance with the principles of the engineering profession, knowledge about ethical responsibility; awareness of being impartial, without discrimination, and being inclusive of diversity.
	1	Acting in accordance with the principles of the engineering profession, knowledge about ethical responsibility ethical responsibility
	2	Awareness of being impartial and inclusive of diversity, without discriminating on any subject
8	Individual and Teamwork: Ability to work effectively, individually and as a team member or leader on interdisciplinary and multidisciplinary teams (face-to-face, remote or hybrid).
	1	Ability to work individually and within the discipline
	2	Ability to work effectively as a team member or leader in multidisciplinary teams (face-to-face, remote or hybrid)
9	Verbal and Written Communication: Taking into account the various differences of the target audience (such as education, language, profession) on technical issues.
	1	Ability to communicate verbally
	2	Ability to communicate effectively in writing
10	Project Management: Knowledge of business practices such as project management and economic feasibility analysis; awareness of entrepreneurship and innovation.
	1	Knowledge of business practices such as project management and economic feasibility analysis
	2	Awareness of entrepreneurship and innovation
11	Lifelong Learning: Lifelong learning skills that include being able to learn independently and continuously, adapting to new and developing technologies, and thinking questioningly about technological changes.