Closed Almost Knight’s Tours on 2D and 3D Chessboards

Let a (generalized) chessboard in two or three dimensions be given. A closed knight’s tour is defined as a Hamiltonian cycle over all cells of the chessboard where all moves are knight’s moves, i.,e. have length 5^0.5. It is well-characterized for which chessboard sizes it is not possible to construct a closed knight’s tour. On … Read more

The Multiple Checkpoint Ordering Problem

The multiple Checkpoint Ordering Problem (mCOP) aims to find an optimal arrangement of n one-dimensional departments with given lengths such that the total weighted sum of their distances to m given checkpoints is minimized. In this paper we suggest an integer linear programming (ILP) approach and a dynamic programming (DP) algorithm, which is only exact … Read more

New Constraints and Features for the University Course Timetabling Problem

The university course timetabling problem deals with the task of scheduling lectures of a set of university courses into a given number of rooms and time periods, taking into account various hard and soft constraints. The goal of the International Timetabling Competitions ITC2002 and ITC2007 was to establish models for comparison that cover the most … Read more

An Infeasible Active Set Method with Combinatorial Line Search for Convex Quadratic Problems with Bound Constraints

The minimization of a convex quadratic function under bound constraints is a fundamental building block for more complicated optimization problems. The active-set method introduced by [M. Bergounioux, K. Ito, and K. Kunisch. Primal-Dual Strategy for Constrained Optimal Control Problems. SIAM Journal on Control and Optimization, 37:1176–1194, 1999.] and [M. Bergounioux, M. Haddou, M. Hintermüller, and … Read more

A recursive semi-smooth Newton method for linear complementarity problems

A primal feasible active set method is presented for finding the unique solution of a Linear Complementarity Problem (LCP) with a P-matrix, which extends the globally convergent active set method for strictly convex quadratic problems with simple bounds proposed by [P. Hungerlaender and F. Rendl. A feasible active set method for strictly convex problems with … Read more

The Traveling Salesman Problem on Grids with Forbidden Neighborhoods

We introduce the Traveling Salesman Problem with forbidden neighborhoods (TSPFN). This is an extension of the Euclidean TSP in the plane where direct connections between points that are too close are forbidden. The TSPFN is motivated by an application in laser beam melting. In the production of a workpiece in several layers using this method … Read more

New Exact Approaches to Row Layout Problems

Given a set of departments, a number of rows and pairwise connectivities between these departments, the multi-row facility layout problem (MRFLP) looks for a non-overlapping arrangement of these departments in the rows such that the weighted sum of the center-to-center distances is minimized. As even small instances of the (MRFLP) are rather challenging, several special … Read more

New Semidefinite Programming Relaxations for the Linear Ordering and the Traveling Salesman Problem

In 2004 Newman suggested a semidefinite programming relaxation for the Linear Ordering Problem (LOP) that is related to the semidefinite program used in the Goemans-Williamson algorithm to approximate the Max Cut problem. Her model is based on the observation that linear orderings can be fully described by a series of cuts. Newman shows that her … Read more

A Semidefinite Opimization Approach to the Target Visitation Problem

We propose an exact algorithm for the Target Visitation Problem (TVP). The (TVP) is a composition of the Linear Ordering Problem and the Traveling Salesman Problem. It has several military and non-military applications, where two important, often competing factors are the overall distance traveled (e.g. by an unmanned aerial vehicle) and the visiting sequence of … Read more