Informatica

We introduce a compact formulation for the fixed-destination multi-depot asymmetric travelling salesman problem (FD-mATSP). It consists of m salesmen distributed among D depots who depart from and return to their respective origins after visiting a set of customers. The proposed model exploits the multi-depot aspect of the problem by labelling the arcs to identify the nodes that belong to the same tour. Our experimental investigation shows that the proposed-two index formulation is versatile and effective in modelling new variations of the FD-mATSP compared with existing formulations. We demonstrate this by applying it for the solution of two important extensions of the FD-mATSP that arise in logistics and manufacturing environments.

This paper investigates the problem of partitioning a complete weighted graph into complete subgraphs, each having the same number of vertices, with the objective of minimizing the sum of edge weights of the resulting subgraphs. This NP-complete problem arises in many applications such as assignment and scheduling-related group partitioning problems and micro-aggregation techniques. In this paper, we present a mathematical programming model and propose a complementary column generation approach to solve the resulting model. A dual based lower bounding feature is also introduced to curtail the notorious tailing-off effects often induced when using column generation methods. Computational results are presented for a wide range of test problems.

This paper presents an optimization based mathematical modelling approach for a single source single destination crude oil facility location transshipment problem. We began by formulating a mixed-integer nonlinear programming model and use a rolling horizon heuristic to find an optimal location for a storage facility within a restricted continuous region. We next design a hybrid two-stage algorithm that combines judicious facility locations resulting from the proposed model into a previously developed column generation approach. The results indicate that improved overall operational costs can be achieved by strategically determining cost-effective locations of the transshipment facility.

This paper presents a column generation-based modelling and solution approach for a teaching assistant workload scheduling problem that arises at academic institutions. A typical weekly workload schedule involves teaching deficiency classes, instructing problem-solving tutorial sessions, and allocating help-hours for students. For this purpose, a mixed-integer programming model that selects valid combinations of weekly schedules from the set of all feasible schedules is formulated. Due to the overwhelming number of variables in this model, an effective column generation procedure is developed. To illustrate the proof-of-concept along with modelling and algorithmic constructs, a case study related to the Department of Mathematics at Kuwait University is addressed. Computational results based on real data indicate that the generated schedules using the proposed model and solution procedure yield improved weekly workloads for teaching assistants in terms of fairness, and achieve enhanced satisfaction levels among assistants, as compared to schedules obtained using ad-hoc manual approaches.

We present a novel dynamic network interdiction model that accounts for interactions between an interdictor deploying resources on arcs in a digraph and an evader traversing the network from a designated source to a known terminus, wherein the agents may modify strategies in selected subsequent periods according to respective decision and implementation cycles. For the resulting minimax model, we develop a reformulation that facilitates a direct solution procedure using commercial software or via a proposed alternating heuristic. We examine certain related stability and convergence issues, demonstrate special convergence cases, and provide insights into the computational performance of the solution procedures.

This paper is concerned with an employee scheduling problem involving multiple shifts and work centers, where employees belong to a hierarchy of categories having downward substitutability. An employee at a higher category may perform the duties of an employee at a lower category, but not vice versa. However, a higher category employee receives a higher compensation than a lower category employee. For a given work center, the demand for each category during a given shift is fixed for the weekdays, and may differ from that on weekends. Two objectives need to be achieved: The first is to find a minimum-cost workforce mix of categories of employees that is needed to satisfy specified demand requirements, and the second is to assign the selected employees to shifts and work centers taking into consideration their preferences for shifts, work centers, and off-days. A mixed-integer programming model is initially developed for the problem, based on which a specialized scheduling heuristic is subsequently developed for the problem. Computational results reported reveal that the proposed heuristic determines solutions proven to lie within 92–99% of optimality for a number of realistic test problems.

A concept of regional technological cooperation is developed based on a cooperative game theoretic model, in which a plan of payoff distributions induces an agreement that is acceptable to each participant. Under certain conditions, the underlying game is shown to be convex, and hence to have a nonempty core with the Shapley value allocations belonging to the core. A compensation scheme is devised based on the Shapley value allocations, whereby participants who enjoy a greater payoff with respect to the technological cooperation compensate the participants who receive a relatively lesser payoff via cooperation. In this manner, regional technological cooperation can bring overall benefits to all the involved players in the game. Some insightful examples are provided to illustrate the methodological concept.

In this research, we develop an algorithm for linear programming problems based on a new interpretation of Karmarkar's representation for this problem. Accordingly, we examine a suitable polytope for which the origin is an exterior point, and in order to determine an optimal solution, we need to ascertain the minimum extent by which this polytope needs to be slid along a one-dimensional axis so that the origin belongs to it. To accomplish this, we employ strongly separating hyperplanes between the origin and the polytope using a closest point routine. The algorithm is further enhanced by the generation of dual solutions which enable us to deform the polytope so that it is favorably positioned with respect to the origin and the axis of sliding motion. The overall scheme is easy to implement, requires a minimal amount of storage, and produces quick good quality lower bounds for the problem in its infinite convergence process. A switchover to the simplex method or an interior point method is also possible, using the current available solution as an advanced start. Preliminary computational results are provided along with implementation guidelines.