Search

For a graph G , the signless Laplacian matrix Q ( G ) is defined as Q ( G ) = D ( G ) + A ( G ) , where A ( G ) is the adjacency matrix of G and D ( G ) the diagonal matrix whose main entries are the degrees of the vertices in G . The Q -spectrum of G is that of Q ( G ) . In the present paper, we are interested in the minimum values of the second largest signless Laplacian eigenvalue q 2 ( G ) of a connected graph G . We find the five smallest values of q 2 ( G ) over the set of connected graphs G with given order n . We also characterize the corresponding extremal graphs.

Given a set of duties (sequences of activities to be accomplished by a bus driver on a specific day) to be operated over a cyclic one-week horizon and groups of drivers with similar characteristics...

The integral simplex using decomposition (ISUD) algorithm was recently developed to solve efficiently set partitioning problems containing a number of variables that can all be enumerated a priori. This primal algorithm generates a sequence of integer solutions with decreasing costs, leading to an optimal or near-optimal solution depending on the stopping criterion used. In this paper, we develop an integral column generation (ICG) heuristic that combines ISUD and column generation to solve set partitioning problems with a very large number of variables. Computational experiments on instances of the public transit vehicle and crew scheduling problem and of the airline crew pairing problem involving up to 2000 constraints show that ICG clearly outperforms two popular column generation heuristics (the restricted master heuristic and the diving heuristic). ICG can yield optimal or near-optimal solutions in less than 1 hour of computational time, generating up to 300 integer solutions during the solution process.

The integral simplex using decomposition (ISUD) is a primal algorithm dedicated to solve set partitioning problems (SPP). Given an integer solution, the integral simplex using decomposition (ISUD) seeks a descent direction that leads to an improved adjacent integer solution. It uses a horizontal decomposition (of a linear transformation of the constraint matrix). We propose the integral simplex using double decomposition (ISU2D) which is a parallel version of ISUD. It uses an innovative disjoint vertical decomposition to find in parallel orthogonal descent directions leading to an integer solution with a larger improvement. Each descent direction identifies a set of variables that will leave the current solution and a set of entering variables with better costs. To find these directions, we develop a dynamic decomposition approach that splits the original problem into subproblems that are then solved in parallel by ISUD. Our main innovation is the use of the current solution as a foundation for the construction of the set of subproblems; the set changes during the optimization process as the current solution changes. In addition, we use bounding and pricing strategies and implement parallel processing techniques. We show that ISU2D is 3 to 4 times faster than ISUD on large instances.

Through this paper we focus on a real-life combinatorial problem arising in emergent logistics and transportation field. The main objective is to solve a realistic multi-attribute rich Vehicle Routing Problem using a primal-based algorithm embedded in column generation framework. The mathematical model is formulated as a Set Partitioning Problem (SPP) while the subproblem is the shortest path problem with resource constraints (SPPRC). The numerical study was carried out on real instances reaching 140 customers. The successful results show the effectiveness of the method, and highlight its interest.

Integral simplex using decomposition (ISUD) is a method that efficiently solves set partitioning problems. It is an iterative method that starts from a known integer solution and moves through a sequence of integer solutions, decreasing the cost at each iteration. At each iteration, the method decomposes the original problem into a reduced problem (RP) and a complementary problem (CP). Given an integer solution to RP (that is also solution to the original problem), CP finds a descent direction having the minimum ratio between its cost and the number of its positive variables. We loop on until an optimal or near-optimal solution to the original problem is reached. In this paper, we introduce a modified model for CP. The new model finds a descent direction that minimizes the ratio between the cost of the direction and an overestimation of the number of variables taking one in the next solution. The new CP presents higher chances of finding improved integer solutions without branching. We present results for the same large instances (with up to 570,000 columns) as the ones previously used to test ISUD. For all the instances, optimality is always reached with a speedup factor of at least five.

