@testset "Graph coloring" begin

@testset "49 US states + DC" begin
    com = CS.init()

    num_colors = 8
    washington = add_var!(com, 1, num_colors)
    montana = add_var!(com, 1, num_colors)
    maine = add_var!(com, 1, num_colors)
    north_dakota = add_var!(com, 1, num_colors)
    south_dakota = add_var!(com, 1, num_colors)
    wyoming = add_var!(com, 1, num_colors)
    wisconsin = add_var!(com, 1, num_colors)
    idaho = add_var!(com, 1, num_colors)
    vermont = add_var!(com, 1, num_colors)
    minnesota = add_var!(com, 1, num_colors)
    oregon = add_var!(com, 1, num_colors)
    new_hampshire = add_var!(com, 1, num_colors)
    iowa = add_var!(com, 1, num_colors)
    massachusetts = add_var!(com, 1, num_colors)
    nebraska = add_var!(com, 1, num_colors)
    new_york = add_var!(com, 1, num_colors)
    pennsylvania = add_var!(com, 1, num_colors)
    connecticut = add_var!(com, 1, num_colors)
    rhode_island = add_var!(com, 1, num_colors)
    new_jersey = add_var!(com, 1, num_colors)
    indiana = add_var!(com, 1, num_colors)
    nevada = add_var!(com, 1, num_colors)
    utah = add_var!(com, 1, num_colors)
    california = add_var!(com, 1, num_colors)
    ohio = add_var!(com, 1, num_colors)
    illinois = add_var!(com, 1, num_colors)
    washington_dc = add_var!(com, 1, num_colors)
    delaware = add_var!(com, 1, num_colors)
    west_virginia = add_var!(com, 1, num_colors)
    maryland = add_var!(com, 1, num_colors)
    colorado = add_var!(com, 1, num_colors)
    kentucky = add_var!(com, 1, num_colors)
    kansas = add_var!(com, 1, num_colors)
    virginia = add_var!(com, 1, num_colors)
    missouri = add_var!(com, 1, num_colors)
    arizona = add_var!(com, 1, num_colors)
    oklahoma = add_var!(com, 1, num_colors)
    north_carolina = add_var!(com, 1, num_colors)
    tennessee = add_var!(com, 1, num_colors)
    texas = add_var!(com, 1, num_colors)
    new_mexico = add_var!(com, 1, num_colors)
    alabama = add_var!(com, 1, num_colors)
    mississippi = add_var!(com, 1, num_colors)
    georgia = add_var!(com, 1, num_colors)
    south_carolina = add_var!(com, 1, num_colors)
    arkansas = add_var!(com, 1, num_colors)
    louisiana = add_var!(com, 1, num_colors)
    florida = add_var!(com, 1, num_colors)
    michigan = add_var!(com, 1, num_colors)

    states = [washington,montana,maine,north_dakota,south_dakota,wyoming,wisconsin,idaho,vermont,minnesota,oregon,new_hampshire,
    iowa,massachusetts,nebraska,new_york,pennsylvania,connecticut,rhode_island,new_jersey,indiana,nevada,utah,california,ohio,
    illinois,washington_dc,delaware,west_virginia,maryland,colorado,kentucky,kansas,virginia,missouri,arizona,oklahoma,north_carolina,
    tennessee,texas,new_mexico,alabama,mississippi,georgia,south_carolina,arkansas,louisiana,florida,michigan]

    add_constraint!(com, washington != oregon)
    add_constraint!(com, washington != idaho)
    add_constraint!(com, oregon != idaho)
    add_constraint!(com, oregon != nevada)
    add_constraint!(com, oregon != california)
    add_constraint!(com, california != nevada)
    add_constraint!(com, california != arizona)
    add_constraint!(com, nevada != idaho)
    add_constraint!(com, nevada != utah)
    add_constraint!(com, nevada != arizona)
    add_constraint!(com, idaho != montana)
    add_constraint!(com, idaho != wyoming)
    add_constraint!(com, idaho != utah)
    add_constraint!(com, utah != wyoming)
    add_constraint!(com, utah != colorado)
    add_constraint!(com, utah != new_mexico)
    add_constraint!(com, utah != arizona)
    add_constraint!(com, arizona != colorado)
    add_constraint!(com, arizona != new_mexico)
    add_constraint!(com, montana != north_dakota)
    add_constraint!(com, montana != south_dakota)
    add_constraint!(com, montana != wyoming)
    add_constraint!(com, wyoming != south_dakota)
    add_constraint!(com, wyoming != nebraska)
    add_constraint!(com, wyoming != colorado)
    add_constraint!(com, colorado != nebraska)
    add_constraint!(com, colorado != kansas)
    add_constraint!(com, colorado != oklahoma)
    add_constraint!(com, colorado != new_mexico)
    add_constraint!(com, new_mexico != oklahoma)
    add_constraint!(com, new_mexico != texas)
    add_constraint!(com, north_dakota != minnesota)
    add_constraint!(com, north_dakota != south_dakota)
    add_constraint!(com, south_dakota != minnesota)
    add_constraint!(com, south_dakota != iowa)
    add_constraint!(com, south_dakota != nebraska)
    add_constraint!(com, nebraska != iowa)
    add_constraint!(com, nebraska != missouri)
    add_constraint!(com, nebraska != kansas)
    add_constraint!(com, kansas != missouri)
    add_constraint!(com, kansas != oklahoma)
    add_constraint!(com, oklahoma != arkansas)
    add_constraint!(com, oklahoma != texas)
    add_constraint!(com, texas != arkansas)
    add_constraint!(com, texas != louisiana)
    add_constraint!(com, minnesota != wisconsin)
    add_constraint!(com, minnesota != iowa)
    add_constraint!(com, iowa != wisconsin)
    add_constraint!(com, iowa != illinois)
    add_constraint!(com, iowa != missouri)
    add_constraint!(com, missouri != illinois)
    add_constraint!(com, missouri != kentucky)
    add_constraint!(com, missouri != tennessee)
    add_constraint!(com, missouri != arkansas)
    add_constraint!(com, arkansas != tennessee)
    add_constraint!(com, arkansas != mississippi)
    add_constraint!(com, arkansas != louisiana)
    add_constraint!(com, louisiana != mississippi)
    add_constraint!(com, wisconsin != illinois)
    add_constraint!(com, wisconsin != michigan)
    add_constraint!(com, illinois != indiana)
    add_constraint!(com, illinois != kentucky)
    add_constraint!(com, kentucky != indiana)
    add_constraint!(com, kentucky != ohio)
    add_constraint!(com, kentucky != west_virginia)
    add_constraint!(com, kentucky != virginia)
    add_constraint!(com, kentucky != tennessee)
    add_constraint!(com, tennessee != virginia)
    add_constraint!(com, tennessee != north_carolina)
    add_constraint!(com, tennessee != georgia)
    add_constraint!(com, tennessee != alabama)
    add_constraint!(com, tennessee != mississippi)
    add_constraint!(com, mississippi != alabama)
    add_constraint!(com, michigan != indiana)
    add_constraint!(com, michigan != ohio)
    add_constraint!(com, indiana != ohio)
    add_constraint!(com, alabama != georgia)
    add_constraint!(com, alabama != florida)
    add_constraint!(com, ohio != pennsylvania)
    add_constraint!(com, ohio != west_virginia)
    add_constraint!(com, maine != new_hampshire)
    add_constraint!(com, new_hampshire != vermont)
    add_constraint!(com, new_hampshire != massachusetts)
    add_constraint!(com, vermont != massachusetts)
    add_constraint!(com, vermont != new_york)
    add_constraint!(com, massachusetts != new_york)
    add_constraint!(com, massachusetts != rhode_island)
    add_constraint!(com, massachusetts != connecticut)
    add_constraint!(com, connecticut != rhode_island)
    add_constraint!(com, new_york != connecticut)
    add_constraint!(com, new_york != pennsylvania)
    add_constraint!(com, new_york != new_jersey)
    add_constraint!(com, pennsylvania != new_jersey)
    add_constraint!(com, pennsylvania != delaware)
    add_constraint!(com, pennsylvania != maryland)
    add_constraint!(com, pennsylvania != west_virginia)
    add_constraint!(com, new_jersey != delaware)
    add_constraint!(com, maryland != washington_dc)
    add_constraint!(com, maryland != west_virginia)
    add_constraint!(com, maryland != virginia)
    add_constraint!(com, washington_dc != virginia)
    add_constraint!(com, west_virginia != virginia)
    add_constraint!(com, virginia != north_carolina)
    add_constraint!(com, north_carolina != south_carolina)
    add_constraint!(com, south_carolina != georgia)
    add_constraint!(com, georgia != florida)

    # :should be :Min or :Max
    @test_throws ErrorException set_objective!(com, :Minimize, CS.vars_max(states))

    set_objective!(com, :Min, CS.vars_max(states))

    status = solve!(com; keep_logs=true)
    CS.save_logs(com, "graph_color_optimize.json")
    rm("graph_color_optimize.json")

    @test status == :Solved
    @test com.best_sol == 4
    @test all([CS.isfixed(var) for var in states])
    @test maximum([value(var) for var in states]) == 4

