We propose a novel exact algorithm for the transportation problem, one of the paradigmatic network optimization problems. The algorithm, called Iterated Inside Out, requires as input a basic feasible solution and is composed of two main phases that are iteratively repeated until an optimal basic feasible solution is computed. In the first “inside” phase, the algorithm progressively improves upon a given basic solution by increasing the value of several nonbasic variables with negative reduced cost. This phase typically outputs a nonbasic feasible solution interior to the constraint set polytope. The second “out” phase moves in the opposite direction by iteratively setting to zero several variables until a new improved basic feasible solution is reached. Extensive computational tests show that the proposed approach strongly outperforms all versions of network and linear programming algorithms available in the commercial solvers CPLEX and Gurobi and other exact algorithms available in the literature. History: Accepted by Andrea Lodi, Area Editor for Design & Analysis of Algorithms—Discrete. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information ( https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2024.0642 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2024.0642 ). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/ .

This paper proposes an exact exponential algorithm for the problem of minimizing the total tardiness of jobs on a single machine. It exploits the structure of a basic branch-and-reduce framework based on the well known Lawler's decomposition property. The proposed algorithm, called branch-and-merge, is an improvement of the branch-and-reduce technique with the embedding of a node merging operation. Its time complexity is O*(2.247^n) keeping the space complexity polynomial. The branch-and-merge technique is likely to be generalized to other sequencing problems with similar decomposition properties.

We consider a two-machine flowshop-scheduling problem with an unknown common due date where the objective is minimization of both the number of tardy jobs and the unknown common due date. We show that the problem is NP-hard in the ordinary sense and present a pseudopolynomial dynamic program for its solution. Then, we propose an exact ϵ-constraint approach based on the optimal solution of a related single-machine problem. For this latter problem a compact ILP formulation is explored: a powerful variable-fixing technique is presented and several logic cuts are considered. Computational results indicate that, with the proposed approach, the pareto optima can be computed, in reasonable time, for instances with up to 500 jobs.

Abstract This article deals with a Hub Location Problem arising in Telecommunication Network Design. The considered network presents two different kinds of nodes: access nodes, that represent source and destination of traffic demands but cannot be directly connected, and transit nodes, that have no own traffic demand but collect traffic from access nodes and route it through the network. Transit nodes are supposed to be fully connected. Given a set of access nodes and a set of potential locations for the transit nodes, the problem is to decide number and positions of the transit nodes to guarantee that all access nodes are allocated to a transit node, satisfying capacity constraints. The goal is to minimize the total cost of the network, which is the sum of connection costs and nodes fixed costs. The problem is a Hub Location Problem, which is known to be NP‐hard. A local search approach is proposed, and different metaheuristic algorithms, such as tabu search, iterated local search and random multistart, have been developed, based on such local search. [A preliminary procedure has been developed in a research project joint with Telecom Italia (Turin Research & Innovation Laboratories) and a patent application has been filed to cover this issue.] © 2004 Wiley Periodicals, Inc. NETWOEKS, Vol. 44(2), 94–105 2004

Abstract The IP (Internet Protocol) Network Design Problem can be shortly stated as follows. Given a set of nodes and a set of traffic demands, we want to determine the minimum cost capacity installation such that all the traffic is routed. Capacity is provided by means of links of a given capacity and traffic must be loaded on the network according to the OSPF‐ECM (Open Shortest Path First—Equal Commodity Multiflow) protocol, with additional constraints on the maximum number of hops. The problem is strongly NP‐Hard, and the literature proposes local search‐based heuristics that do not take into account max‐hop constraints, or assume a simplified OSPF routing. The core in a local search approach is the network loading algorithm for the evaluation of the neighbor solutions costs. It presents critical aspects concerning both computational efficiency and memory requirements. Starting from a tabu search prototype, we show how these aspects deeply impact on the design of a local search procedure, even at the logical level. We present several properties of the related network loading problem, that allow to overcome the critical issues and lead to an efficient solution evaluation. © 2004 Wiley Periodicals, Inc. NETWORKS, VoL. 44(2), 73–83 2004

Introduces a production scheduling problem encountered in COMPAL S.A., a factory located in Lisbon (Portugal) which produces perishable goods for the food market. From the factory specifications the authors show how to derive a scheduling model and a two-step heuristic procedure for its solution.>

The authors propose augmented Lagrangian-based decomposition techniques for solving complex planning and control problems in flexible manufacturing systems. It is shown that the resulting decomposition of the mathematical problem lends itself to control systems with a topological cellular structure, and can be treated very naturally with an object-oriented programming approach. The mathematical formulation of the problem is presented. Its application to a specific example in which all the main features of the method are fully described is presented. Some computational results are presented.>