In this paper, we introduce a general framework for vector space decompositions that decompose the set partitioning problem into a reduced problem, defined in the vector subspace generated by the columns corresponding to nonzero variables in the current integer solution, and a complementary problem, defined in the complementary vector subspace. We show that the integral simplex using decomposition algorithm (ISUD) developed in Zaghrouti et al. (Oper Res 62:435–449, 2014. https://doi.org/10.1287/opre.2013.1247) uses a particular decomposition, in which integrality is handled mainly in the complementary problem, to find a sequence of integer solutions with decreasing objective values leading to an optimal solution. We introduce a new algorithm using a new dynamic decomposition where integrality is handled only in the reduced problem, and the complementary problem is only used to provide descent directions, needed to update the decomposition. The new algorithm improves, at each iteration, the current integer solution by solving a reduced problem very small compared the original problem, that we define by zooming around the descent direction (provided by the complementary problem). This zooming algorithm is superior than ISUD on set partitioning instances from the transportation industry. It rapidly reaches optimal or near-optimal solutions for all instances including those considered very difficult for both ISUD and CPLEX.

Starting from the improved primal simplex (IPS) decomposition, introduced by Elhallaoui et al. (2011) to tackle degeneracy in general linear programs, we introduce and discuss the mathematical foundations of improved column-generation decompositions (ICG) that are better than the standard column-generation decomposition when degeneracy is an issue. We also present an improved dynamic constraint aggregation (IDCA), which is a specialization of ICG to efficiently solve set partitioning problems. We show that IDCA improves the dynamic constraint aggregation (DCA) and the multiphase dynamic constraint aggregation (MPDCA) algorithms (Elhallaoui et al., 2005, 2010) that not only reduce degeneracy but also profit from it to efficiently solve set partitioning problems. IDCA solves at each iteration a complementary problem (CP) to obtain a group of variables that can be aggregated or pivoted into the basis to bypass degenerate pivots and decrease the objective value and to obtain more “central” dual solutions to generate new columns. Our numerical results show reduction factors in the solution times exceeding 10 for IDCA compared to a state-of-the-art standard column-generation solver.

This paper proposes a deep learning model for block-level parking occupancy prediction. The proposed model leverages Convolutional Neural Nets (CNN) to extract spatial relations of traffic flow and stacked LSTM autoencoder to capture temporal correlations. The paper also introduces Clustering Augmented Learning Method (CALM) which is based on concept of simultaneous heterogeneous clustering and regression learning to learn deep feature representations of spatio-temporal data obtained using the proposed embedding. The regression model that is considered in this work has a Feedforward Neural Net(FNN) architecture. With the aim of improving the accuracy of the regression model, CALM iterates between clustering and learning to form robust clusters, thereby leveraging the learning process of the FNN. A dissimilarity measure is proposed based on the weights of each feature of input data in the regression model to form the clusters. During each iteration of learning and clustering, a classifier is used to predict the current cluster labels, and the cluster belonging probabilities are used to control the subsequent re-estimation of cluster centers. Computational experiments on San Francisco Parking data set reveals that proposed approach CALM outperforms other baseline methods including multi-layer LSTM and Lasso with testing MAPE of 7.8% when predicting block-level parking occupancies. The findings highlight that the way in which the spatio - temporal information is exploited in order to aggregate the analogous data into clusters makes a significant difference and demonstrate the effectiveness of the model in processing parking data.

This paper addresses the winner determination problem (WDP) for TL transportation procurement auctions under uncertain shipment volumes and uncertain carriers’ capacity. It extends an existing two-stage robust formulation proposed for the WDP with uncertain shipment volumes. The paper identifies and theoretically validates a number of accelerating strategies to speed up the convergence of a basic constraint generation algorithm proposed in the literature. Experimental results prove the high computational performance of the proposed new algorithm and the relevance of considering uncertainty on the carriers’ capacity when solving the WDP.

In this paper, we propose a two-phase approach to solve a combined routing and scheduling problem that occurs in the textile industry: fabrics are dyed by dye-jets and transported by forklifts. The objective is to minimize the cost of the unproductive activities, i.e., the dye-jet setup times and the forklift waiting time. The first phase solves an integer linear program to assign jobs (fabrics) to dye-jets while minimizing the setup cost; we compare an arc-based and a path-based formulation. The second phase uses a mixed-integer linear program for the dye-jet scheduling and both the routing and scheduling of forklifts. Experiments are performed on real data provided by a major multinational company, and larger test problems are randomly generated to assess the algorithm. The tests were conducted using Cplex 12.6.0 and a column generation solver. The numerical results show that our approach is efficient in terms of both solution quality and computational time.

In this paper we present the solution to a weekly log-truck scheduling problem (LTSP) integrating the routing and scheduling of trucks where all goods are transported in full truckloads. We must take into account pick-up and delivery requirements, multiple products, inventory levels, and lunch breaks. The objective is to minimize the overall transportation cost including wait times and the empty and loaded distance traveled. Our solution is based on a two-phase approach. The first phase involves an integer linear program that determines the destinations of full truckloads. The second phase uses an implicit integer linear program based on an arc formulation to ensure that the trucks are routed and scheduled at a minimum cost. Experiments have been conducted using Cplex 12.4.0, and almost all instances were solved within six hours with a reasonable gap.

Designing competitive manufacturing systems with high levels of productivity and quality at a reasonable cost is a complex task. Decision makers must face numerous decision variables which involve multiple and iterative analysis of the estimated cost, quality and productivity of each design alternative. This paper adresses this issue by providing a fast algorithm for solving the buffer sizing and inspection positioning problem of large production lines by combining heuristic and exact algorithms. We develop a multilevel hybrid search method combining a genetic algorithm and tabu search to identify promising locations for the inspection stations and an exact method that optimizes rapidly (in polynomial time) the buffers' sizes for each location. Our method gives valuable insights into the problem, and its solution time is a small fraction of that required by the exact method on production lines with 10-30 machines.