**Monday, 16:15 - 16:40 h, Room: MA 042**

**Angelo Sifaleras**

Exterior point simplex-type algorithms for linear and network optimization problems

**Coauthor: Nikolaos Samaras**

**Abstract:**

The linear problem is one of the most useful and well-studied optimization problems, which is widely used in several areas of science. Lots of real world problems can be formulated as linear programs. The popularity of linear programming can be attributed to many factors such as the ability to model large problems, and the ability to solve large problems in a reasonable amount of time. Many algorithms have been invented for the solution of a linear program. The majority of these algorithms belong to two main categories: (i) Simplex-type or pivoting algorithms and (ii) interior-point methods (IPMs). All the algorithms presented in this paper belong to the first category, except one that belongs to both categories. The first exterior point simplex type algorithm (EPSA) was originally developed by Paparrizos for the assignment problem. EPSA constructs two paths to the optimal solution. One path consists of basic but not feasible solutions, while the second path is feasible. The key idea behind EPSA is that making steps in directions that are linear combinations of attractive descent direction can lead to faster convergence than that achieved by classic simplex type algorithms.

Talk 3 of the contributed session Mon.3.MA 042

**"Linear optimization"** [...]

Cluster 11

**"Integer & mixed-integer programming"** [...]