Archive

Posts Tagged ‘optimization’

Project Euler 607

June 11, 2017 2 comments

If you like solving Project Euler problems you should try Problem number 607. It’s not very hard, as it can be reduced to a small optimization problem. The idea is to find a path which minimizes time, knowing that certain regions correspond to different speeds. A precise statement of the result can be found on the official page. Here’s an image of the path which realizes the shortest time:

euler607

 

Project Euler tips

March 28, 2017 Leave a comment

A few years back I started working on Project Euler problems mainly because it was fun from a mathematical point of view, but also to improve my programming skills. After solving about 120 problems I seem to have hit a wall, because the numbers involved in some of the problems were just too big for my simple brute-force algorithms.

Recently, I decided to try and see if I can do some more of these problems. I cannot say that I’ve acquired some new techniques between 2012-2016 concerning the mathematics involved in these problems. My research topics are usually quite different and my day to day programming routines are more about constructing new stuff which works fast enough than optimizing actual code. Nevertheless, I have some experience coding in Matlab, and I realized that nested loops are to be avoided. Vectorizing the code can speed up things 100 fold.

So the point of Project Euler tasks is making things go well for large numbers. Normally all problems are tested and should run within a minute on a regular machine. This brings us to choosing the right algorithms, the right simplifications and finding the complexity of the algorithms involved.

Read more…

IMC 2016 – Day 2 – Problem 7

July 28, 2016 Leave a comment

Problem 7. Today, Ivan the Confessor prefers continuous functions {f:[0,1]\rightarrow \Bbb{R}} satisfying {f(x)+f(y) \geq |x-y|} for all {x,y \in [0,1]}. Fin the minimum of {\int_0^1 f} over all preferred functions.

Read more…

SIAM 100 digit challenge no 4 – Matlab solution

October 11, 2015 Leave a comment

In 2002 the SIAM News magazine published a list of {10} problems in numerical analysis. The answer to each of the problems should be given with an accuracy of at least {10} digits. And so there came the Hundred-Dollar, Hundred-Digit Challenge. I present below my attempt to solving the {4}th problem in this series, as it deals to finding the global minimum of a highly oscillating function. I confess that my approach is rather simplistic, but solves the problem. First let’s state the problem below:

Problem 4. What is the global minimum of the function

\displaystyle e^{\sin(50x)}+\sin(60e^y)+\sin(70\sin x)+\sin(\sin(80y))-\sin(10(x+y))+\frac{1}{4}(x^2+y^2).

Read more…

Optimal triangles with vertices on fixed circles

October 5, 2015 Leave a comment

Let {x,y,z>0} and suppose {ABC} is a triangle such that there exists a point {O} which satisfies {OA=x}, {OB = y}, {OC = z}. What is the relative position of {O} with respect to the triangle {ABC} such that

a) The area is maximized;

b) The perimeter is maximized.

This was inspired by this answer on Math Overflow.

Read more…

Seemous 2015 Problem 1

March 11, 2015 1 comment

Problem 1. Prove that for every {x \in (0,1)} the following inequality holds:

\displaystyle \int_0^1 \sqrt{1+\cos^2 y}dy > \sqrt{x^2+\sin^2 x}.

Read more…

Solve a Sudoku Puzzle using Matlab

March 29, 2014 3 comments

There was a time when I loved to solve Sudoku puzzles. It happened sometimes to find some really difficult puzzles, which I was unable to solve. Having a program which solves Sudoku puzzles is cool, but knowing how it works is cooler.

There are multiple types of solvers. One can imagine to take each free cell in a Sudoku puzzle and associate to it the set of integers in \{1,2,...,9\} which can lie in there (see the picture below). If the set of possible values contains only one element, then you have found the element corresponding to that cell. If not, then the program needs to make one guess, and see if it gets him to a contradiction. If it arrives at a contradiction, return to the choice step and choose another option, and this needs to be done recursively, which can take huge amounts of time.

sudoku_solver-148625-1

One other method which can be implemented in Matlab is to use the matrix structure of the Sudoku table and write the constraints of non repetition on lines, columns and 3 \times 3 blocks as linear constraints. Once all these constraints are well defined, you can call a semidefinite programming solver to find a solution. A semidefinite programming solver looks to find the vector which optimizes a given cost functions under certain constraints. A good sudoku puzzle has only one solution, and therfore every admissible input which satisfies the constraints is a solution. This means that the cost function doesn’t matter here.

I will present the implementation using YALMIP. You can find another equivalent Matlab implementation here.

Read more…

%d bloggers like this: