Abstract Let G be a graph with m edges, minimum degree $\delta $ and containing no cycle of length 4. Answering a question of Bollobás and Scott, Fan et al. ‘Bisections of graphs without short ...cycles’, Combinatorics, Probability and Computing 27 (1) (2018), 44–59 showed that if (i) G is $2$ -connected, or (ii) $\delta \ge 3$ , or (iii) $\delta \ge 2$ and the girth of G is at least 5, then G admits a bisection such that $\max \{e(V_1),e(V_2)\}\le (1/4+o(1))m$ , where $e(V_i)$ denotes the number of edges of G with both ends in $V_i$ . Let $s\ge 2$ be an integer. In this note, we prove that if $\delta \ge 2s-1$ and G contains no $K_{2,s}$ as a subgraph, then G admits a bisection such that $\max \{e(V_1),e(V_2)\}\le (1/4+o(1))m$ .
Ising machines can find optimum or quasi-optimum solutions of combinatorial optimization problems efficiently and effectively. It is known that, when a good initial solution is given to an Ising ...machine, we can finally obtain a solution closer to the optimal solution. However, several Ising machines cannot directly accept an initial solution due to its computational nature. In this paper, we propose a method to give quasiinitial solutions into Ising machines that cannot directly accept them. The proposed method gives the positive or negative external magnetic field coefficients (magnetic field controlling term) based on the initial solutions and obtains a solution by using an Ising machine. Then, the magnetic field controlling term is re-calculated every time an Ising machine repeats the annealing process, and hence the solution is repeatedly improved on the basis of the previously obtained solution. The proposed method is applied to the capacitated vehicle routing problem with an additional constraint (constrained CVRP) and the max-cut problem. Experimental results show that the total path distance is reduced by 5.78% on average compared to the initial solution in the constrained CVRP and the sum of cut-edge weight is increased by 1.25% on average in the max-cut problem.
Max-cut is one of the most classic NP-hard combinatorial optimization problems. The symmetry nature of it leads to special difficulty in extracting meaningful configuration information for learning; ...none of the state-of-the-art algorithms has employed any learning operators. This paper proposes an original learning method for max-cut, namely post-flip edge-state learning (PF-ESL). Different from previous algorithms, PF-ESL regards edge-states (cut or not cut) rather than vertex-positions as the critical information of a configuration, and extracts their statistics over a population for learning. It is based on following observations. 1) Edges are the only factors considered by the objective function. 2) Edge-states keep invariant when rotating a local configuration to its symmetry position, but vertex-positions do not. These suggest that edge-states contain more meaningful information about a configuration than vertex-positions do. It is impossible to set the state of an edge without influencing some other edges’ states due to their dependencies. Therefore, instead of setting edge-states directly, PF-ESL samples the flips on vertices. Flips on vertices are sampled according to their capacities in increasing the similarity on edge-states between the given solution and a population. PF-ESL is employed in an EDA (Estimation of Distribution Algorithm) perturbation operator and a path-relinking operator. Experimental results show that our algorithm is competitive, and show that edge-state learning is value-added for both the two operators.
The main contributions of this paper are as follows. Firstly, previous state-of-the-art evolutionary algorithms for max-cut focus on vertex positions in their evolutionary operation, this paper proposes a new and more reasonable perspective suggesting that edge-states are the critical information of divided graphs rather than vertex positions, and introduces a novel method to measure and utilize their similarities based on it. Such a perspective is fundamental to learning based algorithms design for max-cut and other graph partitioning problems, and can shed lights on future researches. Furthermore, since max-cut is one of the most classic and fundamental NP hard problems, many real-world problems involve dividing graph data into different parts to optimize certain functions, this new perspective may inspire related or similar problems. Secondly, besides the original edge-states based perspective, and the post-flip edge-states learning (PFESL) operator based on it, our memetic algorithm also incorporates a novel evolutionary framework which alternates between EDA based Iterated Tabu search (ITS) and path relinking based genetic algorithm. Finally, the proposed algorithm provides competitive results on two mostly used benchmark sets and improves the best-known results of 6 most challenging instances.
•An original edge-state perspective for design learning operators for max-cut.•A novel learning operator to learn edge states.•A new evolutionary framework for max-cut.•It provides competitive results on two mostly used benchmark sets.
EXTREMAL CUTS OF SPARSE RANDOM GRAPHS Dembo, Amir; Montanari, Andrea; Sen, Subhabrata
The Annals of probability,
03/2017, Letnik:
45, Številka:
2
Journal Article
Recenzirano
Odprti dostop
For Erdős-Rényi random graphs with average degree γ, and uniformly random γ-regular graph on n vertices, we prove that with high probability the size of both the Max-Cut and maximum bisection are ...$n\left( {\frac{\gamma }{4} + P * \sqrt {\frac{\gamma }{4}} + o\left( {\sqrt \gamma } \right)} \right) + o\left( n \right)$ while the size of the minimum bisection is $n\left( {\frac{\gamma }{4} - P * \sqrt {\frac{\gamma }{4}} + o\left( {\sqrt \gamma } \right)} \right) + o\left( n \right)$. Our derivation relates the free energy of the anti-ferromagnetic Ising model on such graphs to that of the Sherrington-Kirkpatrick model, with P*≈0.7632 standing for the ground state energy of the latter, expressed analytically via Parisi's formula.
Max cut and semidefinite rank Mirka, Renee; Williamson, David P.
Operations research letters,
March 2024, 2024-03-00, Letnik:
53
Journal Article
Recenzirano
This paper considers the relationship between semidefinite programs (SDPs), matrix rank, and maximum cuts of graphs. Utilizing complementary slackness conditions for SDPs, we investigate when the ...rank 1 feasible solution corresponding to a max cut is the unique optimal solution to the Goemans-Williamson max cut SDP by showing the existence of an optimal dual solution with rank n−1. Our results consider connected bipartite graphs and graphs with multiple max cuts. We conclude with a conjecture for general graphs.
Optimization with photonic wave-based annealers Prabhakar, A.; Shah, P.; Gautham, U. ...
Philosophical transactions of the Royal Society of London. Series A: Mathematical, physical, and engineering sciences,
01/2023, Letnik:
381, Številka:
2241
Journal Article
Recenzirano
Many NP-hard combinatorial optimization (CO) problems can be cast as a quadratic unconstrained binary optimization model, which maps naturally to an Ising model. The final spin configuration in the ...Ising model can adiabatically arrive at a solution to a Hamiltonian, given a known set of interactions between spins. We enhance two photonic Ising machines (PIMs) and compare their performance against classical (Gurobi) and quantum (D-Wave) solvers. The temporal multiplexed coherent Ising machine (TMCIM) uses the bistable response of an electro-optic modulator to mimic the spin up and down states. We compare TMCIM performance on Max-cut problems. A spatial photonic Ising machine (SPIM) convolves the wavefront of a coherent laser beam with the pixel distribution of a spatial light modulator to adiabatically achieve a minimum energy configuration, and solve a number partitioning problem (NPP). Our computational results on Max-cut indicate that classical solvers are still a better choice, while our NPP results show that SPIM is better as the problem size increases. In both cases, connectivity in Ising hardware is crucial for performance. Our results also highlight the importance of better understanding which CO problems are most likely to benefit from which type of PIM.
This article is part of the theme issue ‘Quantum annealing and computation: challenges and perspectives’.
The Quantum Approximate Optimization Algorithm (QAOA) was proposed as a way of finding good, approximate solutions to hard combinatorial optimization problems. QAOA uses a hybrid approach. A ...parametrized quantum state is repeatedly prepared and measured on a quantum computer to estimate its average energy. Then, a classical optimizer, running in a classical computer, uses such information to decide on the new parameters that are then provided to the quantum computer. This process is iterated until some convergence criteria are met. Theoretically, almost all classical minimizers can be used in the hybrid scheme. However, their behaviour can vary greatly in both the quality of the final solution and the time they take to find it.
In this work, we study the performance of twelve different classical optimizers when used with QAOA to solve the maximum cut problem in graphs. We conduct a thorough set of tests on a quantum simulator both, with and without noise, and present results that show that some optimizers can be hundreds of times more efficient than others in some cases.
Though empirical testing is broadly used to evaluate heuristics, there are shortcomings with how it is often applied in practice. In a systematic review of Max-Cut and quadratic unconstrained binary ...optimization (QUBO) heuristics papers, we found only 4% publish source code, only 14% compare heuristics with identical termination criteria, and most experiments are performed with an artificial, homogeneous set of problem instances. To address these limitations, we implement and release as open-source a code-base of 10 Max-Cut and 27 QUBO heuristics. We perform heuristic evaluation using cloud computing on a library of 3,296 instances. This large-scale evaluation provides insight into the types of problem instances for which each heuristic performs well or poorly. Because no single heuristic outperforms all others across all problem instances, we use machine learning to predict which heuristic will work best on a previously unseen problem instance, a key question facing practitioners.
The online supplement is available at
https://doi.org/10.1287/ijoc.2017.0798
.
Recently, annealing processors based on the Ising model have received rising attention as efficient alternative hardware for solving combinatorial optimization problems. After mapping a problem to ...the hardware Ising model, we can observe the natural convergence behavior of the Ising model and find potential solutions to the problem. The quantum annealing processor has shown effectiveness in finding better solutions to the problems by using quantum bits (qubits) with annealing based on their quantum tunneling behaviors. However, the annealing processor based on the emerging quantum technology faces challenges such as limited scalability, high energy consumption, and operating costs due to the extremely low operating temperature. As a low-cost alternative, a CMOS annealing processor has been recently developed and drawn increasing attention thanks to the advantages over its quantum counterpart, including better scalability and lower energy consumption. In this work, we present a digital CMOS annealing processor with in-memory spin operators and register spins. The proposed CMOS annealing processor achieves ><inline-formula> <tex-math notation="LaTeX">10\times </tex-math></inline-formula> energy efficiency and faster operation than state-of-the-art works.
In this paper, a new formulation of the max-cut problem is proposed. Several semidefinite programming(SDP) relaxations of the max-cut problem are given and some relationships between them are put ...forward. Based on a new SDP relaxation, an algorithm is presented for finding a better approximate solution of the max-cut problem and we show the advantages of our model and algorithm with several examples.
PDF
