Mfcttrf

C++ - using const reference to prolong a member of a temporary, ok or UB?

Are there any instances of members of different Hogwarts houses coupling up and marrying each other?

Were Roman public roads build by private companies?

Variable Prefixes and Suffixes

Does the wording of the Wrathful Smite spell imply that there are other living beings that aren't considered "creatures"?

Is English tonal for some words, like "permit"?

How do email clients "send later" without storing a password?

Can I toggle Do Not Disturb on/off on my Mac as easily as I can on my iPhone?

Kerning feedback on logo

I changed a word from a source, how do I cite it correctly?

Are there take-over requests from autopilots?

Kingdom Map and Travel Pace

A medieval fantasy adventurer lights a torch in a 100% pure oxygen room. What happens?

Is there a standard terminology for female equivalents of terms such as 'Kingdom' and if so, what are the most common terms?

Have there been any countries that voted themselves out of existence?

Are there any space probes or landers which regained communication after being lost?

How would a village use its river that it shares with another village downstream?

Exact Brexit date and consequences

Is there a star over my head?

Dividing Divisive Divisors

How to determine the traffic avoidance manuver?

Are Democrats more likely to believe Astrology is a science?

Why should I always enable compiler warnings?

How can a resurrection system prevent the cheapening of death?

What is the standard practice in Constraint Programming modeling?

What is the difference between integer programming and constraint programming?2 stage stochastic programming to approximate many stage problemsWhat is the difference between integer programming and constraint programming?How to implement a custom global constraint in IBM's ILOG CP optimizerCombinatorial Optimization: Metaheuristics, CP, IP — “versus” or “and”?How to formulate maximum function in a constraint?How to select a Constraint Programming SolverCan docplex (module for Constraint Programming optimizer CPLEX for Python) read .lp or .mps file?To which area does constraint programming belong?

6

$begingroup$

I know some general concepts regarding Constraint Programming (e.g., the ones explained in this answer). I am interested in learning how to formulate a combinatorial optimisation problem as a constraint programming model. What steps should be taken for developing such a formulation? What is the standard practice/convention?

For example, the quality of LP-relaxation is an important factor for deciding the quality of an integer program. I was wondering what formulations are considered as good in constraint programming?

Finally, I appreciate if someone could give a simple example of an integer program and compares the way(s) it can be represented as a constraint program.

constraint constraint-programming

share|improve this question

edited 8 hours ago

Opt

asked 8 hours ago

OptOpt

33188 bronze badges

$endgroup$

add a comment | 

6

$begingroup$

I know some general concepts regarding Constraint Programming (e.g., the ones explained in this answer). I am interested in learning how to formulate a combinatorial optimisation problem as a constraint programming model. What steps should be taken for developing such a formulation? What is the standard practice/convention?

For example, the quality of LP-relaxation is an important factor for deciding the quality of an integer program. I was wondering what formulations are considered as good in constraint programming?

Finally, I appreciate if someone could give a simple example of an integer program and compares the way(s) it can be represented as a constraint program.

constraint constraint-programming

share|improve this question

edited 8 hours ago

Opt

asked 8 hours ago

OptOpt

33188 bronze badges

$endgroup$

add a comment | 

$begingroup$

I know some general concepts regarding Constraint Programming (e.g., the ones explained in this answer). I am interested in learning how to formulate a combinatorial optimisation problem as a constraint programming model. What steps should be taken for developing such a formulation? What is the standard practice/convention?

For example, the quality of LP-relaxation is an important factor for deciding the quality of an integer program. I was wondering what formulations are considered as good in constraint programming?

Finally, I appreciate if someone could give a simple example of an integer program and compares the way(s) it can be represented as a constraint program.

constraint constraint-programming

share|improve this question

edited 8 hours ago

Opt

asked 8 hours ago

OptOpt

33188 bronze badges

$endgroup$

share|improve this question

edited 8 hours ago

Opt

asked 8 hours ago

OptOpt

33188 bronze badges

share|improve this question

edited 8 hours ago

Opt

asked 8 hours ago

OptOpt

33188 bronze badges

asked 8 hours ago

OptOpt

33188 bronze badges

asked 8 hours ago

OptOpt

33188 bronze badges

1 Answer
1

active

oldest

votes

7

$begingroup$

at https://www.slideshare.net/PhilippeLaborie/an-introduction-to-cp-optimizer

you may find some information about RCPSP with Linear programming and constraint programming.

Plus https://tidel.mie.utoronto.ca/pubs/JSP_CandOR_2016.pdf

concludes

Comparing the best MIP results with that of CP, results show that MIP
performs similarly to CP for smaller problems in terms of proving
optimality. However, CP dominates MIP for larger problems both in
terms of proving optimality and solution quality.

Let me show how they are different and similar with OPL for jobshop :

With Linear Programming one can write

 int nbJobs = ...;
int nbMchs = ...;

range Jobs = 0..nbJobs-1;
range Mchs = 0..nbMchs-1;
// Mchs is used both to index machines and operation position in job

tuple Operation 
 int mch; // Machine
 int pt; // Processing time
;

Operation Ops[j in Jobs][m in Mchs] = ...;

dvar int+ s[j in Jobs][o in Mchs];
dexpr int e[j in Jobs][o in Mchs]=s[j][o]+Ops[j][o].pt;



minimize max(j in Jobs) e[j][nbMchs-1];
subject to 
 forall (m in Mchs,ordered i,j in Jobs, o1 in Mchs,o2 in Mchs:Ops[i][o1].mch == m && Ops[j][o2].mch == m)
 (e[i][o1]<=s[j][o2]) 

execute {
 for (var j = 0; j <= nbJobs-1; j++) 
 for (var o = 0; o <= nbMchs-1; o++) 
 write(s[j][o] + " ");
 
 writeln("");
 

whereas with Constraint Programming you would directly write a much better model that is within IBM CPLEX Optimization Studio

NB:

I am an IBM employee

share|improve this answer

answered 7 hours ago

Alex FleischerAlex Fleischer

25933 bronze badges

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Thanks Alex. The paper you attached includes a time indexed formulation for the scheduling problem studied. Such formulations are generally known for their good LP bound. I am not sure how good the time-indexed model is written but it seems that CP has performed better than this formulation. Can we solve an integer linear program with CP (without using alldifferent etc)? Is that a bad practice? It seems that the quality of LP bound is not quite important for CP (right?). Feel free to add details to your answer (not in the comment section in response to my comment).
  $endgroup$
  – Opt
  5 hours ago
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  You can solve an integer linear model with CP. You may solve an IP with both LP and CP, or even hybrid the 2 techniques. But for scheduling models, CPO intervals will outperform that CP naïve formulation. 20 years effort as you can read at ibm.com/developerworks/community/forums/html/…
  $endgroup$
  – Alex Fleischer
  5 hours ago
  

  
  
  
  

add a comment | 

Your Answer

StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "700"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);

else
createEditor();

);

function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
imageUploader:
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/4.0/"u003ecc by-sa 4.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
,
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);



);

draft saved

draft discarded

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name

Email

Required, but never shown

StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2for.stackexchange.com%2fquestions%2f1500%2fwhat-is-the-standard-practice-in-constraint-programming-modeling%23new-answer', 'question_page');

);

Post as a guest

Name

Email

Required, but never shown

7

$begingroup$

at https://www.slideshare.net/PhilippeLaborie/an-introduction-to-cp-optimizer

you may find some information about RCPSP with Linear programming and constraint programming.

Plus https://tidel.mie.utoronto.ca/pubs/JSP_CandOR_2016.pdf

concludes

Comparing the best MIP results with that of CP, results show that MIP
performs similarly to CP for smaller problems in terms of proving
optimality. However, CP dominates MIP for larger problems both in
terms of proving optimality and solution quality.

Let me show how they are different and similar with OPL for jobshop :

