The Quadratic Unconstrained Binary Optimization (QUBO) model has gained prominence in recent years with the discovery that it unifies a rich variety of combinatorial optimization problems. By its association with the Ising problem in physics, the QUBO model has emerged as an underpinning of the quantum computing area known as quantum annealing and has become … Read more
The field of Combinatorial Optimization (CO) is one of the most important areas in the general field of optimization, with important applications found in every industry, including both the private and public sectors. It is also one of the most active research areas pursued by the research communities of Operations Research, Computer Science, and Analytics … Read more
This paper presents a new method for identifying critical nodes in planar networks. We propose an efficient method to evaluate the quality of solutions by using special properties of planar networks. It enables us to develop a computationally efficient heuristic algorithm for the problem. The proposed algorithm assisted on randomly generated planar networks. The experimental … Read more
Covering problems constitute an important family of facility location problems. This paper intro- duces a new exact algorithm for two important members of this family: i) the maximal covering location problem, which requires finding a subset of facilities that maximizes the amount of demand covered while respecting a budget constraint on the cost of the … Read more
Extreme events such as disasters cause partial or total disruption of basic services such as water, energy, communication and transportation. In particular, roads can be damaged or blocked by debris, thereby obstructing access to certain affected areas. Thus, restoration of the damaged roads is necessary to evacuate victims and distribute emergency commodities to relief centers … Read more
This paper is motivated by the case of a forwarder in dealing with inland transportation planning from a seaport, where inbound containers from the sea are filled with pallets, which have different destinations in the landside. Although this forwarder does not have or control any vehicle, he is required to plan the assignment of containers … Read more
We study in this paper min max robust combinatorial optimization problems for an uncertainty polytope that is defined by knapsack constraints, either in the space of the optimization variables or in an extended space. We provide exact and approximation algorithms that extend the iterative algorithms proposed by Bertismas and Sim (2003). We also study the … Read more
In this survey, we discuss the state-of-the-art of robust combinatorial optimization under uncertain cost functions. We summarize complexity results presented in the literature for various underlying problems, with the aim of pointing out the connections between the different results and approaches, and with a special emphasis on the role of the chosen uncertainty sets. Moreover, … Read more
In the field of robust optimization uncertain data is modeled by uncertainty sets, i.e. sets which contain all relevant outcomes of the uncertain parameters. The complexity of the related robust problem depends strongly on the shape of the uncertainty set. Two popular classes of uncertainty are budgeted uncertainty and ellipsoidal uncertainty. In this paper we … Read more
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