Assignment: Linear Programing and Affine Scaling

Submission Deadline: Thursday, December 18, 2025, at 12

This assignment is optional. If you submit it, then the 6 best of your 7 submitted assignments will be counted towards your final grade.

The script that you have to edit and submit before the deadline is asg-linprog/linprog.py.

You will have to implement the affine scaling algorithm for solving linear programs as described in the lecture. Moreover you will have to implement and solve a model for the diet problem. This problem consists in finding the amounts of a set of food items that minimize cost while satisfying certain minimal and maximal nutritional requirements. The data for the food items and their nutritional values are provided in the script file. Different data sets will be used in the remote testing system.

In all computational examples, use the unitary vector as initial point but be aware that this might not be feasible and that you will need to address this issue in your implementation. Overall, use the default tolerance of 1e-3.

Other instructions are provided in the docstrings of asg-linprog/linprog.py. Otherwise write to the teacher. This assignment has not been tested thoroughly. If you find any issues, please report them as soon as possible.