11
$\begingroup$

When solving large-scale hub assignment models (1000+ candidate hubs and 1000+ demand nodes), it is possible that parts of a cost matrix are not connected to one another.

A typical workflow would be:

  1. Read in data
  2. Create a graph (can be based on street or other network data)
  3. Create potential assignments with some cut off distance
  4. Calculate cost matrix
  5. Create formulation
  6. Solve
  7. Create output from solution

Is it better to create a separate formulation for each and solve?

OR

Is it better to break the formulation apart into the sub-problems?

OR

Do solvers just handle this (my experience would say no...)?

$\endgroup$
  • 6
    $\begingroup$ When you say "parts of a cost matrix are not connected", do you mean that the graph you construct in step 2 decomposes into multiple (disjoint) components? $\endgroup$ – prubin Jun 21 '19 at 14:29
  • 1
    $\begingroup$ What‘s the difference between option 1 and 2? $\endgroup$ – Marcus Ritt Jun 23 '19 at 18:39
  • $\begingroup$ @prubin - I mean that a group of potential candidate hubs potentially serves a group of demands. There are then other candidates and demands which are separable. This may be create by a number of options including as you mentioned (disjoint) components. Or, the user may specify some distance limitation for traversing the input graph which the assignments are created from. $\endgroup$ – fhk Jun 24 '19 at 2:43
  • $\begingroup$ @Marcus Rift The difference between one and two is as follows: The first option is to identify this in the input generation and then create separate formulations. Where as in 2 you generate a complete formulation that covers the whole problem and then separate it. $\endgroup$ – fhk Jun 24 '19 at 2:43
4
$\begingroup$

Cost matrixes are discussed in the book: "Assignment Problems" by Rainer Burkard, Mauro Dell'Amico, Silvano Martello (on pages 73, and 200, etc.). Yes, some parts would be unconnected (most likely) in such a large problem.

Seperation and calculation of the cost matrixes is only the start of the problem. Solving using traditional methods, for so many hubs and nodes, using CPLEX (for example) is going to run into out-of-memory problems.

Solution of these problems is complex (nearly NP-hard at that size; but you'll run into time and memory constraints, as opposed to simply not being able to formulate a solution). I can recommend a couple of papers (with 100's of equations) that address the hub-location-allocation problem (HLAP).


"Bi-objective optimization of multi-server intermodal hub-location-allocation problem in congested systems: modeling and solution" by Mahdi Rashidi Kahag, Seyed Taghi Akhavan Niaki, Mehdi Seifbarghy and Sina Zabihi, from the Journal of Industrial Engineering International (June 2019, Volume 15, Issue 2, pp 221–248):

"Abstract:

A new multi-objective intermodal hub-location-allocation problem is modeled in this paper in which both the origin and the destination hub facilities are modeled as an M/M/m queuing system. The problem is being formulated as a constrained bi-objective optimization model to minimize the total costs as well as minimizing the total system time. A small-size problem is solved on the GAMS software to validate the accuracy of the proposed model. As the problem becomes strictly NP-hard, an MOIWO algorithm with an efficient chromosome structure and a fuzzy dominance method is proposed to solve large-scale problems.

...

"Conclusion:

In this paper, a new bi-objective intermodal hub-location-allocation problem within queuing framework was investigated. The developed model of this problem intended to simultaneously minimize the total network costs and the total time spent in the network. The solution of a small-size problem using the GAMS software was presented to show the accuracy of the developed formulation. As the problem belongs to the class of NP-Hard problems with conflicting objectives, an MOIWO algorithm with a new chromosome structure was utilized to solve the problem. Moreover, a fuzzy ranking method was used in MOIWO to prioritize the solutions obtained in each iteration.".

I kept that quote short as I prefer the second paper.


In the paper: "Managing facility disruption in hub-and-spoke networks: formulations and efficient solution methods" by Nader Azizi, an open access publication of the: Annals of Operations Research (January 2019, Volume 272, Issue 1–2, pp 159–185), in the first section, he offers an introduction to his paper: "The focus of this paper is on the Uncapacitated Single Allocation p-Hub Location problem where the number of hub facilities to open is predetermined. This problem is also known as the Single Allocation p-Hub Median problem.".

He details some of the history of solving this problem:

"Early research on hub-and-spoke systems focused on developing efficient mathematical formulations and solution techniques for this paradigm. O’Kelly (1986, 1987) presented the first mathematical model for the single allocation p-hub median problem. Another pioneer of the hub location research, Campbell (1994), developed a linear integer formulation for the problem. Based on the idea of multicommodity flow, Ernst and Krishnamoorthy (1996) proposed a new set of formulations for both single and multiple allocation cases. A widely used formulation in the literature for single and multiple allocation p-hub median problem is the work of Skorin-Kapov et al. (1996). The MIP models proposed by Skorin-Kapov et al. (1996) yield to tight linear relaxation.

Over the years, a number of solution techniques e.g., approximation and exact methods have been developed and successfully applied to solve instances of the hub location-allocation problem. Examples of such methods include Simulated Annealing (Ernst and Krishnamoorthy 1999), Genetic Algorithm (Kratica et al. 2007), Hybrid GA and Tabu Search (Abdinnour-Helm 1998), Lagrangian Relaxation (Elhedhli and Wu 2010; Contreras et al. 2009), Benders Decomposition (Contreras et al. 2012), Branch and Bound (Ernst and Krishnamoorthy 1998), and Branch and Cut (Yaman and Carello 2005) among others.

