cimod
C++ library for a binary (and polynomial) quadratic model.
Loading...
Searching...
No Matches
binary_quadratic_model.hpp
Go to the documentation of this file.
1// Copyright 2020-2025 Jij Inc.
2
3// Licensed under the Apache License, Version 2.0 (the "License");
4// you may not use this file except in compliance with the License.
5// You may obtain a copy of the License at
6
7// http://www.apache.org/licenses/LICENSE-2.0
8
9// Unless required by applicable law or agreed to in writing, software
10// distributed under the License is distributed on an "AS IS" BASIS,
11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12// See the License for the specific language governing permissions and
13// limitations under the License.
14
77#pragma once
78
79#include <algorithm>
80#include <cassert>
81#include <cstdint>
82#include <functional>
83#include <iostream>
84#include <limits>
85#include <set>
86#include <string>
87#include <tuple>
88#include <type_traits>
89#include <typeinfo>
90#include <unordered_map>
91#include <unordered_set>
92#include <utility>
93#include <vector>
94
95#include <Eigen/Dense>
96#include <Eigen/Sparse>
97
99#include "cimod/hash.hpp"
100#include "cimod/json.hpp"
101#include "cimod/utilities.hpp"
102#include "cimod/vartypes.hpp"
103
104namespace cimod {
110 template<typename IndexType, typename FloatType>
111 using Linear = std::unordered_map<IndexType, FloatType>;
112
118 template<typename IndexType, typename FloatType>
119 using Quadratic = std::unordered_map<std::pair<IndexType, IndexType>, FloatType, pair_hash>;
120
126 template<typename IndexType, typename FloatType>
127 using Adjacency = std::unordered_map<IndexType, std::unordered_map<IndexType, FloatType>>;
128
134 template<typename IndexType>
135 using Sample = std::unordered_map<IndexType, int32_t>;
136
137 struct Dense { };
138 struct Sparse { };
139
147 template<typename IndexType, typename FloatType, typename DataType>
149 private:
157 template<typename T, typename U>
158 using dispatch_t = std::enable_if_t<std::is_same_v<T, U>, std::nullptr_t>;
159
160 public:
167 using DenseMatrix = Eigen::Matrix<FloatType, Eigen::Dynamic, Eigen::Dynamic, Eigen::RowMajor>;
168 using SparseMatrix = Eigen::SparseMatrix<FloatType, Eigen::RowMajor>;
169 using SpIter = typename SparseMatrix::InnerIterator;
170
171 using Matrix = std::conditional_t<std::is_same_v<DataType, Dense>, DenseMatrix, SparseMatrix>;
172
173 using Vector = Eigen::Matrix<FloatType, Eigen::Dynamic, 1>;
174
175 protected:
191
196 std::vector<IndexType> _idx_to_label;
197
201 std::unordered_map<IndexType, size_t> _label_to_idx;
202
208
214
218 inline void _set_label_to_idx() {
219 // reset
220 _label_to_idx.clear();
221 // initialize
222 for ( size_t i = 0; i < _idx_to_label.size(); i++ ) {
224 }
225 }
226
237 template<typename T = DataType>
238 inline FloatType &_quadmat_get( size_t i, size_t j, dispatch_t<T, Dense> = nullptr ) {
239 return _quadmat( i, j );
240 }
241
252 template<typename T = DataType>
253 inline FloatType _quadmat_get( size_t i, size_t j, dispatch_t<T, Dense> = nullptr ) const {
254 return _quadmat( i, j );
255 }
256
267 template<typename T = DataType>
268 inline FloatType &_quadmat_get( size_t i, size_t j, dispatch_t<T, Sparse> = nullptr ) {
269 return _quadmat.coeffRef( i, j );
270 }
271
282 template<typename T = DataType>
283 inline FloatType _quadmat_get( size_t i, size_t j, dispatch_t<T, Sparse> = nullptr ) const {
284 return _quadmat.coeff( i, j );
285 }
286
296 size_t i = _label_to_idx.at( label_i );
297 size_t j = _label_to_idx.at( label_j );
298 if ( i != j )
299 return _quadmat_get( std::min( i, j ), std::max( i, j ) );
300 else
301 throw std::runtime_error( "No self-loop (mat(i,i)) allowed" );
302 }
303
312 size_t i = _label_to_idx.at( label_i );
313 return _quadmat_get( i, _quadmat.rows() - 1 );
314 }
315
325 size_t i = _label_to_idx.at( label_i );
326 size_t j = _label_to_idx.at( label_j );
327
328 if ( i != j )
329 return _quadmat_get( std::min( i, j ), std::max( i, j ) );
330 else
331 throw std::runtime_error( "No self-loop (mat(i,i)) allowed" );
332 }
333
341 inline FloatType _mat( IndexType label_i ) const {
342 size_t i = _label_to_idx.at( label_i );
343 return _quadmat_get( i, _quadmat.rows() - 1 );
344 }
345
351 template<typename T = DataType>
352 inline FloatType _max_linear( dispatch_t<T, Dense> = nullptr ) const {
353 size_t N = _quadmat.rows();
354 return _quadmat.block( 0, N - 1, N - 1, 1 ).maxCoeff();
355 }
356
362 template<typename T = DataType>
364 size_t N = _quadmat.rows();
365 return _quadmat.block( 0, 0, N - 1, N - 1 ).maxCoeff();
366 }
367
373 template<typename T = DataType>
374 inline FloatType _min_linear( dispatch_t<T, Dense> = nullptr ) const {
375 size_t N = _quadmat.rows();
376 return _quadmat.block( 0, N - 1, N - 1, 1 ).minCoeff();
377 }
378
384 template<typename T = DataType>
386 size_t N = _quadmat.rows();
387 return _quadmat.block( 0, 0, N - 1, N - 1 ).minCoeff();
388 }
389
395 template<typename T = DataType>
396 inline FloatType _max_linear( dispatch_t<T, Sparse> = nullptr ) const {
397 size_t N = _quadmat.rows();
398 SparseMatrix mat( N - 1, 1 );
399 mat = _quadmat.block( 0, N - 1, N - 1, 1 );
400 return mat.coeffs().maxCoeff();
401 }
402
408 template<typename T = DataType>
410 size_t N = _quadmat.rows();
411 SparseMatrix mat( N - 1, N - 1 );
412 mat = _quadmat.block( 0, 0, N - 1, N - 1 );
413 return mat.coeffs().maxCoeff();
414 }
415
421 template<typename T = DataType>
422 inline FloatType _min_linear( dispatch_t<T, Sparse> = nullptr ) const {
423 size_t N = _quadmat.rows();
424 SparseMatrix mat( N - 1, 1 );
425 mat = _quadmat.block( 0, N - 1, N - 1, 1 );
426 return mat.coeffs().minCoeff();
427 }
428
434 template<typename T = DataType>
436 size_t N = _quadmat.rows();
437 SparseMatrix mat( N - 1, N - 1 );
438 mat = _quadmat.block( 0, 0, N - 1, N - 1 );
439 return mat.coeffs().minCoeff();
440 }
441
447 template<typename T = DataType>
449 size_t i = _label_to_idx.at( label_i );
450 // define temp mat
451 size_t N = _quadmat.rows() + 1;
452 Matrix tempmat = Matrix( N, N );
453 tempmat.setZero();
454 // copy elements to new matrix
455 tempmat.block( 0, 0, i, i ) = _quadmat.block( 0, 0, i, i );
456 tempmat.block( 0, i + 1, i, N - i - 1 ) = _quadmat.block( 0, i, i, N - i - 1 );
457 tempmat.block( i + 1, i + 1, N - i - 1, N - i - 1 ) = _quadmat.block( i, i, N - i - 1, N - i - 1 );
458
460 }
461
467 template<typename T = DataType>
469 size_t i = _label_to_idx.at( label_i );
470 // define temp mat
471 size_t N = _quadmat.rows() + 1;
472 // Matrix tempmat = Matrix(N, N);
473 // copy elements to new matrix
474 // tempmat.block(0,0,i,i) = _quadmat.block(0,0,i,i);
475 // tempmat.block(0,i+1,i,N-i-1) = _quadmat.block(0,i,i,N-i-1);
476 // tempmat.block(i+1,i+1,N-i-1,N-i-1) = _quadmat.block(i,i,N-i-1,N-i-1);
477
478 std::vector<Eigen::Triplet<FloatType>> triplets;
479 triplets.reserve( _quadmat.nonZeros() );
480
481 for ( int k = 0; k < _quadmat.outerSize(); k++ ) {
482 for ( SpIter it( _quadmat, k ); it; ++it ) {
483 size_t r = it.row();
484 size_t c = it.col();
485 FloatType val = it.value();
486
487 if ( r >= i && c >= i ) {
488 triplets.emplace_back( r + 1, c + 1, val );
489 } else if ( r >= i ) {
490 triplets.emplace_back( r + 1, c, val );
491 } else if ( c >= i ) {
492 triplets.emplace_back( r, c + 1, val );
493 } else {
494 triplets.emplace_back( r, c, val );
495 }
496 }
497 }
498
499 _quadmat.resize( N, N );
500 _quadmat.setFromTriplets( triplets.begin(), triplets.end() );
501 }
502
508 template<typename T = DataType>
510 size_t i = _label_to_idx.at( label_i );
511 // define temp mat
512 size_t N = _quadmat.rows();
513 Matrix tempmat = Matrix( N - 1, N - 1 );
514 tempmat.setZero();
515 // copy elements to new matrix
516 tempmat.block( 0, 0, i, i ) = _quadmat.block( 0, 0, i, i );
517 tempmat.block( 0, i, i, N - i - 1 ) = _quadmat.block( 0, i + 1, i, N - i - 1 );
518 tempmat.block( i, i, N - i - 1, N - i - 1 ) = _quadmat.block( i + 1, i + 1, N - i - 1, N - i - 1 );
519
521 }
522
528 template<typename T = DataType>
530 size_t i = _label_to_idx.at( label_i );
531 // define temp mat
532 size_t N = _quadmat.rows();
533 // copy elements to new matrix
534 // tempmat.block(0,0,i,i) = _quadmat.block(0,0,i,i);
535 // tempmat.block(0,i,i,N-i-1) = _quadmat.block(0,i+1,i,N-i-1);
536 // tempmat.block(i,i,N-i-1,N-i-1) = _quadmat.block(i+1,i+1,N-i-1,N-i-1);
537
538 std::vector<Eigen::Triplet<FloatType>> triplets;
539 triplets.reserve( _quadmat.nonZeros() );
540
541 for ( int k = 0; k < _quadmat.outerSize(); k++ ) {
542 for ( SpIter it( _quadmat, k ); it; ++it ) {
543 size_t r = it.row();
544 size_t c = it.col();
545 FloatType val = it.value();
546
547 if ( r == i || c == i )
548 continue;
549
550 if ( r > i && c > i ) {
551 triplets.emplace_back( r - 1, c - 1, val );
552 } else if ( r > i ) {
553 triplets.emplace_back( r - 1, c, val );
554 } else if ( c > i ) {
555 triplets.emplace_back( r, c - 1, val );
556 } else {
557 triplets.emplace_back( r, c, val );
558 }
559 }
560 }
561
562 _quadmat.resize( N - 1, N - 1 );
563 _quadmat.setFromTriplets( triplets.begin(), triplets.end() );
564 }
565
573 if ( _label_to_idx.find( label_i ) == _label_to_idx.end() ) {
574 // add label_i
575 _idx_to_label.push_back( label_i );
576 std::sort( _idx_to_label.begin(), _idx_to_label.end() );
578
580 }
581 }
582
591 inline void _delete_label( IndexType label_i, bool force_delete = true ) {
592 auto position = std::find( _idx_to_label.begin(), _idx_to_label.end(), label_i );
593 if ( position != _idx_to_label.end() ) {
594 if ( force_delete == false ) {
595 // check if there are corresponding nonzero elements
596 size_t i = std::distance( _idx_to_label.begin(), position );
597 if ( _quadmat.col( i ).squaredNorm() > std::numeric_limits<FloatType>::epsilon()
598 || _quadmat.row( i ).squaredNorm() > std::numeric_limits<FloatType>::epsilon() ) {
599 // exists nonzero elements
600 return;
601 }
602 }
603 // delete from matrix first
605 // add label_i
606 _idx_to_label.erase( position );
607 // already sorted
608 // std::sort(_idx_to_label.begin(), _idx_to_label.end());
610 }
611 }
612
619 template<typename T = DataType>
621 const Linear<IndexType, FloatType> &linear,
622 const Quadratic<IndexType, FloatType> &quadratic,
623 dispatch_t<T, Dense> = nullptr ) {
624 // gather labels
625 std::unordered_set<IndexType> labels;
626
627 for ( const auto &kv : linear ) {
628 labels.insert( kv.first );
629 }
630
631 for ( const auto &kv : quadratic ) {
632 labels.insert( kv.first.first );
633 labels.insert( kv.first.second );
634 }
635
636 // init label <-> index conversion variables
637 _idx_to_label = std::vector<IndexType>( labels.begin(), labels.end() );
638 std::sort( _idx_to_label.begin(), _idx_to_label.end() );
640
641 // initialize _quadmat
642 size_t mat_size = _idx_to_label.size() + 1;
644 _quadmat.fill( 0 );
645 _quadmat_get( mat_size - 1, mat_size - 1 ) = 1;
646
647 // copy linear and quadratic to _quadmat
648 for ( const auto &kv : linear ) {
649 IndexType key = kv.first;
650 FloatType val = kv.second;
651 _mat( key ) += val;
652 }
653
654 for ( const auto &kv : quadratic ) {
655 std::pair<IndexType, IndexType> key = kv.first;
656 FloatType val = kv.second;
657 _mat( key.first, key.second ) += val;
658 }
659 }
660
667 template<typename T = DataType>
669 const Linear<IndexType, FloatType> &linear,
670 const Quadratic<IndexType, FloatType> &quadratic,
671 dispatch_t<T, Sparse> = nullptr ) {
672 // gather labels
673 std::unordered_set<IndexType> labels;
674
675 for ( const auto &kv : linear ) {
676 labels.insert( kv.first );
677 }
678
679 for ( const auto &kv : quadratic ) {
680 labels.insert( kv.first.first );
681 labels.insert( kv.first.second );
682 }
683
684 // init label <-> index conversion variables
685 _idx_to_label = std::vector<IndexType>( labels.begin(), labels.end() );
686 std::sort( _idx_to_label.begin(), _idx_to_label.end() );
688
689 // initialize _quadmat
690 size_t mat_size = _idx_to_label.size() + 1;
692
693 std::vector<Eigen::Triplet<FloatType>> triplets;
694 const size_t buffer = 5;
695 triplets.reserve( linear.size() + quadratic.size() + buffer );
696
697 // set triplets to _quadmat
698 for ( const auto &kv : linear ) {
699 size_t idx1 = _label_to_idx.at( kv.first );
700 size_t idx2 = mat_size - 1;
701 FloatType val = kv.second;
702
703 // NOTE: duplicated elements are summed up.
704 triplets.emplace_back( std::min( idx1, idx2 ), std::max( idx1, idx2 ), val );
705 }
706
707 for ( const auto &kv : quadratic ) {
708 size_t idx1 = _label_to_idx.at( kv.first.first );
709 size_t idx2 = _label_to_idx.at( kv.first.second );
710 FloatType val = kv.second;
711
712 // NOTE: duplicated elements are summed up.
713 triplets.emplace_back( std::min( idx1, idx2 ), std::max( idx1, idx2 ), val );
714 }
715
716 triplets.emplace_back( mat_size - 1, mat_size - 1, 1 );
717
718 _quadmat.setFromTriplets( triplets.begin(), triplets.end() );
719 }
720
728 template<typename T = DataType>
730
731 size_t mat_size = _idx_to_label.size() + 1;
732
733 if ( ( size_t )mat.rows() == _idx_to_label.size() + 1 ) {
734 if ( fix_format == false ) {
735 _quadmat = mat;
736 } else {
738 _quadmat += mat.template triangularView<Eigen::StrictlyLower>().transpose();
739 }
740 } else if ( ( size_t )mat.rows() == _idx_to_label.size() ) {
741 _quadmat.block( 0, 0, mat_size - 1, mat_size - 1 ) += mat.template triangularView<Eigen::StrictlyUpper>();
742 _quadmat.block( 0, 0, mat_size - 1, mat_size - 1 )
743 += mat.template triangularView<Eigen::StrictlyLower>().transpose();
744 // local fields
745 Vector loc = mat.diagonal();
746 _quadmat.block( 0, mat_size - 1, mat_size - 1, 1 ) += loc;
747 } else {
748 throw std::runtime_error( "the number of variables and dimension do not match." );
749 }
750 }
751
759 template<typename T = DataType>
761
762 // generate sparse matrix
764
765 size_t mat_size = _idx_to_label.size() + 1;
766
767 if ( ( size_t )mat.rows() == _idx_to_label.size() + 1 ) {
768 if ( fix_format == false ) {
769 _quadmat = mat.sparseView();
770 } else {
771 sparse_mat = mat.sparseView();
773 sparse_mat = mat.sparseView().transpose();
775 }
776 } else if ( ( size_t )mat.rows() == _idx_to_label.size() ) {
777 // generate Dense Matrix
778 DenseMatrix temp_mat = DenseMatrix::Zero( mat_size, mat_size );
779
780 temp_mat.block( 0, 0, mat_size - 1, mat_size - 1 ) += mat.template triangularView<Eigen::StrictlyUpper>();
781 temp_mat.block( 0, 0, mat_size - 1, mat_size - 1 )
782 += mat.template triangularView<Eigen::StrictlyLower>().transpose();
783 // local fields
784 Vector loc = mat.diagonal();
785 temp_mat.block( 0, mat_size - 1, mat_size - 1, 1 ) += loc;
786
787 // insert in sparsematrix
788 _quadmat += temp_mat.sparseView();
789 } else {
790 throw std::runtime_error( "the number of variables and dimension do not match." );
791 }
792 }
793
834 inline void _initialize_quadmat( const DenseMatrix &mat, const std::vector<IndexType> &labels_vec, bool fix_format ) {
835
836 // initlaize label <-> index dict
837 std::unordered_set<IndexType> labels( labels_vec.begin(), labels_vec.end() );
838 _idx_to_label = std::vector<IndexType>( labels.begin(), labels.end() );
839 std::sort( _idx_to_label.begin(), _idx_to_label.end() );
841
842 if ( mat.rows() != mat.cols() ) {
843 throw std::runtime_error( "matrix must be a square matrix" );
844 }
845
846 size_t mat_size = _idx_to_label.size() + 1;
848 _quadmat.setZero();
850 _quadmat_get( mat_size - 1, mat_size - 1 ) = 1;
851 }
852
855 for ( size_t i = 0; i < _idx_to_label.size(); i++ ) {
857 if ( val != 0 )
859 }
860
861 return ret_linear;
862 }
863
864 template<typename T = DataType>
867 for ( size_t i = 0; i < _idx_to_label.size(); i++ ) {
868 for ( size_t j = i + 1; j < _idx_to_label.size(); j++ ) {
870 if ( val != 0 )
871 ret_quadratic[ std::make_pair( _idx_to_label[ i ], _idx_to_label[ j ] ) ] = val;
872 }
873 }
874
875 return ret_quadratic;
876 }
877
878 template<typename T = DataType>
881
882 for ( int k = 0; k < _quadmat.outerSize(); k++ ) {
883 // k -> row index
884 for ( SpIter it( _quadmat, k ); it; ++it ) {
885 size_t r = it.row();
886 size_t c = it.col();
887 FloatType val = it.value();
888
890 ret_quadratic[ std::make_pair( _idx_to_label[ r ], _idx_to_label[ c ] ) ] = val;
891 }
892 }
893
894 return ret_quadratic;
895 }
896
914 inline void _initialize_quadmat( const SparseMatrix &mat, const std::vector<IndexType> &labels_vec ) {
915 this->_quadmat = mat;
916 std::unordered_set<IndexType> labels( labels_vec.begin(), labels_vec.end() );
917 _idx_to_label = std::vector<IndexType>( labels.begin(), labels.end() );
918 std::sort( _idx_to_label.begin(), _idx_to_label.end() );
920 }
921
936 template<typename T = DataType>
937 inline void _spin_to_binary( dispatch_t<T, Dense> = nullptr ) {
938 size_t num_variables = _idx_to_label.size();
940 // calc col(row)wise-sum ((num_variables, 1))
941 // Vector colwise_sum = _quadmat.block(0,0,num_variables,num_variables).colwise().sum();
943 for ( size_t i = 0; i < num_variables; i++ ) {
944 colwise_sum( i ) = _quadmat.block( 0, 0, i, num_variables ).col( i ).sum();
945 }
946
947 Vector rowwise_sum = _quadmat.block( 0, 0, num_variables, num_variables ).rowwise().sum();
948
950
951 // offset
952 m_offset += colwise_sum.sum() - local_field.sum();
953
954 // local field
955 _quadmat.block( 0, num_variables, num_variables, 1 ) = 2 * local_field - 2 * ( colwise_sum + rowwise_sum );
956
957 // quadratic
958 _quadmat.block( 0, 0, num_variables, num_variables ) *= 4;
959 }
960
975 template<typename T = DataType>
976 inline void _spin_to_binary( dispatch_t<T, Sparse> = nullptr ) {
977 size_t num_variables = _idx_to_label.size();
979 // calc col(row)wise-sum ((num_variables, 1))
980 // Vector colwise_sum = _quadmat.block(0,0,num_variables,num_variables).colwise().sum();
981 // Vector rowwise_sum = _quadmat.block(0,0,num_variables,num_variables).rowwise().sum();
982
985 colwise_sum.setZero();
986 rowwise_sum.setZero();
987
988 for ( int k = 0; k < _quadmat.outerSize(); k++ ) {
989 // k -> row index
990 for ( SpIter it( _quadmat, k ); it; ++it ) {
991 size_t r = it.row();
992 size_t c = it.col();
993 FloatType val = it.value();
994
995 if ( ( r < num_variables ) && ( c < num_variables ) ) {
996 colwise_sum( c ) += val;
997 rowwise_sum( r ) += val;
998 }
999 }
1000 }
1001
1003
1004 // offset
1005 m_offset += colwise_sum.sum() - local_field.sum();
1006
1007 // local field
1008 //_quadmat.block(0,num_variables,num_variables,1)
1009 // = 2 * local_field - 2 * (colwise_sum + rowwise_sum);
1010
1011 // quadratic
1012 //_quadmat.block(0,0,num_variables,num_variables) *= 4;
1013
1015
1016 std::vector<Eigen::Triplet<FloatType>> triplets;
1017 triplets.reserve( _quadmat.nonZeros() );
1018 for ( size_t r = 0; r < num_variables; r++ ) {
1019 triplets.emplace_back( r, num_variables, new_local_field( r ) );
1020 }
1021
1022 for ( int k = 0; k < _quadmat.outerSize(); k++ ) {
1023 // k -> row index
1024 for ( SpIter it( _quadmat, k ); it; ++it ) {
1025 size_t r = it.row();
1026 size_t c = it.col();
1027 FloatType val = it.value();
1028
1029 if ( ( r < num_variables ) && ( c < num_variables ) ) {
1030 triplets.emplace_back( r, c, 4 * val );
1031 }
1032 }
1033 }
1034
1035 triplets.emplace_back( num_variables, num_variables, 1 );
1036
1038 _quadmat.setFromTriplets( triplets.begin(), triplets.end() );
1039 }
1040
1055 template<typename T = DataType>
1056 inline void _binary_to_spin( dispatch_t<T, Dense> = nullptr ) {
1057 size_t num_variables = _idx_to_label.size();
1059 // calc col(row)wise-sum ((num_variables, 1))
1060 // Vector colwise_sum = _quadmat.block(0,0,num_variables,num_variables).colwise().sum();
1062 for ( size_t i = 0; i < num_variables; i++ ) {
1063 colwise_sum( i ) = _quadmat.block( 0, 0, i, num_variables ).col( i ).sum();
1064 }
1065 Vector rowwise_sum = _quadmat.block( 0, 0, num_variables, num_variables ).rowwise().sum();
1066
1068
1069 // offset
1070 m_offset += 0.25 * colwise_sum.sum() + 0.5 * local_field.sum();
1071
1072 // local field
1073 _quadmat.block( 0, num_variables, num_variables, 1 ) = 0.5 * local_field + 0.25 * ( colwise_sum + rowwise_sum );
1074
1075 // quadratic
1076 _quadmat.block( 0, 0, num_variables, num_variables ) *= 0.25;
1077 }
1078
1093 template<typename T = DataType>
1094 inline void _binary_to_spin( dispatch_t<T, Sparse> = nullptr ) {
1095 size_t num_variables = _idx_to_label.size();
1097 // calc col(row)wise-sum ((num_variables, 1))
1098 // Vector colwise_sum = _quadmat.block(0,0,num_variables,num_variables).colwise().sum();
1099 // Vector rowwise_sum = _quadmat.block(0,0,num_variables,num_variables).rowwise().sum();
1100
1103 colwise_sum.setZero();
1104 rowwise_sum.setZero();
1105
1106 for ( int k = 0; k < _quadmat.outerSize(); k++ ) {
1107 // k -> row index
1108 for ( SpIter it( _quadmat, k ); it; ++it ) {
1109 size_t r = it.row();
1110 size_t c = it.col();
1111 FloatType val = it.value();
1112
1113 if ( ( r < num_variables ) && ( c < num_variables ) ) {
1114 colwise_sum( c ) += val;
1115 rowwise_sum( r ) += val;
1116 }
1117 }
1118 }
1119
1121
1122 // offset
1123 m_offset += 0.25 * colwise_sum.sum() + 0.5 * local_field.sum();
1124
1125 // local field
1126 //_quadmat.block(0,num_variables,num_variables,1)
1127 // = 0.5 * local_field + 0.25 * (colwise_sum + rowwise_sum);
1128
1129 // quadratic
1130 // quadmat.block(0,0,num_variables,num_variables) *= 0.25;
1131
1133
1134 std::vector<Eigen::Triplet<FloatType>> triplets;
1135 triplets.reserve( _quadmat.nonZeros() );
1136 for ( size_t r = 0; r < num_variables; r++ ) {
1137 triplets.emplace_back( r, num_variables, new_local_field( r ) );
1138 }
1139
1140 for ( int k = 0; k < _quadmat.outerSize(); k++ ) {
1141 // k -> row index
1142 for ( SpIter it( _quadmat, k ); it; ++it ) {
1143 size_t r = it.row();
1144 size_t c = it.col();
1145 FloatType val = it.value();
1146
1147 if ( ( r < num_variables ) && ( c < num_variables ) ) {
1148 triplets.emplace_back( r, c, 0.25 * val );
1149 }
1150 }
1151 }
1152
1153 triplets.emplace_back( num_variables, num_variables, 1 );
1154
1155 _quadmat.setFromTriplets( triplets.begin(), triplets.end() );
1156 }
1157
1158 public:
1168 const Linear<IndexType, FloatType> &linear,
1169 const Quadratic<IndexType, FloatType> &quadratic,
1170 const FloatType &offset,
1171 const Vartype vartype ) :
1172 m_offset( offset ),
1173 m_vartype( vartype ) {
1174 _initialize_quadmat( linear, quadratic );
1175 }
1176
1186 const Linear<IndexType, FloatType> &linear,
1187 const Quadratic<IndexType, FloatType> &quadratic,
1188 const Vartype vartype ) :
1189 BinaryQuadraticModel( linear, quadratic, 0.0, vartype ) {
1190 }
1191
1202 const Eigen::Ref<const DenseMatrix> &mat,
1203 const std::vector<IndexType> &labels_vec,
1204 const FloatType &offset,
1205 const Vartype vartype,
1206 bool fix_format = true ) :
1207 m_offset( offset ),
1208 m_vartype( vartype ) {
1210 }
1211
1221 const Eigen::Ref<const DenseMatrix> &mat,
1222 const std::vector<IndexType> &labels_vec,
1223 const Vartype vartype,
1224 bool fix_format = true ) :
1225 BinaryQuadraticModel( mat, labels_vec, 0.0, vartype, fix_format ) {
1226 }
1227
1239 const SparseMatrix &mat,
1240 const std::vector<IndexType> &labels_vec,
1241 const FloatType &offset,
1242 const Vartype vartype ) :
1243 m_offset( offset ),
1244 m_vartype( vartype ) {
1246 }
1247
1257 BinaryQuadraticModel( const SparseMatrix &mat, const std::vector<IndexType> &labels_vec, const Vartype vartype ) :
1258 BinaryQuadraticModel( mat, labels_vec, 0.0, vartype ) {
1259 }
1260
1262
1268 size_t get_num_variables() const {
1269 return _idx_to_label.size();
1270 }
1271
1278 size_t length() const {
1279 return get_num_variables();
1280 }
1281
1288 bool contains( const IndexType &v ) const {
1289 if ( _label_to_idx.find( v ) != _label_to_idx.end() ) {
1290 return true;
1291 } else {
1292 return false;
1293 }
1294 }
1295
1302 return _mat( label_i );
1303 }
1304
1313
1322
1331
1338 return this->m_offset;
1339 }
1340
1347 return this->m_vartype;
1348 }
1349
1355 const std::vector<IndexType> &get_variables() const {
1356 return this->_idx_to_label;
1357 }
1358
1368
1369 /* Update methods */
1370
1377 void add_variable( const IndexType &v, const FloatType &bias ) {
1378 // add new label if not exist
1379 _add_new_label( v );
1380 _mat( v ) += bias;
1381 }
1382
1389 for ( auto &it : linear ) {
1390 add_variable( it.first, it.second );
1391 }
1392 }
1393
1401 void add_interaction( const IndexType &u, const IndexType &v, const FloatType &bias ) {
1402 // add labels u and v
1403 _add_new_label( u );
1404 _add_new_label( v );
1405 _mat( u, v ) += bias;
1406 }
1407
1414 for ( auto &it : quadratic ) {
1415 add_interaction( it.first.first, it.first.second, it.second );
1416 }
1417 }
1418
1424 void remove_variable( const IndexType &v ) {
1425 _delete_label( v );
1426 }
1427
1433 void remove_variables_from( const std::vector<IndexType> &variables ) {
1434 for ( auto &it : variables ) {
1436 }
1437 }
1438
1445 void remove_interaction( const IndexType &u, const IndexType &v ) {
1446 _mat( u, v ) = 0;
1447 _delete_label( u, false );
1448 _delete_label( v, false );
1449 }
1450
1456 void remove_interactions_from( const std::vector<std::pair<IndexType, IndexType>> &interactions ) {
1457 for ( auto &it : interactions ) {
1458 remove_interaction( it.first, it.second );
1459 }
1460 }
1461
1467 void add_offset( const FloatType &offset ) {
1468 m_offset += offset;
1469 }
1470
1475 add_offset( -m_offset );
1476 }
1477
1486 void scale(
1487 const FloatType &scalar,
1488 const std::vector<IndexType> &ignored_variables = {},
1489 const std::vector<std::pair<IndexType, IndexType>> &ignored_interactions = {},
1490 const bool ignored_offset = false ) {
1491 if ( scalar == 0.0 )
1492 throw std::runtime_error( "scalar must not be zero" );
1493
1494 // scale
1495 _quadmat *= scalar;
1496
1497 // revert scale of linear
1498 for ( const auto &it : ignored_variables ) {
1499 _mat( it ) *= 1.0 / scalar;
1500 }
1501
1502 // revert scale of quadratic
1503 for ( const auto &it : ignored_interactions ) {
1504 _mat( it.first, it.second ) *= 1.0 / scalar;
1505 }
1506
1507 // scaling offset
1508 if ( !ignored_offset ) {
1509 m_offset *= scalar;
1510 }
1511 }
1512
1526 const std::pair<FloatType, FloatType> &bias_range = { 1.0, 1.0 },
1527 const bool use_quadratic_range = false,
1528 const std::pair<FloatType, FloatType> &quadratic_range = { 1.0, 1.0 },
1529 const std::vector<IndexType> &ignored_variables = {},
1530 const std::vector<std::pair<IndexType, IndexType>> &ignored_interactions = {},
1531 const bool ignored_offset = false ) {
1532 // parse range
1533 std::pair<FloatType, FloatType> l_range = bias_range;
1534 std::pair<FloatType, FloatType> q_range;
1535 if ( !use_quadratic_range ) {
1537 } else {
1539 }
1540
1541 // calculate scaling value
1546
1547 std::vector<FloatType> v_scale
1548 = { lin_min / l_range.first, lin_max / l_range.second, quad_min / q_range.first, quad_max / q_range.second };
1549
1550 FloatType inv_scale = *std::max_element( v_scale.begin(), v_scale.end() );
1551
1552 // scaling
1553 if ( inv_scale != 0.0 ) {
1555 }
1556 }
1557
1564 void fix_variable( const IndexType &v, const int32_t &value ) {
1565 std::vector<std::pair<IndexType, IndexType>> interactions;
1566 const Quadratic<IndexType, FloatType> &quadratic = this->get_quadratic();
1567 for ( const auto &it : quadratic ) {
1568 if ( it.first.first == v ) {
1569 add_variable( it.first.second, value * it.second );
1570 interactions.push_back( it.first );
1571 } else if ( it.first.second == v ) {
1572 add_variable( it.first.first, value * it.second );
1573 interactions.push_back( it.first );
1574 }
1575 }
1577 add_offset( _mat( v ) * value );
1578 remove_variable( v );
1579 }
1580
1586 void fix_variables( const std::vector<std::pair<IndexType, int32_t>> &fixed ) {
1587 for ( auto &it : fixed ) {
1588 fix_variable( it.first, it.second );
1589 }
1590 }
1591
1597 void flip_variable( const IndexType &v ) {
1598
1599 if ( m_vartype == Vartype::SPIN ) {
1600 size_t i = _label_to_idx.at( v );
1601 _quadmat.row( i ) *= -1;
1602 _quadmat.col( i ) *= -1;
1603 } else if ( m_vartype == Vartype::BINARY ) {
1604 // change vartype to spin
1606
1607 size_t i = _label_to_idx.at( v );
1608 _quadmat.row( i ) *= -1;
1609 _quadmat.col( i ) *= -1;
1610
1611 // change vartype to binary
1613 }
1614 }
1615
1617 // * @brief Enforce u, v being the same variable in a binary quadratic model. (currently disabled)
1618 // *
1619 // * @param u
1620 // * @param v
1621 // */
1622 // void contract_variables
1623 //(
1624 // const IndexType &u,
1625 // const IndexType &v
1626 //)
1627 //{
1628
1629 // if(this->m_vartype == Vartype::BINARY){
1630 // // the quadratic bias becomes linear
1631 // _mat(u) += _mat(v) + _mat(u,v);
1632 // }
1633 // else if(this->m_vartype == Vartype::SPIN){
1634 // _mat(u) += _mat(v);
1635 // m_offset += _mat(u,v);
1636 // }
1637 // this->remove_interaction(u,v);
1638
1639 //}
1640
1641 /* Transformations */
1642
1649 void change_vartype( const Vartype &vartype ) {
1650 if ( m_vartype == Vartype::BINARY && vartype == Vartype::SPIN ) // binary -> spin
1651 {
1653 } else if ( m_vartype == Vartype::SPIN && vartype == Vartype::BINARY ) // spin -> binary
1654 {
1656 }
1657 }
1658
1670 if ( inplace == true ) {
1671 this->change_vartype( vartype );
1672 }
1673 new_bqm.change_vartype( vartype );
1674
1675 return new_bqm;
1676 }
1677
1678 /* Methods */
1679
1688 // initialize vector
1689 Vector s = Vector::Zero( _quadmat.rows() );
1690 for ( const auto &elem : sample ) {
1691 s[ _label_to_idx.at( elem.first ) ] = elem.second;
1692 }
1693 s[ _quadmat.rows() - 1 ] = 1;
1694
1695 return en + ( s.transpose() * _quadmat * s ) - 1;
1696 }
1697
1704 std::vector<FloatType> energies( const std::vector<Sample<IndexType>> &samples_like ) const {
1705 std::vector<FloatType> en_vec;
1706 for ( auto &it : samples_like ) {
1707 en_vec.push_back( energy( it ) );
1708 }
1709 return en_vec;
1710 }
1711
1712 /* Conversions */
1718 std::tuple<Quadratic<IndexType, FloatType>, FloatType> to_qubo() {
1719 // change vartype to binary
1721
1722 const Linear<IndexType, FloatType> &linear = bqm.get_linear();
1723 Quadratic<IndexType, FloatType> Q = bqm.get_quadratic();
1724 FloatType offset = bqm.get_offset();
1725 for ( const auto &it : linear ) {
1726 Q[ std::make_pair( it.first, it.first ) ] = it.second;
1727 }
1728 return std::make_tuple( Q, offset );
1729 }
1730
1743
1744 for ( auto &&elem : Q ) {
1745 const auto &key = elem.first;
1746 const auto &value = elem.second;
1747 if ( key.first == key.second ) {
1748 linear[ key.first ] = value;
1749 } else {
1750 quadratic[ std::make_pair( key.first, key.second ) ] = value;
1751 }
1752 }
1753
1754 return BinaryQuadraticModel<IndexType, FloatType, DataType>( linear, quadratic, offset, Vartype::BINARY );
1755 }
1756
1762 std::tuple<Linear<IndexType, FloatType>, Quadratic<IndexType, FloatType>, FloatType> to_ising() {
1763 // change vartype to spin
1765
1766 const Linear<IndexType, FloatType> &linear = bqm.get_linear();
1767 const Quadratic<IndexType, FloatType> &quadratic = bqm.get_quadratic();
1768 FloatType offset = bqm.get_offset();
1769 return std::make_tuple( linear, quadratic, offset );
1770 }
1771
1787
1806 return this->_quadmat;
1807 }
1808
1809 using json = nlohmann::json;
1810
1816 template<typename T = DataType>
1818 std::string schema_version = "3.0.0-dense";
1819 /*
1820 * output sample
1821 * >>> bqm = dimod.BinaryQuadraticModel({'c': -1, 'd': 1}, {('a', 'd'): 2, ('b', 'e'): 5, ('a', 'c'): 3}, 0.0,
1822 * dimod.BINARY)
1823 *
1824 * >>> bqm.to_serializable()
1825 * {'type': 'BinaryQuadraticModel', 'version': {'bqm_schema': '3.0.0-dense'}, 'use_bytes': False, 'index_type':
1826 * 'uint16', 'bias_type': 'float32', 'num_variables': 5, 'variable_labels': ['a', 'b', 'c', 'd', 'e'], 'variable_type':
1827 * 'BINARY', 'offset': 0.0, 'info': {}, 'biases': [0.0, 0.0, -1.0, 1.0, 0.0,...]}
1828 */
1829
1830 // set index_dtype
1831 std::string index_dtype = this->get_num_variables() <= 65536UL ? "uint16" : "uint32";
1832
1833 // set bias_type
1834 std::string bias_type;
1835 if ( typeid( m_offset ) == typeid( float ) ) {
1836 bias_type = "float32";
1837 } else if ( typeid( m_offset ) == typeid( double ) ) {
1838 bias_type = "float64";
1839 } else {
1840 throw std::runtime_error( "FloatType must be float or double." );
1841 }
1842
1843 // set variable type
1844 std::string variable_type;
1845 if ( m_vartype == Vartype::SPIN ) {
1846 variable_type = "SPIN";
1847 } else if ( m_vartype == Vartype::BINARY ) {
1848 variable_type = "BINARY";
1849 } else {
1850 throw std::runtime_error( "Variable type must be SPIN or BINARY." );
1851 }
1852
1853 // copy matrix to std::vector
1854 std::vector<FloatType> biases( _quadmat.data(), _quadmat.data() + _quadmat.size() );
1855
1856 json output;
1857 output[ "type" ] = "BinaryQuadraticModel";
1858 output[ "version" ] = { { "bqm_schema", schema_version } };
1859 output[ "variable_labels" ] = this->get_variables();
1860 output[ "use_bytes" ] = false;
1861 output[ "index_type" ] = index_dtype;
1862 output[ "bias_type" ] = bias_type;
1863 output[ "num_variables" ] = this->get_num_variables();
1864 output[ "variable_type" ] = variable_type;
1865 output[ "offset" ] = m_offset;
1866 output[ "info" ] = {};
1867 output[ "biases" ] = biases;
1868
1869 return output;
1870 }
1871
1877 template<typename T = DataType>
1879 std::string schema_version = "3.0.0";
1880 /*
1881 * output sample
1882 * >>> bqm = dimod.BinaryQuadraticModel({'c': -1, 'd': 1}, {('a', 'd'): 2, ('b', 'e'): 5, ('a', 'c'): 3}, 0.0,
1883 * dimod.BINARY)
1884 *
1885 * >>> bqm.to_serializable()
1886 * {'type': 'BinaryQuadraticModel', 'version': {'bqm_schema': '3.0.0'}, 'use_bytes': False, 'index_type': 'uint16',
1887 * 'bias_type': 'float32', 'num_variables': 5, 'num_interactions': 3, 'variable_labels': ['a', 'b', 'c', 'd', 'e'],
1888 * 'variable_type': 'BINARY', 'offset': 0.0, 'info': {}, 'linear_biases': [0.0, 0.0, -1.0, 1.0, 0.0],
1889 * 'quadratic_biases': [3.0, 2.0, 5.0], 'quadratic_head': [0, 0, 1], 'quadratic_tail': [2, 3, 4]}
1890 */
1891
1892 // set index_dtype
1893 std::string index_dtype = this->get_num_variables() <= 65536UL ? "uint16" : "uint32";
1894
1895 // set bias_type
1896 std::string bias_type;
1897 if ( typeid( m_offset ) == typeid( float ) ) {
1898 bias_type = "float32";
1899 } else if ( typeid( m_offset ) == typeid( double ) ) {
1900 bias_type = "float64";
1901 } else {
1902 throw std::runtime_error( "FloatType must be float or double." );
1903 }
1904
1905 // set variable type
1906 std::string variable_type;
1907 if ( m_vartype == Vartype::SPIN ) {
1908 variable_type = "SPIN";
1909 } else if ( m_vartype == Vartype::BINARY ) {
1910 variable_type = "BINARY";
1911 } else {
1912 throw std::runtime_error( "Variable type must be SPIN or BINARY." );
1913 }
1914
1915 json output;
1916 output[ "type" ] = "BinaryQuadraticModel";
1917 output[ "version" ] = { { "bqm_schema", schema_version } };
1918 output[ "variable_labels" ] = this->get_variables();
1919 output[ "use_bytes" ] = false;
1920 output[ "index_type" ] = index_dtype;
1921 output[ "bias_type" ] = bias_type;
1922 output[ "num_variables" ] = this->get_num_variables();
1923 output[ "variable_type" ] = variable_type;
1924 output[ "offset" ] = m_offset;
1925 output[ "info" ] = "";
1926
1927 // biases
1928 size_t mat_size = this->get_num_variables() + 1;
1929 Vector l_bias_vec = _quadmat.block( 0, mat_size - 1, mat_size - 1, 1 );
1930 std::vector<FloatType> l_bias( l_bias_vec.size() );
1931 for ( int i = 0; i < l_bias_vec.size(); i++ ) {
1932 l_bias[ i ] = l_bias_vec( i );
1933 }
1934
1935 std::vector<FloatType> q_bias;
1936 std::vector<size_t> q_head;
1937 std::vector<size_t> q_tail;
1938
1939 q_bias.reserve( _quadmat.nonZeros() );
1940 q_head.reserve( _quadmat.nonZeros() );
1941 q_tail.reserve( _quadmat.nonZeros() );
1942
1943 for ( int k = 0; k < _quadmat.outerSize(); k++ ) {
1944 for ( SpIter it( _quadmat, k ); it; ++it ) {
1945 size_t r = it.row();
1946 size_t c = it.col();
1947 FloatType val = it.value();
1948
1949 if ( ( r < mat_size - 1 ) && ( c < mat_size - 1 ) ) {
1950 q_bias.push_back( val );
1951 q_head.push_back( r );
1952 q_tail.push_back( c );
1953 }
1954 }
1955 }
1956
1957 output[ "linear_biases" ] = l_bias;
1958 output[ "quadratic_biases" ] = q_bias;
1959 output[ "quadratic_head" ] = q_head;
1960 output[ "quadratic_tail" ] = q_tail;
1961 output[ "num_interactions" ] = q_bias.size();
1962
1963 return output;
1964 }
1965
1974 template<typename IndexType_serial = IndexType, typename FloatType_serial = FloatType, typename T = DataType>
1977 // extract type and version
1978 std::string type = input[ "type" ];
1979 if ( type != "BinaryQuadraticModel" ) {
1980 throw std::runtime_error( "Type must be \"BinaryQuadraticModel\".\n" );
1981 }
1982 std::string version = input[ "version" ][ "bqm_schema" ];
1983 if ( version != "3.0.0-dense" ) {
1984 throw std::runtime_error( "bqm_schema must be 3.0.0-dense.\n" );
1985 }
1986
1987 // extract variable_type
1988 Vartype vartype;
1989 std::string variable_type = input[ "variable_type" ];
1990 if ( variable_type == "SPIN" ) {
1991 vartype = Vartype::SPIN;
1992 } else if ( variable_type == "BINARY" ) {
1993 vartype = Vartype::BINARY;
1994 } else {
1995 throw std::runtime_error( "variable_type must be SPIN or BINARY." );
1996 }
1997
1998 // extract biases
1999 std::vector<IndexType_serial> variables = input[ "variable_labels" ];
2000 std::vector<FloatType_serial> biases = input[ "biases" ];
2001 FloatType offset = input[ "offset" ];
2002
2003 size_t mat_size = variables.size() + 1;
2004 Eigen::Map<Matrix> mat( biases.data(), mat_size, mat_size );
2005
2007 return bqm;
2008 }
2009
2018 template<typename IndexType_serial = IndexType, typename FloatType_serial = FloatType, typename T = DataType>
2021 // extract type and version
2022 std::string type = input[ "type" ];
2023 if ( type != "BinaryQuadraticModel" ) {
2024 throw std::runtime_error( "Type must be \"BinaryQuadraticModel\".\n" );
2025 }
2026 std::string version = input[ "version" ][ "bqm_schema" ];
2027 if ( version != "3.0.0" ) {
2028 throw std::runtime_error( "bqm_schema must be 3.0.0.\n" );
2029 }
2030
2031 // extract variable_type
2032 Vartype vartype;
2033 std::string variable_type = input[ "variable_type" ];
2034 if ( variable_type == "SPIN" ) {
2035 vartype = Vartype::SPIN;
2036 } else if ( variable_type == "BINARY" ) {
2037 vartype = Vartype::BINARY;
2038 } else {
2039 throw std::runtime_error( "variable_type must be SPIN or BINARY." );
2040 }
2041
2042 // extract biases
2043 std::vector<IndexType_serial> variables = input[ "variable_labels" ];
2044 FloatType offset = input[ "offset" ];
2045
2046 std::vector<FloatType_serial> l_bias = input[ "linear_biases" ];
2047 std::vector<size_t> q_head = input[ "quadratic_head" ];
2048 std::vector<size_t> q_tail = input[ "quadratic_tail" ];
2049 std::vector<FloatType_serial> q_bias = input[ "quadratic_biases" ];
2050
2051 // make triplets
2052 std::vector<Eigen::Triplet<FloatType_serial>> triplets;
2053 triplets.reserve( q_bias.size() + l_bias.size() );
2054
2055 size_t mat_size = variables.size() + 1;
2056
2057 for ( size_t i = 0; i < l_bias.size(); i++ ) {
2058 if ( l_bias[ i ] != 0 )
2059 triplets.emplace_back( i, mat_size - 1, l_bias[ i ] );
2060 }
2061
2062 for ( size_t i = 0; i < q_bias.size(); i++ ) {
2063 triplets.emplace_back( q_head[ i ], q_tail[ i ], q_bias[ i ] );
2064 }
2065
2066 triplets.emplace_back( mat_size - 1, mat_size - 1, 1 );
2067
2069
2070 mat.setFromTriplets( triplets.begin(), triplets.end() );
2071
2073 return bqm;
2074 }
2075 };
2076} // namespace cimod
Class for dense binary quadratic model.
Definition binary_quadratic_model.hpp:148
FloatType _max_quadratic(dispatch_t< T, Sparse >=nullptr) const
calculate maximum element in quadratic term for dense graph
Definition binary_quadratic_model.hpp:409
size_t get_num_variables() const
get the number of variables
Definition binary_quadratic_model.hpp:1268
void add_variables_from(const Linear< IndexType, FloatType > &linear)
Add variables and/or linear biases to a binary quadratic model.
Definition binary_quadratic_model.hpp:1388
FloatType & _mat(IndexType label_i)
get reference of _quadmat(i,i)
Definition binary_quadratic_model.hpp:311
bool contains(const IndexType &v) const
Return true if the variable contains v.
Definition binary_quadratic_model.hpp:1288
FloatType & _quadmat_get(size_t i, size_t j, dispatch_t< T, Sparse >=nullptr)
access elements for sparse matrix
Definition binary_quadratic_model.hpp:268
static BinaryQuadraticModel< IndexType, FloatType, DataType > from_ising(const Linear< IndexType, FloatType > &linear, const Quadratic< IndexType, FloatType > &quadratic, FloatType offset=0.0)
Create a binary quadratic model from an Ising problem.
Definition binary_quadratic_model.hpp:1781
void add_interaction(const IndexType &u, const IndexType &v, const FloatType &bias)
Add an interaction and/or quadratic bias to a binary quadratic model.
Definition binary_quadratic_model.hpp:1401
static BinaryQuadraticModel< IndexType_serial, FloatType_serial, DataType > from_serializable(const json &input, dispatch_t< T, Sparse >=nullptr)
Create a BinaryQuadraticModel instance from a serializable object.
Definition binary_quadratic_model.hpp:2020
void _set_label_to_idx()
set _label_to_idx from _idx_to_label
Definition binary_quadratic_model.hpp:218
void fix_variables(const std::vector< std::pair< IndexType, int32_t > > &fixed)
Fix the value of the variables and remove it from a binary quadratic model.
Definition binary_quadratic_model.hpp:1586
BinaryQuadraticModel< IndexType, FloatType, DataType > change_vartype(const Vartype &vartype, bool inplace)
Create a binary quadratic model with the specified vartype.
Definition binary_quadratic_model.hpp:1668
void _binary_to_spin(dispatch_t< T, Dense >=nullptr)
change internal variable from QUBO to Ising ones for dense matrix The following conversion is applied...
Definition binary_quadratic_model.hpp:1056
Quadratic< IndexType, FloatType > _generate_quadratic(dispatch_t< T, Sparse >=nullptr) const
Definition binary_quadratic_model.hpp:879
std::vector< IndexType > _idx_to_label
vector for converting index to label the list is asssumed to be sorted
Definition binary_quadratic_model.hpp:196
FloatType _quadmat_get(size_t i, size_t j, dispatch_t< T, Dense >=nullptr) const
access elements for dense matrix
Definition binary_quadratic_model.hpp:253
FloatType _min_quadratic(dispatch_t< T, Sparse >=nullptr) const
calculate minimum element in quadratic term for dense graph
Definition binary_quadratic_model.hpp:435
void _initialize_quadmat(const Linear< IndexType, FloatType > &linear, const Quadratic< IndexType, FloatType > &quadratic, dispatch_t< T, Dense >=nullptr)
initialize matrix with linear and quadratic dicts (for dense matrix)
Definition binary_quadratic_model.hpp:620
void normalize(const std::pair< FloatType, FloatType > &bias_range={ 1.0, 1.0 }, const bool use_quadratic_range=false, const std::pair< FloatType, FloatType > &quadratic_range={ 1.0, 1.0 }, const std::vector< IndexType > &ignored_variables={}, const std::vector< std::pair< IndexType, IndexType > > &ignored_interactions={}, const bool ignored_offset=false)
Normalizes the biases of the binary quadratic model such that they fall in the provided range(s),...
Definition binary_quadratic_model.hpp:1525
static BinaryQuadraticModel< IndexType_serial, FloatType_serial, DataType > from_serializable(const json &input, dispatch_t< T, Dense >=nullptr)
Create a BinaryQuadraticModel instance from a serializable object.
Definition binary_quadratic_model.hpp:1976
void _spin_to_binary(dispatch_t< T, Dense >=nullptr)
change internal variable from Ising to QUBO ones for dense matrix The following conversion is applied...
Definition binary_quadratic_model.hpp:937
void _delete_label_from_mat(IndexType label_i, dispatch_t< T, Sparse >=nullptr)
delete row and column that corresponds to existing label from _quadmat for sparse matrix
Definition binary_quadratic_model.hpp:529
FloatType _min_quadratic(dispatch_t< T, Dense >=nullptr) const
calculate minimum element in quadratic term for dense graph
Definition binary_quadratic_model.hpp:385
FloatType _min_linear(dispatch_t< T, Dense >=nullptr) const
calculate minimum element in linear term for dense graph
Definition binary_quadratic_model.hpp:374
void remove_variables_from(const std::vector< IndexType > &variables)
Remove specified variables and all of their interactions from a binary quadratic model.
Definition binary_quadratic_model.hpp:1433
void _initialize_quadmat(const DenseMatrix &mat, const std::vector< IndexType > &labels_vec, bool fix_format)
initialize matrix with matrix and labels the form of matrix is assumed to be the following two forms:
Definition binary_quadratic_model.hpp:834
Eigen::Matrix< FloatType, Eigen::Dynamic, Eigen::Dynamic, Eigen::RowMajor > DenseMatrix
Eigen Matrix if DataType is Dense , Matrix is equal to Eigen::Matrix if DataType is Sparse,...
Definition binary_quadratic_model.hpp:167
FloatType _mat(IndexType label_i, IndexType label_j) const
get reference of _quadmat(i,j)
Definition binary_quadratic_model.hpp:324
Matrix interaction_matrix() const
generate (Dense or Sparse) interaction matrix with given list of indices The generated matrix will be...
Definition binary_quadratic_model.hpp:1805
FloatType & _mat(IndexType label_i, IndexType label_j)
get reference of _quadmat(i,j)
Definition binary_quadratic_model.hpp:295
FloatType _min_linear(dispatch_t< T, Sparse >=nullptr) const
calculate minimum element in linear term for dense graph
Definition binary_quadratic_model.hpp:422
void _binary_to_spin(dispatch_t< T, Sparse >=nullptr)
change internal variable from QUBO to Ising ones for sparse matrix The following conversion is applie...
Definition binary_quadratic_model.hpp:1094
void _spin_to_binary(dispatch_t< T, Sparse >=nullptr)
change internal variable from Ising to QUBO ones for sparse matrix The following conversion is applie...
Definition binary_quadratic_model.hpp:976
nlohmann::json json
Definition binary_quadratic_model.hpp:1809
Vartype get_vartype() const
Get the vartype object.
Definition binary_quadratic_model.hpp:1346
std::unordered_map< IndexType, size_t > _label_to_idx
dict for converting label to index
Definition binary_quadratic_model.hpp:201
std::conditional_t< std::is_same_v< DataType, Dense >, DenseMatrix, SparseMatrix > Matrix
Definition binary_quadratic_model.hpp:171
FloatType _max_linear(dispatch_t< T, Dense >=nullptr) const
calculate maximum element in linear term for dense graph
Definition binary_quadratic_model.hpp:352
size_t length() const
Return the number of variables.
Definition binary_quadratic_model.hpp:1278
void _delete_label(IndexType label_i, bool force_delete=true)
delete label if label_i does not exist, this process is skipped.
Definition binary_quadratic_model.hpp:591
json to_serializable(dispatch_t< T, Dense >=nullptr) const
Convert the binary quadratic model to a dense-version serializable object.
Definition binary_quadratic_model.hpp:1817
const std::vector< IndexType > & get_variables() const
Get variables.
Definition binary_quadratic_model.hpp:1355
FloatType m_offset
The energy offset associated with the model.
Definition binary_quadratic_model.hpp:207
FloatType _mat(IndexType label_i) const
get reference of _quadmat(i,i)
Definition binary_quadratic_model.hpp:341
void remove_interaction(const IndexType &u, const IndexType &v)
Remove interaction of variables u, v from a binary quadratic model.
Definition binary_quadratic_model.hpp:1445
void scale(const FloatType &scalar, const std::vector< IndexType > &ignored_variables={}, const std::vector< std::pair< IndexType, IndexType > > &ignored_interactions={}, const bool ignored_offset=false)
Multiply by the specified scalar all the biases and offset of a binary quadratic model.
Definition binary_quadratic_model.hpp:1486
Eigen::Matrix< FloatType, Eigen::Dynamic, 1 > Vector
Definition binary_quadratic_model.hpp:173
BinaryQuadraticModel(const BinaryQuadraticModel &)=default
BinaryQuadraticModel(const Eigen::Ref< const DenseMatrix > &mat, const std::vector< IndexType > &labels_vec, const FloatType &offset, const Vartype vartype, bool fix_format=true)
BinaryQuadraticModel constructor (with matrix);.
Definition binary_quadratic_model.hpp:1201
std::vector< FloatType > energies(const std::vector< Sample< IndexType > > &samples_like) const
Determine the energies of the given samples.
Definition binary_quadratic_model.hpp:1704
static BinaryQuadraticModel< IndexType, FloatType, DataType > from_qubo(const Quadratic< IndexType, FloatType > &Q, FloatType offset=0.0)
Create a binary quadratic model from a QUBO model.
Definition binary_quadratic_model.hpp:1740
Quadratic< IndexType, FloatType > _generate_quadratic(dispatch_t< T, Dense >=nullptr) const
Definition binary_quadratic_model.hpp:865
FloatType _max_quadratic(dispatch_t< T, Dense >=nullptr) const
calculate maximum element in quadratic term for dense graph
Definition binary_quadratic_model.hpp:363
Eigen::SparseMatrix< FloatType, Eigen::RowMajor > SparseMatrix
Definition binary_quadratic_model.hpp:168
std::enable_if_t< std::is_same_v< T, U >, std::nullptr_t > dispatch_t
template type for dispatch used for SFINAE
Definition binary_quadratic_model.hpp:158
BinaryQuadraticModel(const SparseMatrix &mat, const std::vector< IndexType > &labels_vec, const Vartype vartype)
BinaryQuadraticModel constructor (with sparse matrix); this constructor is for developers.
Definition binary_quadratic_model.hpp:1257
void _insert_label_into_mat(IndexType label_i, dispatch_t< T, Dense >=nullptr)
insert row and column that corresponds to added label into _quadmat for dense matrix
Definition binary_quadratic_model.hpp:448
BinaryQuadraticModel(const Eigen::Ref< const DenseMatrix > &mat, const std::vector< IndexType > &labels_vec, const Vartype vartype, bool fix_format=true)
BinaryQuadraticModel constructor (with matrix);.
Definition binary_quadratic_model.hpp:1220
void add_offset(const FloatType &offset)
Add specified value to the offset of a binary quadratic model.
Definition binary_quadratic_model.hpp:1467
BinaryQuadraticModel(const SparseMatrix &mat, const std::vector< IndexType > &labels_vec, const FloatType &offset, const Vartype vartype)
BinaryQuadraticModel constructor (with sparse matrix); this constructor is for developers.
Definition binary_quadratic_model.hpp:1238
FloatType get_linear(IndexType label_i) const
Get the element of linear object.
Definition binary_quadratic_model.hpp:1301
void add_variable(const IndexType &v, const FloatType &bias)
Add variable v and/or its bias to a binary quadratic model.
Definition binary_quadratic_model.hpp:1377
Matrix _quadmat
quadratic dense-type matrix The stored matrix has the following triangular form:
Definition binary_quadratic_model.hpp:190
std::tuple< Linear< IndexType, FloatType >, Quadratic< IndexType, FloatType >, FloatType > to_ising()
Convert a binary quadratic model to Ising format.
Definition binary_quadratic_model.hpp:1762
FloatType _quadmat_get(size_t i, size_t j, dispatch_t< T, Sparse >=nullptr) const
access elements for sparse matrix
Definition binary_quadratic_model.hpp:283
void _initialize_quadmat(const Linear< IndexType, FloatType > &linear, const Quadratic< IndexType, FloatType > &quadratic, dispatch_t< T, Sparse >=nullptr)
initialize matrix with linear and quadratic dicts (for sparse matrix)
Definition binary_quadratic_model.hpp:668
json to_serializable(dispatch_t< T, Sparse >=nullptr) const
Convert the binary quadratic model to a serializable object.
Definition binary_quadratic_model.hpp:1878
FloatType get_offset() const
Get the offset.
Definition binary_quadratic_model.hpp:1337
void _delete_label_from_mat(IndexType label_i, dispatch_t< T, Dense >=nullptr)
delete row and column that corresponds to existing label from _quadmat for dense matrix
Definition binary_quadratic_model.hpp:509
BinaryQuadraticModel< IndexType, FloatType, DataType > empty(Vartype vartype)
Create an empty BinaryQuadraticModel.
Definition binary_quadratic_model.hpp:1364
void _insert_label_into_mat(IndexType label_i, dispatch_t< T, Sparse >=nullptr)
insert row and column that corresponds to added label into _quadmat for sparse matrix
Definition binary_quadratic_model.hpp:468
typename SparseMatrix::InnerIterator SpIter
Definition binary_quadratic_model.hpp:169
FloatType _max_linear(dispatch_t< T, Sparse >=nullptr) const
calculate maximum element in linear term for dense graph
Definition binary_quadratic_model.hpp:396
BinaryQuadraticModel(const Linear< IndexType, FloatType > &linear, const Quadratic< IndexType, FloatType > &quadratic, const Vartype vartype)
BinaryQuadraticModel constructor.
Definition binary_quadratic_model.hpp:1185
Vartype m_vartype
The model's type.
Definition binary_quadratic_model.hpp:213
Quadratic< IndexType, FloatType > get_quadratic() const
Get uadratic object.
Definition binary_quadratic_model.hpp:1328
Linear< IndexType, FloatType > _generate_linear() const
Definition binary_quadratic_model.hpp:853
void remove_offset()
Set the binary quadratic model's offset to zero.
Definition binary_quadratic_model.hpp:1474
std::tuple< Quadratic< IndexType, FloatType >, FloatType > to_qubo()
Convert a binary quadratic model to QUBO format.
Definition binary_quadratic_model.hpp:1718
void _add_new_label(IndexType label_i)
add new label if label_i already exists, this process is skipped.
Definition binary_quadratic_model.hpp:572
void remove_variable(const IndexType &v)
Remove variable v and all its interactions from a binary quadratic model.
Definition binary_quadratic_model.hpp:1424
void _initialize_quadmat(const SparseMatrix &mat, const std::vector< IndexType > &labels_vec)
initialize matrix with matrix and labels the form of matrix is assumed to be the following form:
Definition binary_quadratic_model.hpp:914
void fix_variable(const IndexType &v, const int32_t &value)
Fix the value of a variable and remove it from a binary quadratic model.
Definition binary_quadratic_model.hpp:1564
void flip_variable(const IndexType &v)
Flip variable v in a binary quadratic model.
Definition binary_quadratic_model.hpp:1597
FloatType energy(const Sample< IndexType > &sample) const
Determine the energy of the specified sample of a binary quadratic model.
Definition binary_quadratic_model.hpp:1686
Linear< IndexType, FloatType > get_linear() const
Get linear object.
Definition binary_quadratic_model.hpp:1310
void _add_triangular_elements(const DenseMatrix &mat, bool fix_format, dispatch_t< T, Sparse >=nullptr)
add non-diagonal elements to upper triangular components for sparse matrix
Definition binary_quadratic_model.hpp:760
void add_interactions_from(const Quadratic< IndexType, FloatType > &quadratic)
Add interactions and/or quadratic biases to a binary quadratic model.
Definition binary_quadratic_model.hpp:1413
void change_vartype(const Vartype &vartype)
‍**
Definition binary_quadratic_model.hpp:1649
BinaryQuadraticModel(const Linear< IndexType, FloatType > &linear, const Quadratic< IndexType, FloatType > &quadratic, const FloatType &offset, const Vartype vartype)
BinaryQuadraticModel constructor.
Definition binary_quadratic_model.hpp:1167
void remove_interactions_from(const std::vector< std::pair< IndexType, IndexType > > &interactions)
Remove all specified interactions from the binary quadratic model.
Definition binary_quadratic_model.hpp:1456
FloatType & _quadmat_get(size_t i, size_t j, dispatch_t< T, Dense >=nullptr)
access elements for dense matrix
Definition binary_quadratic_model.hpp:238
void _add_triangular_elements(const DenseMatrix &mat, bool fix_format, dispatch_t< T, Dense >=nullptr)
add non-diagonal elements to upper triangular components for dense matrix
Definition binary_quadratic_model.hpp:729
FloatType get_quadratic(IndexType label_i, IndexType label_j) const
Get the element of quadratic object.
Definition binary_quadratic_model.hpp:1319
void declare_BQM(py::module &m, const std::string &name)
Definition main.hpp:41
Definition binary_polynomial_model.hpp:139
std::unordered_map< IndexType, std::unordered_map< IndexType, FloatType > > Adjacency
Type alias for adjacency list.
Definition binary_quadratic_model.hpp:127
std::unordered_map< IndexType, int32_t > Sample
Type alias for sample, which represents the spin or binary configurations.
Definition binary_polynomial_model.hpp:162
std::unordered_map< IndexType, FloatType > Linear
Type alias for linear bias.
Definition binary_quadratic_model.hpp:111
std::unordered_map< std::pair< IndexType, IndexType >, FloatType, pair_hash > Quadratic
Type alias for quadratic bias.
Definition binary_quadratic_model.hpp:119
Vartype
Enum class for representing problem type.
Definition vartypes.hpp:24
Definition binary_quadratic_model.hpp:137
Definition binary_quadratic_model.hpp:138
Hash function for std::unordered_map.
Definition hash.hpp:65