constraint-programming Questions - OR-Exchange

Graph Coloring Solvers

2010-06-04T02:00:27Z

Hey,

I'm curious about the state of the art in solving graph coloring (by solving I mean finding the optimal coloring and proving that it is optimal).

Can someone point me to papers describing solvers/implementation of solvers both for finding colorings quickly and for proving optimality which are state of the art?

Thanks

Minimal Backtracking Proof Tree

2010-05-06T00:11:56Z

When trying to prove that a particular instance of a problem like SAT is unsatisfiable, generally one explores the search tree using an algorithm like DPLL and the proof of unsatisfiability consists of the exhaustive exploration of the search tree - i.e. try an partial assignment of values to variables, do propagation and if the domain of a variable becomes empty, you know the assignment does not satisfy the instance so you backtrack. By propagation I mean, one looks at every constraint and then for every variable in the constraint, one prunes the values in the domain of the variable which are not part of any model satisfying that particular constraint.

My question is that how hard in terms of computational complexity is to find a search tree proving infeasibility of minimal size, i.e. if the size of the search tree is $S$, then how hard is it to find the minimal such search tree given that the size of the input is taken as $S$ (Note - that can be much larger than the size of the original problem, exponential in the worst case).

Any finite domain NLP benchmark tests?

2010-04-10T09:43:09Z

Hi all, I would like to perform some benchmarks over a set of nonlinear problems where some functions (objective or nonlinear constrains) are defined over restricted domains, e.g.

an_objective - > min

wrt

x>0

x + 5y + 0.01 * x * sqrt(x) < -10

I would easily write my own set of tests (there are some already done), but since my solver is involved (http://openopt.org/ralg, latest stable release vs my current implementation vs some other solvers) it would be much better to have a set taken from an external source, preferably an article or a book. I have searched google with "finite domain non linear benchmark" but there are no appropriate results (I don't know about some non-free journals, however).

So, does anyone know any appropriate source?

Thank you in advance, D.

question about OR

2010-03-18T14:45:20Z

Maximize P= 10x + 2y [rest deleted. No really: no homework!]

Extracting Gomory cuts out of Cgl (Coin-or)

2010-01-05T02:19:58Z

Hey,

I'm trying to extract Cgl Gomory cuts out of the Cgl (Cut Generation Library) of Coin-Or The following is the code I'm using to extract the cuts -

OsiCuts cutlist;
CglGomory * gomory = new CglGomory();
gomory->setLimit(100);
gomory->generateCuts(*sym, cutlist) ;

where sym is an instance of OsiSymSolverInterface (the OsiSolverInterface for Symphony). Unfortunately the code is segfaulting at generateCuts somewhere inside the method as far as I've been able to determine using gdb.

Extraction of CglProbing cuts is likewise segfaulting again inside the generateCuts method of the CglProbing class.

All other cuts seem to be working fine.

If someone could shed some light on this or even better, post/link to an example file using these cuts or a tutorial of some sort, that would great. If there's an example/tutorial for extracting cuts out of some other solver like SCIP instead of Coin-OR, that would work too.

Thanks

CP and Integer programming

2009-12-31T20:17:06Z

Hi everybody,

Does anyone know a good reference or tutorial in the spirit of the book "Model building in mathematical programming" for Constraint Programming techniques for solving MIPs?

Thanks in advance Regards, Shahin

How do you decide whether MIP or CP is more appropriate?

2009-12-01T15:34:56Z

What are some guidelines for deciding whether a MIP or CP approach is more appropriate for modeling an optimization problem? Or in what cases should CP be used instead of MIP?