With Linear Programming one can write

 int nbJobs = ...;
int nbMchs = ...;

range Jobs = 0..nbJobs-1;
range Mchs = 0..nbMchs-1;
// Mchs is used both to index machines and operation position in job

tuple Operation 
 int mch; // Machine
 int pt; // Processing time
;

Operation Ops[j in Jobs][m in Mchs] = ...;

dvar int+ s[j in Jobs][o in Mchs];
dexpr int e[j in Jobs][o in Mchs]=s[j][o]+Ops[j][o].pt;



minimize max(j in Jobs) e[j][nbMchs-1];
subject to 
 forall (m in Mchs,ordered i,j in Jobs, o1 in Mchs,o2 in Mchs:Ops[i][o1].mch == m && Ops[j][o2].mch == m)
 (e[i][o1]<=s[j][o2]) 

execute {
 for (var j = 0; j <= nbJobs-1; j++) 
 for (var o = 0; o <= nbMchs-1; o++) 
 write(s[j][o] + " ");
 
 writeln("");
 

whereas with Constraint Programming you would directly write a much better model that is within IBM CPLEX Optimization Studio

NB:

I am an IBM employee

share|improve this answer

answered 7 hours ago

Alex FleischerAlex Fleischer

25933 bronze badges

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Thanks Alex. The paper you attached includes a time indexed formulation for the scheduling problem studied. Such formulations are generally known for their good LP bound. I am not sure how good the time-indexed model is written but it seems that CP has performed better than this formulation. Can we solve an integer linear program with CP (without using alldifferent etc)? Is that a bad practice? It seems that the quality of LP bound is not quite important for CP (right?). Feel free to add details to your answer (not in the comment section in response to my comment).
  $endgroup$
  – Opt
  5 hours ago
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  You can solve an integer linear model with CP. You may solve an IP with both LP and CP, or even hybrid the 2 techniques. But for scheduling models, CPO intervals will outperform that CP naïve formulation. 20 years effort as you can read at ibm.com/developerworks/community/forums/html/…
  $endgroup$
  – Alex Fleischer
  5 hours ago
  

  
  
  
  

add a comment | 

7

$begingroup$

at https://www.slideshare.net/PhilippeLaborie/an-introduction-to-cp-optimizer

you may find some information about RCPSP with Linear programming and constraint programming.

Plus https://tidel.mie.utoronto.ca/pubs/JSP_CandOR_2016.pdf

concludes

Comparing the best MIP results with that of CP, results show that MIP
performs similarly to CP for smaller problems in terms of proving
optimality. However, CP dominates MIP for larger problems both in
terms of proving optimality and solution quality.

Let me show how they are different and similar with OPL for jobshop :

With Linear Programming one can write

 int nbJobs = ...;
int nbMchs = ...;

range Jobs = 0..nbJobs-1;
range Mchs = 0..nbMchs-1;
// Mchs is used both to index machines and operation position in job

tuple Operation 
 int mch; // Machine
 int pt; // Processing time
;

Operation Ops[j in Jobs][m in Mchs] = ...;

dvar int+ s[j in Jobs][o in Mchs];
dexpr int e[j in Jobs][o in Mchs]=s[j][o]+Ops[j][o].pt;



minimize max(j in Jobs) e[j][nbMchs-1];
subject to 
 forall (m in Mchs,ordered i,j in Jobs, o1 in Mchs,o2 in Mchs:Ops[i][o1].mch == m && Ops[j][o2].mch == m)
 (e[i][o1]<=s[j][o2]) 

execute {
 for (var j = 0; j <= nbJobs-1; j++) 
 for (var o = 0; o <= nbMchs-1; o++) 
 write(s[j][o] + " ");
 
 writeln("");
 

whereas with Constraint Programming you would directly write a much better model that is within IBM CPLEX Optimization Studio

NB:

I am an IBM employee

share|improve this answer

answered 7 hours ago

Alex FleischerAlex Fleischer

25933 bronze badges

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Thanks Alex. The paper you attached includes a time indexed formulation for the scheduling problem studied. Such formulations are generally known for their good LP bound. I am not sure how good the time-indexed model is written but it seems that CP has performed better than this formulation. Can we solve an integer linear program with CP (without using alldifferent etc)? Is that a bad practice? It seems that the quality of LP bound is not quite important for CP (right?). Feel free to add details to your answer (not in the comment section in response to my comment).
  $endgroup$
  – Opt
  5 hours ago
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  You can solve an integer linear model with CP. You may solve an IP with both LP and CP, or even hybrid the 2 techniques. But for scheduling models, CPO intervals will outperform that CP naïve formulation. 20 years effort as you can read at ibm.com/developerworks/community/forums/html/…
  $endgroup$
  – Alex Fleischer
  5 hours ago
  

  
  
  
  

add a comment | 

$begingroup$

at https://www.slideshare.net/PhilippeLaborie/an-introduction-to-cp-optimizer

you may find some information about RCPSP with Linear programming and constraint programming.

Plus https://tidel.mie.utoronto.ca/pubs/JSP_CandOR_2016.pdf

concludes

Comparing the best MIP results with that of CP, results show that MIP
performs similarly to CP for smaller problems in terms of proving
optimality. However, CP dominates MIP for larger problems both in
terms of proving optimality and solution quality.

Let me show how they are different and similar with OPL for jobshop :

With Linear Programming one can write

 int nbJobs = ...;
int nbMchs = ...;

range Jobs = 0..nbJobs-1;
range Mchs = 0..nbMchs-1;
// Mchs is used both to index machines and operation position in job

tuple Operation 
 int mch; // Machine
 int pt; // Processing time
;

Operation Ops[j in Jobs][m in Mchs] = ...;

dvar int+ s[j in Jobs][o in Mchs];
dexpr int e[j in Jobs][o in Mchs]=s[j][o]+Ops[j][o].pt;



minimize max(j in Jobs) e[j][nbMchs-1];
subject to 
 forall (m in Mchs,ordered i,j in Jobs, o1 in Mchs,o2 in Mchs:Ops[i][o1].mch == m && Ops[j][o2].mch == m)
 (e[i][o1]<=s[j][o2]) 

execute {
 for (var j = 0; j <= nbJobs-1; j++) 
 for (var o = 0; o <= nbMchs-1; o++) 
 write(s[j][o] + " ");
 
 writeln("");
 

whereas with Constraint Programming you would directly write a much better model that is within IBM CPLEX Optimization Studio

NB:

I am an IBM employee

share|improve this answer

answered 7 hours ago

Alex FleischerAlex Fleischer

25933 bronze badges

$endgroup$

 int nbJobs = ...;
int nbMchs = ...;

range Jobs = 0..nbJobs-1;
range Mchs = 0..nbMchs-1;
// Mchs is used both to index machines and operation position in job

tuple Operation 
 int mch; // Machine
 int pt; // Processing time
;

Operation Ops[j in Jobs][m in Mchs] = ...;

dvar int+ s[j in Jobs][o in Mchs];
dexpr int e[j in Jobs][o in Mchs]=s[j][o]+Ops[j][o].pt;



minimize max(j in Jobs) e[j][nbMchs-1];
subject to 
 forall (m in Mchs,ordered i,j in Jobs, o1 in Mchs,o2 in Mchs:Ops[i][o1].mch == m && Ops[j][o2].mch == m)
 (e[i][o1]<=s[j][o2]) 

execute {
 for (var j = 0; j <= nbJobs-1; j++) 
 for (var o = 0; o <= nbMchs-1; o++) 
 write(s[j][o] + " ");
 
 writeln("");
 

share|improve this answer

answered 7 hours ago

Alex FleischerAlex Fleischer

25933 bronze badges

answered 7 hours ago

Alex FleischerAlex Fleischer

25933 bronze badges

answered 7 hours ago

Alex FleischerAlex Fleischer

25933 bronze badges