More recent studies focus on the extension of the classical version and aim to develop more realistic hub location-allocation problems such as models with congestion (e.g., Elhedhli and Wu 2010; Azizi et al. 2017), flow dependent economies of scale (Camargo et al. 2009; Campbell et al. 2005), and competitive hub location models (Eiselt and Marianov 2009). For an overview of hub location problem the reader may refer to Campbell and O’Kelly (2012) and Contreras (2015).".

...

"In short, the contribution of the paper include:

(i) An investigation into a reliable hub-and-spoke system incorporating heterogeneous probability of hub failure

(ii) A non-linear model purposely designed to simultaneously construct networks with and without symmetrical flow and select backup facilities for every demand possibly affected by a disruption

(iii) An improved linear model with the use of indicator constraints and

(iv) Efficient Particle Swarm Optimization (PSO) based meta-heuristics for large instances.

The remainder of this paper is organised as follow. In Sect. 2, we describe the problem and present non-linear, linear and improved linear formulations. The details of the three proposed PSO based algorithms are presented in Sect. 3 followed by computational results and discussions in Sect. 5. Concluding remarks are presented in Sect. 6.".

In section 2 he explains (in detail, with almost 100 equations) that a Reliable Single Allocation p-Hub Location problem (RSApHL-I) involves a Mixed Integer Quadratic Programing (MIQP) formulation, and includes $n^2+4n^3+n^4$ variables. His approach is similar to the technique proposed by Chaovalitwongse et al. (2004) to linearize multi-quadratic 0–1 programming problems. He demonstrates that the problems could be solved more effectively and with significantly less computational efforts when all Big-M formulations are replaced with indicator constraints.

He concludes section 2 by saying:

"Due to the limitation in solving the above model formulation to optimality for realistically sized problem instances with CPLEX, one way forward is to design an efficient metaheuristic. In this study, we developed three metaheuristics based on the well-known evolutionary algorithm of Particle Swarm Optimisation (PSO). These algorithms are discussed in section 3.".

"A large portion of the published research works on PSO is dedicated to continuous optimization problems whereas there is a lack of research dealing with its discrete counterpart namely combinatorial optimization problems (Liu et al. 2008). To the best of our knowledge, our proposed algorithms is the first PSO-based optimisation technique to be developed for solving this interesting though challenging class of hub location problem.

In this paper two variations of a basic PSO and a hybrid PSO algorithm that incorporate crossover and memory are proposed. The two versions which we refer to as PSO-v1 and PSO-v2, differ in terms of solutions representation and the mechanism by which a continuous particle position is transformed into one or more discrete solution(s). The hybrid PSO algorithm on the other hand, is an extension of PSO-v2 which incorporates a short-term memory and a crossover operator, both of which are in our knowledge, new ingredients that are successfully embedded for the first time into the PSO search methodology.".

In section 6 the paper concludes:

"In this study, a mixed integer quadratic programming (MIQP) formulation is proposed for the reliable single allocation hub location problem with heterogeneous probability of hub failure. The model assigned a backup facility to every demand point in the network for a fast and a low-cost recovery after hub failure. The objective function of the model minimises the weighted transportation cost in regular situation and the expected cost resulted from hub failures.

The proposed formulation is developed in such way to maintain the size of the problem after linearization. To improve the computational efficiency of the resulting MILP model, all constraints initially formulated using Big Ms are substituted with logical constraints known as Indicator Constraints. Using the proposed formulation, we solved all small instances and some medium size problem instances to optimality and provided lower and/or upper bounds for other problems. To tackle large instances, three novel algorithms based on PSO namely PSO-v1, PSO-v2 and H-PSO are proposed. In PSO-v1 and PSO-v2, we investigated the effect of two different solution representations and the mechanisms through which a continuous particle is transferred to a discrete solution. It was found that PSO-v2 that maps a continuous particle to a single discrete solution performs better than PSO-v1. The performance of the PSO-v2 is then further improved by introducing two new interesting features namely a crossover operator and a memory to keep track of good solutions that are explored during the search. To our knowledge, this is the first time the hybridisation of PSO with those attributes is examined.".


Other:

O'Kelly's paper: "Network Hub Location" (2009) is a quick read with a basic overview of the subject.

Campbell and O’Kelly provide an excellent survey on the literature of hub location research in their paper: "Twenty-Five Years of Hub Location Research", published in Transportation Science 46(2):153-169 (January 2013).

Wikipedia: Facility Location Problem, Distributional cost-effectiveness analysis, Allocative efficiency, and Geometric median.

LocalSolver 9.0 documentation: P-median (Code examples for LSP, Python, C++, C#, and Java)

IBM Forum - OPL using CPLEX Optimizer

$\endgroup$
  • 2
    $\begingroup$ Ok looks like I have just a little reading to do... $\endgroup$ – fhk Jul 29 '19 at 16:03
7
$\begingroup$

Formulating as one big problem requires more memory, some way to recognize that the problem decomposes into disjoint subproblems, and some way to then solve the subproblems independently. At least one commercial solver (SAS) looks for such structure after presolve and suggests using the decomposition algorithm in that case. The decomposition algorithm automates the process, solving the independent subproblems concurrently, and returning the solution in the original space.

$\endgroup$
  • 2
    $\begingroup$ I should probably have also mentioned two other SAS features that have similar functionality (solving independent problems concurrently): the COFOR loop in PROC OPTMODEL, and BY-group processing in many SAS procedures. $\endgroup$ – RobPratt Jun 25 '19 at 1:59
  • 1
    $\begingroup$ gurobi also has some capabilities to detect structure in the problem that leads to decomposition and thus several subproblems. I can imagine that the other commercial solvers also have this feature... $\endgroup$ – JakobS Jul 29 '19 at 10:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.