Optimization and Simulation for the Daily Operation of Renewable Energy Communities

Renewable Energy Communities (RECs) are an important building block for the decarbonization of the energy sector. The concept of RECs allows individual consumers to join together in local communities to generate, store, consume and sell renewable energy. A major benefit of this collective approach is a better match between supply and demand profiles, and thus, … Read more

Planning a Zero-Emission Mixed-Fleet Public Bus System with Minimal Life Cycle Cost

The variety of available technology options for the operation of zero-emission bus systems gives rise to the problem of finding an optimal technology decision for bus operators. Among others, overnight charging, opportunity charging and hydrogen-based technology options are frequently pursued technological solutions. As their operating conditions are strongly influenced by the urban context, an optimal … Read more

Integer Optimization with Penalized Fractional Values: The Knapsack Case

We consider integer optimization problems where variables can potentially take fractional values, but this occurrence is penalized in the objective function. This general situation has relevant examples in scheduling (preemption), routing (split delivery), cutting and telecommunications, just to mention a few. However, the general case in which variables integrality can be relaxed at cost of … Read more

Dynamic programming algorithms, efficient solution of the LP-relaxation and approximation schemes for the Penalized Knapsack Problem

We consider the 0-1 Penalized Knapsack Problem (PKP). Each item has a profit, a weight and a penalty and the goal is to maximize the sum of the profits minus the greatest penalty value of the items included in a solution. We propose an exact approach relying on a procedure which narrows the relevant range … Read more

Improved dynamic programming and approximation results for the knapsack problem with setups

We consider the 0-1 Knapsack Problem with Setups (KPS). Items are grouped into families and if any items of a family are packed, this induces a setup cost as well as a setup resource consumption. We introduce a new dynamic programming algorithm which performs much better than a previous dynamic program and turns out to … Read more

Minimization and Maximization Versions of the Quadratic Traveling Salesman Problem

The traveling salesman problem (TSP) asks for a shortest tour through all vertices of a graph with respect to the weights of the edges. The symmetric quadratic traveling salesman problem (SQTSP) associates a weight with every three vertices traversed in succession. If these weights correspond to the turning angles of the tour, we speak of … Read more

Approximation of Knapsack Problems with Conflict and Forcing Graphs

We study the classical 0-1 knapsack problem with additional restrictions on pairs of items. A conflict constraint states that from a certain pair of items at most one item can be contained in a feasible solution. Reversing this condition, we obtain a forcing constraint stating that at least one of the two items must be … Read more

On the shortest path game

In this work we address a game theoretic variant of the shortest path problem, in which two decision makers (agents/players) move together along the edges of a graph from a given starting vertex to a given destination. The two players take turns in deciding in each vertex which edge to traverse next. The decider in … Read more

Generating subtour constraints for the TSP from pure integer solutions

The traveling salesman problem (TSP) is one of the most prominent combinatorial optimization problems. Given a complete graph G = (V, E) and nonnegative real edge distances d, the TSP asks for a shortest tour through all vertices with respect to the distances d. The method of choice for solving the TSP to optimality is … Read more

Scheduling the Tasks of Two Agents with a Central Selection Mechanism

We address a class of deterministic scheduling problems in which two agents compete for the usage of a single machine. The agents have their own objective functions and submit in each round an arbitrary, unprocessed task from their buffer for possible selection. In each round the smaller of the two submitted tasks is chosen and … Read more