(The question focuses in particular on the solver Gecode, but I think it is general enough for CP).

  1. Given a vector of variables x[0], ..., x[n], all with domain {0,...,m} where m>>n, I would like to model the following constraint: (i < j) <=> (x[i] < x[j]) for all i,j = 0,..,n. I think this constraint must come up quite often, so there might be some well-known way to model it, or even a pre-made constraint among those offered by Gecode, but I am unable to find any suitable one here. (I cannot really understand the documentation of odered_nvector, which has a name that suggests something similar to what I am looking for, but it doesn't look like it does what I want, right?)

  2. If the value 0 in the domain is used as a joker value, and the constraint should be limited only to those variables which are not mapped to the joker value, what would be the best way to proceed? To be clear, the constraint would then be: (x[i] == 0) || (x[j] == 0) || ((i < j) <=> (x[i] < x[j])). (For example, for alldifferent there is the corresponding alldifferent_except_0.)

  3. Is there a standard way to generalise this constraint when the relationship is not necessarily "<"? For example, given a binary relation R on the set {0,...,n} and a binary relation S on {0,...,m}, is there a standard way to model the constraint ((i,j) in R) <=> ((x[i],x[j]) in S)? (In particular, if using Gecode, are there pre-made global constraints which are useful in this case?)

asked 19 Feb, 12:40

Alberto%20Santini's gravatar image

Alberto Santini
11
accept rate: 0%

edited 19 Feb, 12:41


For the first part, I think you want the strictly_increasing constraint (increasing if you use weak rather than strong inequalities). Sorry, can't answer the other two parts.

link

answered 19 Feb, 15:50

Paul%20Rubin's gravatar image

Paul Rubin ♦♦
14.5k412
accept rate: 19%

Thanks, Paul. You are right about the first part. I am having a hard time figuring out the other two parts. In general it seems to me that gecode has a lot of constraints, but poor support for mixing them and a weird API, while CPLEX CPO has few pre-built constraints, but combining them is as easy as using some overloaded operator (C++), plus their API is really straightforward. Both could use some better documentation and tutorials at a level beyond "Solve SEND+MORE=MONEY". If I manage to figure out any of them, I pledge to write one! :-)

(20 Feb, 05:13) Alberto Santini
Your answer
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "Title")
  • image?![alt text](/path/img.jpg "Title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported

Tags:

×37
×1

Asked: 19 Feb, 12:40

Seen: 112 times

Last updated: 20 Feb, 05:14

OR-Exchange! Your site for questions, answers, and announcements about operations research.