end

@testset "49 US states + DC only 3 colors" begin
    com = CS.init()

    num_colors = 3
    washington = add_var!(com, 1, num_colors)
    montana = add_var!(com, 1, num_colors)
    maine = add_var!(com, 1, num_colors)
    north_dakota = add_var!(com, 1, num_colors)
    south_dakota = add_var!(com, 1, num_colors)
    wyoming = add_var!(com, 1, num_colors)
    wisconsin = add_var!(com, 1, num_colors)
    idaho = add_var!(com, 1, num_colors)
    vermont = add_var!(com, 1, num_colors)
    minnesota = add_var!(com, 1, num_colors)
    oregon = add_var!(com, 1, num_colors)
    new_hampshire = add_var!(com, 1, num_colors)
    iowa = add_var!(com, 1, num_colors)
    massachusetts = add_var!(com, 1, num_colors)
    nebraska = add_var!(com, 1, num_colors)
    new_york = add_var!(com, 1, num_colors)
    pennsylvania = add_var!(com, 1, num_colors)
    connecticut = add_var!(com, 1, num_colors)
    rhode_island = add_var!(com, 1, num_colors)
    new_jersey = add_var!(com, 1, num_colors)
    indiana = add_var!(com, 1, num_colors)
    nevada = add_var!(com, 1, num_colors)
    utah = add_var!(com, 1, num_colors)
    california = add_var!(com, 1, num_colors)
    ohio = add_var!(com, 1, num_colors)
    illinois = add_var!(com, 1, num_colors)
    washington_dc = add_var!(com, 1, num_colors)
    delaware = add_var!(com, 1, num_colors)
    west_virginia = add_var!(com, 1, num_colors)
    maryland = add_var!(com, 1, num_colors)
    colorado = add_var!(com, 1, num_colors)
    kentucky = add_var!(com, 1, num_colors)
    kansas = add_var!(com, 1, num_colors)
    virginia = add_var!(com, 1, num_colors)
    missouri = add_var!(com, 1, num_colors)
    arizona = add_var!(com, 1, num_colors)
    oklahoma = add_var!(com, 1, num_colors)
    north_carolina = add_var!(com, 1, num_colors)
    tennessee = add_var!(com, 1, num_colors)
    texas = add_var!(com, 1, num_colors)
    new_mexico = add_var!(com, 1, num_colors)
    alabama = add_var!(com, 1, num_colors)
    mississippi = add_var!(com, 1, num_colors)
    georgia = add_var!(com, 1, num_colors)
    south_carolina = add_var!(com, 1, num_colors)
    arkansas = add_var!(com, 1, num_colors)
    louisiana = add_var!(com, 1, num_colors)
    florida = add_var!(com, 1, num_colors)
    michigan = add_var!(com, 1, num_colors)

    states = [washington,montana,maine,north_dakota,south_dakota,wyoming,wisconsin,idaho,vermont,minnesota,oregon,new_hampshire,
    iowa,massachusetts,nebraska,new_york,pennsylvania,connecticut,rhode_island,new_jersey,indiana,nevada,utah,california,ohio,
    illinois,washington_dc,delaware,west_virginia,maryland,colorado,kentucky,kansas,virginia,missouri,arizona,oklahoma,north_carolina,
    tennessee,texas,new_mexico,alabama,mississippi,georgia,south_carolina,arkansas,louisiana,florida,michigan]

    add_constraint!(com, washington != oregon)
    add_constraint!(com, washington != idaho)
    add_constraint!(com, oregon != idaho)
    add_constraint!(com, oregon != nevada)
    add_constraint!(com, oregon != california)
    add_constraint!(com, california != nevada)
    add_constraint!(com, california != arizona)
    add_constraint!(com, nevada != idaho)
    add_constraint!(com, nevada != utah)
    add_constraint!(com, nevada != arizona)
    add_constraint!(com, idaho != montana)
    add_constraint!(com, idaho != wyoming)
    add_constraint!(com, idaho != utah)
    add_constraint!(com, utah != wyoming)
    add_constraint!(com, utah != colorado)
    add_constraint!(com, utah != new_mexico)
    add_constraint!(com, utah != arizona)
    add_constraint!(com, arizona != colorado)
    add_constraint!(com, arizona != new_mexico)
    add_constraint!(com, montana != north_dakota)
    add_constraint!(com, montana != south_dakota)
    add_constraint!(com, montana != wyoming)
    add_constraint!(com, wyoming != south_dakota)
    add_constraint!(com, wyoming != nebraska)
    add_constraint!(com, wyoming != colorado)
    add_constraint!(com, colorado != nebraska)
    add_constraint!(com, colorado != kansas)
    add_constraint!(com, colorado != oklahoma)
    add_constraint!(com, colorado != new_mexico)
    add_constraint!(com, new_mexico != oklahoma)
    add_constraint!(com, new_mexico != texas)
    add_constraint!(com, north_dakota != minnesota)
    add_constraint!(com, north_dakota != south_dakota)
    add_constraint!(com, south_dakota != minnesota)
    add_constraint!(com, south_dakota != iowa)
    add_constraint!(com, south_dakota != nebraska)
    add_constraint!(com, nebraska != iowa)
    add_constraint!(com, nebraska != missouri)
    add_constraint!(com, nebraska != kansas)
    add_constraint!(com, kansas != missouri)
    add_constraint!(com, kansas != oklahoma)
    add_constraint!(com, oklahoma != arkansas)
    add_constraint!(com, oklahoma != texas)
    add_constraint!(com, texas != arkansas)
    add_constraint!(com, texas != louisiana)
    add_constraint!(com, minnesota != wisconsin)
    add_constraint!(com, minnesota != iowa)
    add_constraint!(com, iowa != wisconsin)
    add_constraint!(com, iowa != illinois)
    add_constraint!(com, iowa != missouri)
    add_constraint!(com, missouri != illinois)
    add_constraint!(com, missouri != kentucky)
    add_constraint!(com, missouri != tennessee)
    add_constraint!(com, missouri != arkansas)
    add_constraint!(com, arkansas != tennessee)
    add_constraint!(com, arkansas != mississippi)
    add_constraint!(com, arkansas != louisiana)
    add_constraint!(com, louisiana != mississippi)
    add_constraint!(com, wisconsin != illinois)
    add_constraint!(com, wisconsin != michigan)
    add_constraint!(com, illinois != indiana)
    add_constraint!(com, illinois != kentucky)
    add_constraint!(com, kentucky != indiana)
    add_constraint!(com, kentucky != ohio)
    add_constraint!(com, kentucky != west_virginia)
    add_constraint!(com, kentucky != virginia)
    add_constraint!(com, kentucky != tennessee)
    add_constraint!(com, tennessee != virginia)
    add_constraint!(com, tennessee != north_carolina)
    add_constraint!(com, tennessee != georgia)
    add_constraint!(com, tennessee != alabama)
    add_constraint!(com, tennessee != mississippi)
    add_constraint!(com, mississippi != alabama)
    add_constraint!(com, michigan != indiana)
    add_constraint!(com, michigan != ohio)
    add_constraint!(com, indiana != ohio)
    add_constraint!(com, alabama != georgia)
    add_constraint!(com, alabama != florida)
    add_constraint!(com, ohio != pennsylvania)
    add_constraint!(com, ohio != west_virginia)
    add_constraint!(com, maine != new_hampshire)
    add_constraint!(com, new_hampshire != vermont)
    add_constraint!(com, new_hampshire != massachusetts)
    add_constraint!(com, vermont != massachusetts)
    add_constraint!(com, vermont != new_york)
    add_constraint!(com, massachusetts != new_york)
    add_constraint!(com, massachusetts != rhode_island)
    add_constraint!(com, massachusetts != connecticut)
    add_constraint!(com, connecticut != rhode_island)
    add_constraint!(com, new_york != connecticut)
    add_constraint!(com, new_york != pennsylvania)
    add_constraint!(com, new_york != new_jersey)
    add_constraint!(com, pennsylvania != new_jersey)
    add_constraint!(com, pennsylvania != delaware)
    add_constraint!(com, pennsylvania != maryland)
    add_constraint!(com, pennsylvania != west_virginia)
    add_constraint!(com, new_jersey != delaware)
    add_constraint!(com, maryland != washington_dc)
    add_constraint!(com, maryland != west_virginia)
    add_constraint!(com, maryland != virginia)
    add_constraint!(com, washington_dc != virginia)
    add_constraint!(com, west_virginia != virginia)
    add_constraint!(com, virginia != north_carolina)
    add_constraint!(com, north_carolina != south_carolina)
    add_constraint!(com, south_carolina != georgia)
    add_constraint!(com, georgia != florida)

    set_objective!(com, :Min, CS.vars_max(states))

    status = solve!(com)

    @test status == :Infeasible
end

end