Scippy

SCIP

Solving Constraint Integer Programs

queens.cpp
Go to the documentation of this file.
1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the examples to */
4 /* An introduction to SCIP */
5 /* */
6 /* Copyright (C) 2007 Cornelius Schwarz */
7 /* */
8 /* 2007 University of Bayreuth */
9 /* */
10 /* */
11 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
12 
13 /**
14  * @file queens.cpp
15  * @author Cornelius Schwarz
16  * @brief n-queens examlple implementation
17  */
18 
19 #include "queens.hpp"
20 #include <sstream>
21 #include "scip_exception.hpp"
22 #include "scip/pub_message.h"
23 
24 using namespace std;
25 using namespace scipexamples;
26 
27 /* constructor */
29  : _scip(0), _n(n), _vars(n, vector<SCIP_VAR *>(n)), _cons()
30 {
31  // initialize scip
32  SCIP_CALL_EXC( SCIPcreate(& _scip) );
33 
34  // load default plugins linke separators, heuristics, etc.
36 
37  // disable scip output to stdout
39 
40  // create an empty problem
41  SCIP_CALL_EXC( SCIPcreateProb(_scip, "queens", NULL, NULL, NULL, NULL, NULL, NULL, NULL) );
42 
43  // set the objective sense to maximize, default is minimize
45 
46  // create a binary variable for every field (i,j) on the chess board
47  ostringstream namebuf;
48  for( size_t i = 0; i < _n; ++i )
49  {
50  for( size_t j = 0; j < _n; ++j )
51  {
52  SCIP_VAR* var;
53  namebuf.str("");
54  namebuf << "x#" << i << "#" << j;
55 
56  // create the SCIP_VAR object
57  SCIP_CALL_EXC( SCIPcreateVar(_scip, & var, namebuf.str().c_str(), 0.0, 1.0, 1.0, SCIP_VARTYPE_BINARY, TRUE, FALSE, NULL, NULL, NULL, NULL, NULL) );
58 
59  // add the SCIP_VAR object to the scip problem
60  SCIP_CALL_EXC( SCIPaddVar(_scip, var) );
61 
62  // storing the SCIP_VAR pointer for later access
63  _vars[i][j] = var;
64  }
65  }
66 
67  // create constraints
68  // one queen per row
69  for( size_t i = 0; i < _n; ++i )
70  {
71  SCIP_CONS * cons;
72  namebuf.str("");
73  namebuf<<"row_"<<i;
74 
75  // create SCIP_CONS object
76  // this is an equality since there must be a queen in every row
77  SCIP_CALL_EXC( SCIPcreateConsLinear(_scip, & cons, namebuf.str().c_str(), 0, NULL, NULL, 1.0, 1.0,
79 
80  // add the vars belonging to field in this row to the constraint
81  for( size_t j = 0; j < _n; ++j )
82  SCIP_CALL_EXC( SCIPaddCoefLinear(_scip, cons, _vars[i][j], 1.0) );
83 
84  // add the constraint to scip
85  SCIP_CALL_EXC( SCIPaddCons(_scip, cons) );
86 
87  // store the constraint for later on
88  _cons.push_back(cons);
89  }
90 
91  // this is the same with the col constraints ( one queen per column)
92  for( size_t j = 0; j < _n; ++j )
93  {
94  SCIP_CONS * cons;
95  namebuf.str("");
96  namebuf << "col_" << j;
97  SCIP_CALL_EXC( SCIPcreateConsLinear(_scip, & cons, namebuf.str().c_str(), 0, NULL, NULL, 1.0, 1.0,
99 
100  for( size_t i = 0; i < _n; ++i )
101  SCIP_CALL_EXC( SCIPaddCoefLinear(_scip, cons, _vars[i][j], 1.0) );
102 
103  SCIP_CALL_EXC( SCIPaddCons(_scip, cons) );
104  _cons.push_back(cons);
105  }
106 
107  // now we create the constraints for the diagonals
108  // there is only one queen allowed in each diagonal, but there do not need to be one. Therefore we add a <= 1 constraint
109  // in this problem case we can set the lhs to zero instead of -SCIPinfinity
110  // diag col down
111  for( size_t j = 0; j < _n; ++j )
112  {
113  SCIP_CONS * cons;
114  namebuf.str("");
115  namebuf << "diag_col_down_" << j;
116  SCIP_CALL_EXC(SCIPcreateConsLinear(_scip, & cons, namebuf.str().c_str(), 0, NULL, NULL, 0.0, 1.0,
118 
119  for( size_t i = 0; i < _n - j; ++i )
120  SCIP_CALL_EXC( SCIPaddCoefLinear(_scip, cons, _vars[i][j+i], 1.0) );
121  SCIP_CALL_EXC( SCIPaddCons(_scip, cons) );
122  _cons.push_back(cons);
123  }
124 
125  // diag row down
126  for( size_t i = 0; i < _n; ++i )
127  {
128  SCIP_CONS * cons;
129  namebuf.str("");
130  namebuf<<"diag_row_down_"<<i;
131  SCIP_CALL_EXC( SCIPcreateConsLinear(_scip, & cons, namebuf.str().c_str(), 0, NULL, NULL, 0.0, 1.0,
133 
134  for( size_t j = 0; j < _n - i; ++j )
135  SCIP_CALL_EXC( SCIPaddCoefLinear(_scip, cons, _vars[i+j][j], 1.0) );
136  SCIP_CALL_EXC( SCIPaddCons(_scip, cons) );
137  _cons.push_back(cons);
138  }
139 
140  // diag col up
141  for( size_t j = 0; j < _n; ++j )
142  {
143  SCIP_CONS * cons;
144  namebuf.str("");
145  namebuf<<"diag_col_up_"<<j;
146  SCIP_CALL_EXC( SCIPcreateConsLinear(_scip, & cons, namebuf.str().c_str(), 0, NULL, NULL, 0.0, 1.0,
148 
149  for( size_t i = 0; i < _n - j; ++i )
150  SCIP_CALL_EXC( SCIPaddCoefLinear(_scip, cons, _vars[i][_n - j - i - 1], 1.0) );
151  SCIP_CALL_EXC( SCIPaddCons(_scip, cons) );
152  _cons.push_back(cons);
153  }
154 
155  // diag row up
156  for( size_t i = 0; i < _n; ++i )
157  {
158  SCIP_CONS * cons;
159  namebuf.str("");
160  namebuf<<"diag_row_up"<<i;
161  SCIP_CALL_EXC( SCIPcreateConsLinear(_scip, & cons, namebuf.str().c_str(), 0, NULL, NULL, 0.0, 1.0,
163 
164  for( size_t j = 0; j < _n - i; ++j )
165  SCIP_CALL_EXC( SCIPaddCoefLinear(_scip, cons, _vars[i+j][_n - j - 1], 1.0) );
166  SCIP_CALL_EXC( SCIPaddCons(_scip, cons) );
167  _cons.push_back(cons);
168  }
169 }
170 
171 
172 /* display the solution */
173 void scipexamples::QueensSolver::disp(std::ostream& out)
174 {
175  // get the best found solution from scip
176  SCIP_SOL * sol = SCIPgetBestSol(_scip);
177  out << "solution for " << _n << "-queens:" << endl << endl;
178 
179  // when SCIP did not succeed then sol is NULL
180  if (sol == NULL)
181  {
182  out << "no solution found" << endl;
183  return;
184  }
185 
186  for( size_t i = 0; i < _n; ++i )
187  {
188  for( size_t j = 0; j < _n; ++j )
189  out << " ---";
190  out << endl;
191 
192  for( size_t j = 0; j < _n; ++j )
193  {
194  out << "| ";
195  // we display a D in every field if x[i][j] = 1 which means that a queen will be placed there
196  if ( SCIPgetSolVal(_scip, sol, _vars[i][j]) > 0.5 )
197  out << "D ";
198  else
199  out << " ";
200  }
201  out << "|" << endl;
202  }
203  for( size_t j = 0; j < _n; ++j)
204  out << " ---";
205  out << endl;
206 }
207 
208 
209 /* destructor */
211 {
212  // since the SCIPcreateVar captures all variables, we have to release them now
213  for( size_t i = 0; i < _n; ++i )
214  {
215  for ( size_t j = 0; j < _n; ++j )
216  SCIP_CALL_EXC( SCIPreleaseVar(_scip, & _vars[i][j]) ); /*lint !e1551 !e1546*/
217  }
218  _vars.clear(); /*lint !e1551*/
219 
220  // the same for the constraints
221  for( vector<SCIP_CONS *>::size_type i = 0; i < _cons.size(); ++i ) /*lint !e1551*/
222  SCIP_CALL_EXC( SCIPreleaseCons(_scip, &_cons[i]) ); /*lint !e1551 !e1546*/
223  _cons.clear(); /*lint !e1551*/
224 
225  // after releasing all vars and cons we can free the scip problem
226  // remember this has allways to be the last call to scip
227  SCIP_CALL_EXC( SCIPfree(&_scip) ); /*lint !e1551 !e1546*/
228 }
229 
230 /* solve the n-queens problem */
232 {
233  // this tells scip to start the solution process
234  SCIP_CALL_EXC( SCIPsolve(_scip) );
235 }
#define NULL
Definition: def.h:239
SCIP_RETCODE SCIPcreateProb(SCIP *scip, const char *name, SCIP_DECL_PROBDELORIG((*probdelorig)), SCIP_DECL_PROBTRANS((*probtrans)), SCIP_DECL_PROBDELTRANS((*probdeltrans)), SCIP_DECL_PROBINITSOL((*probinitsol)), SCIP_DECL_PROBEXITSOL((*probexitsol)), SCIP_DECL_PROBCOPY((*probcopy)), SCIP_PROBDATA *probdata)
Definition: scip_prob.c:162
SCIP_RETCODE SCIPreleaseVar(SCIP *scip, SCIP_VAR **var)
Definition: scip_var.c:1251
#define FALSE
Definition: def.h:65
#define TRUE
Definition: def.h:64
QueensSolver(size_t n=8)
constructs the BP model for the n-queens problem
Definition: queens.cpp:28
SCIP_MESSAGEHDLR * SCIPgetMessagehdlr(SCIP *scip)
Definition: scip_message.c:171
void solve(void)
solves the queens problem using SCIPsolve
Definition: queens.cpp:231
SCIP_RETCODE SCIPcreate(SCIP **scip)
Definition: scip_general.c:339
SCIP_RETCODE SCIPaddCoefLinear(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var, SCIP_Real val)
exception handling for SCIP
void disp(std::ostream &out=std::cout)
display the solution
Definition: queens.cpp:173
SCIP_RETCODE SCIPsetObjsense(SCIP *scip, SCIP_OBJSENSE objsense)
Definition: scip_prob.c:1298
SCIP_RETCODE SCIPsolve(SCIP *scip)
Definition: scip_solve.c:2577
SCIP_RETCODE SCIPaddCons(SCIP *scip, SCIP_CONS *cons)
Definition: scip_prob.c:2822
Definition: pqueue.h:28
SCIP_RETCODE SCIPincludeDefaultPlugins(SCIP *scip)
void SCIPmessagehdlrSetQuiet(SCIP_MESSAGEHDLR *messagehdlr, SCIP_Bool quiet)
Definition: message.c:401
SCIP_RETCODE SCIPcreateVar(SCIP *scip, SCIP_VAR **var, const char *name, SCIP_Real lb, SCIP_Real ub, SCIP_Real obj, SCIP_VARTYPE vartype, SCIP_Bool initial, SCIP_Bool removable, SCIP_DECL_VARDELORIG((*vardelorig)), SCIP_DECL_VARTRANS((*vartrans)), SCIP_DECL_VARDELTRANS((*vardeltrans)), SCIP_DECL_VARCOPY((*varcopy)), SCIP_VARDATA *vardata)
Definition: scip_var.c:104
SCIP_RETCODE SCIPcreateConsLinear(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, SCIP_Real *vals, SCIP_Real lhs, SCIP_Real rhs, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode)
SCIP_SOL * SCIPgetBestSol(SCIP *scip)
Definition: scip_sol.c:2379
SCIP_RETCODE SCIPaddVar(SCIP *scip, SCIP_VAR *var)
Definition: scip_prob.c:1724
SCIP_RETCODE SCIPreleaseCons(SCIP *scip, SCIP_CONS **cons)
Definition: scip_cons.c:1187
n-queens example
public methods for message output
#define SCIP_CALL_EXC(x)
macro to call scip function with exception handling
~QueensSolver()
destructor this is the place to release the SCIP_VAR and SCIP_CONS pointers and to free the SCIP poin...
Definition: queens.cpp:210
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition: scip_sol.c:1410
SCIP_RETCODE SCIPfree(SCIP **scip)
Definition: scip_general.c:371