The semi-Lagrangian relaxation （SLR）, a new exactmethod for combinatorial optimization problems with equality constraints,is applied to the quadratic assignment problem （QAP）.A dual ascent algorithm with finite co...The semi-Lagrangian relaxation （SLR）, a new exactmethod for combinatorial optimization problems with equality constraints,is applied to the quadratic assignment problem （QAP）.A dual ascent algorithm with finite convergence is developed forsolving the semi-Lagrangian dual problem associated to the QAP.We perform computational experiments on 30 moderately difficultQAP instances by using the mixed integer programming solvers,Cplex, and SLR＋Cplex, respectively. The numerical results notonly further illustrate that the SLR and the developed dual ascentalgorithm can be used to solve the QAP reasonably, but also disclosean interesting fact： comparing with solving the unreducedproblem, the reduced oracle problem cannot be always effectivelysolved by using Cplex in terms of the CPU time.展开更多
As the hot line in NP-hard problems research in recent years, backbone analysis is crucial for phase transition, hardness, and algorithm design. Whereas theoretical analysis of backbone and its applications in algorit...As the hot line in NP-hard problems research in recent years, backbone analysis is crucial for phase transition, hardness, and algorithm design. Whereas theoretical analysis of backbone and its applications in algorithm design are still at a begin- ning state yet, this paper took the quadratic assignment problem （QAP） as a case study and proved by theoretical analysis that it is NP-hard to find the backbone, i.e., no algorithm exists to obtain the backbone of a QAP in polynomial time. Results of this paper showed that it is reasonable to acquire approximate backbone by inter- section of local optimal solutions. Furthermore, with the method of constructing biased instances, this paper proposed a new meta-heuristic -- biased instance based approximate backbone （BI-AB）, whose basic idea is as follows： firstly, construct a new biased instance for every QAP instance （the optimal solution of the new instance is also optimal for the original one）; secondly, the approximate backbone is obtained by intersection of multiple local optimal solutions computed by some existing algorithm; finally, search for the optimal solutions in the reduced space by fixing the approximate backbone. Work of the paper enhanced the research area of theoretical analysis of backbone. The meta-heuristic proposed in this paper provided a new way for general algorithm design of NP-hard problems as well.展开更多
An appropriate spatial structure of a power battery supply network is crucial for the specialization and scale development of key components in new energy vehicles, accelerating the transformation and upgrade of the i...An appropriate spatial structure of a power battery supply network is crucial for the specialization and scale development of key components in new energy vehicles, accelerating the transformation and upgrade of the industry. This paper investigates the cooperative relationships among supply chain enterprises from the perspective of complex networks.Employing methodologies such as the gravity model and Moran's I analysis, it explores the spatial structural characteristics and correlation patterns of the power battery supply network in China and discusses the influencing factors using the quadratic assignment procedure,revealing the mechanisms behind the differences in the spatial distributions of the power battery supply network. The results indicate that the distribution of power battery enterprises is densely concentrated in the eastern and southern regions, whereas the western region has a sparse distribution. The spatial supply network consists of a four-tier linkage system, encompassing 135 prefecture-level cities, with Chongqing, Shanghai, Nanjing, and other cities particularly prominent. Overall, the degree of agglomeration is low, with coastal cities dominating the landscape and inland cities serving as complementary regions. Most areas are characterized as insignificant or low-high regions, and the regional linkage effect of core cities is not pronounced. There is a notable lack of significance and high spatial heterogeneity.Four types of factors—spatial factors, market factors, agglomeration economies, and innovation levels—jointly influence and shape the spatial structure of the power battery supply network.展开更多
City cluster is an effective platform for encouraging regionally coordinated development.Coordinated reduction of carbon emissions within city cluster via the spatial association network between cities can help coordi...City cluster is an effective platform for encouraging regionally coordinated development.Coordinated reduction of carbon emissions within city cluster via the spatial association network between cities can help coordinate the regional carbon emission management,realize sustainable development,and assist China in achieving the carbon peaking and carbon neutrality goals.This paper applies the improved gravity model and social network analysis(SNA)to the study of spatial correlation of carbon emissions in city clusters and analyzes the structural characteristics of the spatial correlation network of carbon emissions in the Yangtze River Delta(YRD)city cluster in China and its influencing factors.The results demonstrate that:1)the spatial association of carbon emissions in the YRD city cluster exhibits a typical and complex multi-threaded network structure.The network association number and density show an upward trend,indicating closer spatial association between cities,but their values remain generally low.Meanwhile,the network hierarchy and network efficiency show a downward trend but remain high.2)The spatial association network of carbon emissions in the YRD city cluster shows an obvious‘core-edge’distribution pattern.The network is centered around Shanghai,Suzhou and Wuxi,all of which play the role of‘bridges’,while cities such as Zhoushan,Ma'anshan,Tongling and other cities characterized by the remote location,single transportation mode or lower economic level are positioned at the edge of the network.3)Geographic proximity,varying levels of economic development,different industrial structures,degrees of urbanization,levels of technological innovation,energy intensities and environmental regulation are important influencing factors on the spatial association of within the YRD city cluster.Finally,policy implications are provided from four aspects:government macro-control and market mechanism guidance,structural characteristics of the‘core-edge’network,reconfiguration and optimization of the spatial layout of the YRD city cluster,and the application of advanced technologies.展开更多
In IaaS Cloud,different mapping relationships between virtual machines(VMs) and physical machines(PMs) cause different resource utilization,so how to place VMs on PMs to reduce energy consumption is becoming one of th...In IaaS Cloud,different mapping relationships between virtual machines(VMs) and physical machines(PMs) cause different resource utilization,so how to place VMs on PMs to reduce energy consumption is becoming one of the major concerns for cloud providers.The existing VM scheduling schemes propose optimize PMs or network resources utilization,but few of them attempt to improve the energy efficiency of these two kinds of resources simultaneously.This paper proposes a VM scheduling scheme meeting multiple resource constraints,such as the physical server size(CPU,memory,storage,bandwidth,etc.) and network link capacity to reduce both the numbers of active PMs and network elements so as to finally reduce energy consumption.Since VM scheduling problem is abstracted as a combination of bin packing problem and quadratic assignment problem,which is also known as a classic combinatorial optimization and NP-hard problem.Accordingly,we design a twostage heuristic algorithm to solve the issue,and the simulations show that our solution outperforms the existing PM- or network-only optimization solutions.展开更多
Globalization and informatization promote the evolution of urban spatial organization from a hierarchical structure mode to a network structure mode,forming a complex network system.This study considers the coupling o...Globalization and informatization promote the evolution of urban spatial organization from a hierarchical structure mode to a network structure mode,forming a complex network system.This study considers the coupling of“space of flows”and“spaces of places”as the core and“embeddedness”as the link and a relevant theoretical basis;then we construct a conceptual model of urban networks and explore the internal logic of enterprise networks and city networks.Using the interlocking-affiliate network model and data from China’s top 500 listed companies,this study constructs a directed multi-valued relational matrix between cities in western China from 2005 to 2015.Using social network analysis and the multiple regression of quadratic assignment program model(MRQAP),this study adopts a“top-down”research perspective to analyze the spatio-temporal evolution and growth mechanism of the city network in western China from three nested spatial scales:large regions,intercity agglomerations,and intracity agglomerations.The results show the following:(1)Under the large regional scale,the city network has good symmetry,obvious characteristics of hierarchical diffusion,neighborhood diffusion,and cross-administrative regional connection,presenting the“core-periphery”structural pattern.(2)The network of intercity agglomerations has the characteristics of centralization,stratification,and geographical proximity.(3)The internal network of each urban agglomeration presents a variety of network structure modes,such as dual-core,single-core,and multicore modes.(4)Administrative subordination and economic system proximity have a significant positive impact on the city network in western China.The differences in internet convenience,investment in science and technology,average time distance,and economic development have negative effects on the growth and development of city networks.(5)The preferential attachment is the internal driving force of the city network development.展开更多
Imagery assessment is an efficient method for detecting craniofacial anomalies.A cephalometric landmark matching approach may help in orthodontic diagnosis,craniofacial growth assessment and treatment planning.Automati...Imagery assessment is an efficient method for detecting craniofacial anomalies.A cephalometric landmark matching approach may help in orthodontic diagnosis,craniofacial growth assessment and treatment planning.Automatic landmark matching and anomalies detection helps face the manual labelling lim-itations and optimize preoperative planning of maxillofacial surgery.The aim of this study was to develop an accurate Cephalometric Landmark Matching method as well as an automatic system for anatomical anomalies classification.First,the Active Appearance Model(AAM)was used for the matching process.This pro-cess was achieved by the Ant Colony Optimization(ACO)algorithm enriched with proximity information.Then,the maxillofacial anomalies were classified using the Support Vector Machine(SVM).The experiments were conducted on X-ray cephalograms of 400 patients where the ground truth was produced by two experts.The frameworks achieved a landmark matching error(LE)of 0.50±1.04 and a successful landmark matching of 89.47%in the 2 mm and 3 mm range and of 100%in the 4 mm range.The classification of anomalies achieved an accuracy of 98.75%.Compared to previous work,the proposed approach is simpler and has a comparable range of acceptable matching cost and anomaly classification.Results have also shown that it outperformed the K-nearest neigh-bors(KNN)classifier.展开更多
In this paper we study a Class of nonconvex quadratically constrained quadratic programming problems generalized from relaxations of quadratic assignment problems. We show that each problem is polynomially solved. Str...In this paper we study a Class of nonconvex quadratically constrained quadratic programming problems generalized from relaxations of quadratic assignment problems. We show that each problem is polynomially solved. Strong duality holds if a redundant constraint is introduced. As an application, a new lower bound is proposed for the quadratic assignment problem.展开更多
We present an effective spectral matching method based on a shape association graph for finding region correspondences between two cel animation keyframes.We formulate the correspondence problem as an adapted quadrati...We present an effective spectral matching method based on a shape association graph for finding region correspondences between two cel animation keyframes.We formulate the correspondence problem as an adapted quadratic assignment problem,which comprehensively considers both the intrinsic geometric and topology of regions to find the globally optimal correspondence.To simultaneously represent the geometric and topological similarities between regions,we propose a shape association graph(SAG),whose node attributes indicate the geometric distance between regions,and whose edge attributes indicate the topological distance between combined region pairs.We convert topological distance to geometric distance between geometric objects with topological features of the pairs,and introduce Kendall shape space to calculate the intrinsic geometric distance.By utilizing the spectral properties of the affinity matrix induced by the SAG,our approach can efficiently extract globally optimal region correspondences,even if shapes have inconsistent topology and severe deformation.It is also robust to shapes undergoing similarity transformations,and compatible with parallel computing techniques.展开更多
基金supported by the National Natural Science Foundation of China(71401106)the Innovation Program of Shanghai Municipal Education Commission(14YZ090)+4 种基金the Shanghai Natural Science Foundation(14ZR1418700)the Shanghai First-class Academic Discipline Project(S1201YLXK)the Hujiang Foundation of China(A14006)the grant S2009/esp-1594 from the Comunidad de Madrid(Spain)the grant MTM2012-36163-C06-06 from the Spanish government
文摘The semi-Lagrangian relaxation （SLR）, a new exactmethod for combinatorial optimization problems with equality constraints,is applied to the quadratic assignment problem （QAP）.A dual ascent algorithm with finite convergence is developed forsolving the semi-Lagrangian dual problem associated to the QAP.We perform computational experiments on 30 moderately difficultQAP instances by using the mixed integer programming solvers,Cplex, and SLR＋Cplex, respectively. The numerical results notonly further illustrate that the SLR and the developed dual ascentalgorithm can be used to solve the QAP reasonably, but also disclosean interesting fact： comparing with solving the unreducedproblem, the reduced oracle problem cannot be always effectivelysolved by using Cplex in terms of the CPU time.
基金the National Natural Science Foundation of China (Grant Nos. 60673046 and 60673066)the Natural Science Foundation of LiaoNing Province (Grant No. 20051082)the Gifted Young Foundation of Dalian University of Technology
文摘As the hot line in NP-hard problems research in recent years, backbone analysis is crucial for phase transition, hardness, and algorithm design. Whereas theoretical analysis of backbone and its applications in algorithm design are still at a begin- ning state yet, this paper took the quadratic assignment problem （QAP） as a case study and proved by theoretical analysis that it is NP-hard to find the backbone, i.e., no algorithm exists to obtain the backbone of a QAP in polynomial time. Results of this paper showed that it is reasonable to acquire approximate backbone by inter- section of local optimal solutions. Furthermore, with the method of constructing biased instances, this paper proposed a new meta-heuristic -- biased instance based approximate backbone （BI-AB）, whose basic idea is as follows： firstly, construct a new biased instance for every QAP instance （the optimal solution of the new instance is also optimal for the original one）; secondly, the approximate backbone is obtained by intersection of multiple local optimal solutions computed by some existing algorithm; finally, search for the optimal solutions in the reduced space by fixing the approximate backbone. Work of the paper enhanced the research area of theoretical analysis of backbone. The meta-heuristic proposed in this paper provided a new way for general algorithm design of NP-hard problems as well.
基金Humanities and Social Sciences Project of the Ministry of Education of China,No.23YJCZH195Scientific Research Program funded by the Shaanxi Provincial Education Department,No.20JK0358, No.21JK0908+2 种基金Natural Science Basic Research Program of Shaanxi,No.2024JC-YBQN-0738, No.2023-JC-QN-0560Shaanxi Provincial Education Science Planning Project,No.SGH23Y2484China Logistics Society&China Federation of Logistics and Purchasing Research Fund,No.2023CSLKT3-220。
文摘An appropriate spatial structure of a power battery supply network is crucial for the specialization and scale development of key components in new energy vehicles, accelerating the transformation and upgrade of the industry. This paper investigates the cooperative relationships among supply chain enterprises from the perspective of complex networks.Employing methodologies such as the gravity model and Moran's I analysis, it explores the spatial structural characteristics and correlation patterns of the power battery supply network in China and discusses the influencing factors using the quadratic assignment procedure,revealing the mechanisms behind the differences in the spatial distributions of the power battery supply network. The results indicate that the distribution of power battery enterprises is densely concentrated in the eastern and southern regions, whereas the western region has a sparse distribution. The spatial supply network consists of a four-tier linkage system, encompassing 135 prefecture-level cities, with Chongqing, Shanghai, Nanjing, and other cities particularly prominent. Overall, the degree of agglomeration is low, with coastal cities dominating the landscape and inland cities serving as complementary regions. Most areas are characterized as insignificant or low-high regions, and the regional linkage effect of core cities is not pronounced. There is a notable lack of significance and high spatial heterogeneity.Four types of factors—spatial factors, market factors, agglomeration economies, and innovation levels—jointly influence and shape the spatial structure of the power battery supply network.
基金Under the auspices of the National Natural Science Foundation of China (No.72273151)。
文摘City cluster is an effective platform for encouraging regionally coordinated development.Coordinated reduction of carbon emissions within city cluster via the spatial association network between cities can help coordinate the regional carbon emission management,realize sustainable development,and assist China in achieving the carbon peaking and carbon neutrality goals.This paper applies the improved gravity model and social network analysis(SNA)to the study of spatial correlation of carbon emissions in city clusters and analyzes the structural characteristics of the spatial correlation network of carbon emissions in the Yangtze River Delta(YRD)city cluster in China and its influencing factors.The results demonstrate that:1)the spatial association of carbon emissions in the YRD city cluster exhibits a typical and complex multi-threaded network structure.The network association number and density show an upward trend,indicating closer spatial association between cities,but their values remain generally low.Meanwhile,the network hierarchy and network efficiency show a downward trend but remain high.2)The spatial association network of carbon emissions in the YRD city cluster shows an obvious‘core-edge’distribution pattern.The network is centered around Shanghai,Suzhou and Wuxi,all of which play the role of‘bridges’,while cities such as Zhoushan,Ma'anshan,Tongling and other cities characterized by the remote location,single transportation mode or lower economic level are positioned at the edge of the network.3)Geographic proximity,varying levels of economic development,different industrial structures,degrees of urbanization,levels of technological innovation,energy intensities and environmental regulation are important influencing factors on the spatial association of within the YRD city cluster.Finally,policy implications are provided from four aspects:government macro-control and market mechanism guidance,structural characteristics of the‘core-edge’network,reconfiguration and optimization of the spatial layout of the YRD city cluster,and the application of advanced technologies.
基金the National Natural Science Foundation of China，the National High Technology Research and Development Program of China (863 Program)，the Fundamental Research Funds for the Central Universities，the Natural Science Foundation of Gansu Province,China，the Open Fund of the State Key Laboratory of Software Development Environment
文摘In IaaS Cloud,different mapping relationships between virtual machines(VMs) and physical machines(PMs) cause different resource utilization,so how to place VMs on PMs to reduce energy consumption is becoming one of the major concerns for cloud providers.The existing VM scheduling schemes propose optimize PMs or network resources utilization,but few of them attempt to improve the energy efficiency of these two kinds of resources simultaneously.This paper proposes a VM scheduling scheme meeting multiple resource constraints,such as the physical server size(CPU,memory,storage,bandwidth,etc.) and network link capacity to reduce both the numbers of active PMs and network elements so as to finally reduce energy consumption.Since VM scheduling problem is abstracted as a combination of bin packing problem and quadratic assignment problem,which is also known as a classic combinatorial optimization and NP-hard problem.Accordingly,we design a twostage heuristic algorithm to solve the issue,and the simulations show that our solution outperforms the existing PM- or network-only optimization solutions.
基金National Natural Science Foundation of China(41501176)National Natural Science Foundation of China(41961030)。
文摘Globalization and informatization promote the evolution of urban spatial organization from a hierarchical structure mode to a network structure mode,forming a complex network system.This study considers the coupling of“space of flows”and“spaces of places”as the core and“embeddedness”as the link and a relevant theoretical basis;then we construct a conceptual model of urban networks and explore the internal logic of enterprise networks and city networks.Using the interlocking-affiliate network model and data from China’s top 500 listed companies,this study constructs a directed multi-valued relational matrix between cities in western China from 2005 to 2015.Using social network analysis and the multiple regression of quadratic assignment program model(MRQAP),this study adopts a“top-down”research perspective to analyze the spatio-temporal evolution and growth mechanism of the city network in western China from three nested spatial scales:large regions,intercity agglomerations,and intracity agglomerations.The results show the following:(1)Under the large regional scale,the city network has good symmetry,obvious characteristics of hierarchical diffusion,neighborhood diffusion,and cross-administrative regional connection,presenting the“core-periphery”structural pattern.(2)The network of intercity agglomerations has the characteristics of centralization,stratification,and geographical proximity.(3)The internal network of each urban agglomeration presents a variety of network structure modes,such as dual-core,single-core,and multicore modes.(4)Administrative subordination and economic system proximity have a significant positive impact on the city network in western China.The differences in internet convenience,investment in science and technology,average time distance,and economic development have negative effects on the growth and development of city networks.(5)The preferential attachment is the internal driving force of the city network development.
基金supported by Princess Nourah bint Abdulrahman University Researchers Supporting Project number(PNURSP2022R196)Princess Nourah bint Abdulrahman University,Riyadh,Saudi Arabia.
文摘Imagery assessment is an efficient method for detecting craniofacial anomalies.A cephalometric landmark matching approach may help in orthodontic diagnosis,craniofacial growth assessment and treatment planning.Automatic landmark matching and anomalies detection helps face the manual labelling lim-itations and optimize preoperative planning of maxillofacial surgery.The aim of this study was to develop an accurate Cephalometric Landmark Matching method as well as an automatic system for anatomical anomalies classification.First,the Active Appearance Model(AAM)was used for the matching process.This pro-cess was achieved by the Ant Colony Optimization(ACO)algorithm enriched with proximity information.Then,the maxillofacial anomalies were classified using the Support Vector Machine(SVM).The experiments were conducted on X-ray cephalograms of 400 patients where the ground truth was produced by two experts.The frameworks achieved a landmark matching error(LE)of 0.50±1.04 and a successful landmark matching of 89.47%in the 2 mm and 3 mm range and of 100%in the 4 mm range.The classification of anomalies achieved an accuracy of 98.75%.Compared to previous work,the proposed approach is simpler and has a comparable range of acceptable matching cost and anomaly classification.Results have also shown that it outperformed the K-nearest neigh-bors(KNN)classifier.
基金Supported by the fundamental research funds for the central universities under grant YWF-10-02-021 and by National Natural Science Foundation of China under grant 11001006 The author is very grateful to all the three anonymous referees for their constructive criticisms and useful suggestions that help to improve the paper.
文摘In this paper we study a Class of nonconvex quadratically constrained quadratic programming problems generalized from relaxations of quadratic assignment problems. We show that each problem is polynomially solved. Strong duality holds if a redundant constraint is introduced. As an application, a new lower bound is proposed for the quadratic assignment problem.
基金supported by the National Key R&D Program of China(2020YFC1523302)the National Natural Science Foundation of China(61972041,62072045).
文摘We present an effective spectral matching method based on a shape association graph for finding region correspondences between two cel animation keyframes.We formulate the correspondence problem as an adapted quadratic assignment problem,which comprehensively considers both the intrinsic geometric and topology of regions to find the globally optimal correspondence.To simultaneously represent the geometric and topological similarities between regions,we propose a shape association graph(SAG),whose node attributes indicate the geometric distance between regions,and whose edge attributes indicate the topological distance between combined region pairs.We convert topological distance to geometric distance between geometric objects with topological features of the pairs,and introduce Kendall shape space to calculate the intrinsic geometric distance.By utilizing the spectral properties of the affinity matrix induced by the SAG,our approach can efficiently extract globally optimal region correspondences,even if shapes have inconsistent topology and severe deformation.It is also robust to shapes undergoing similarity transformations,and compatible with parallel computing techniques.
