标签: constraint-programming

我想知道熟悉 Google 优化工具的人是否可以解决这个问题。我正在查看 Google 的员工调度和 N 皇后示例。这两个示例似乎都使优化器仅在硬约束下运行（例如，必须是这种情况），但似乎没有解决（这是首选但不是必需的）。是否支持软约束？或者此时软约束的唯一实现是optaplanner？

我并不反对 optaplanner。只是需要付出更多的努力来学习足够的 java 和所使用的“流口水”语法。

I am a beginner in Constraint Programming using Minizinc and I need help from experts in the field.

How can I compute all the possible combinations: 6 Rectangles inside the Square (10x10) using Minizinc?

Considering that the RESTRICTIONS of the problem are:

1) No Rectangle Can Overlap

2) The 6 rectangles may be vertical or horizontal

OUTPUT:

我从SICStus Prolog开始,我想定义一个变量,比如说StartingTimes,有一个由list定义的域[1, 5, 10]

我怎样才能在SICStus Prolog中做到这一点？

我会做的事情如下:

 domain(StartingTimes, 1, 10)
 StartingTimes #= 1 #\/ StartingTimes #= 5 #\/ StartingTimes #= 10

但那太可怕了.必须有一个简单的方法来做到这一点.也许fd_sets？

注意:我试图找出它是如何在手动中完成的,但prolog使用常用词,并且很难使用谷歌.

我正在尝试为global_cardinality我的程序添加约束,并在SICStus Prolog的手册中写道:

global_cardinality(+ XS,+瓦尔斯)

global_cardinality(+ XS,+瓦尔斯+选项)

其中Xs = [X1,...,Xd]是整数或域变量的列表,Vals = [K1-V1,...,Kn-Vn]是对的列表,其中每个键Ki​​是唯一的整数Vi是域变量或整数.如果Xs的每个元素等于某个键,则为真,对于每对Ki-Vi,Xs的恰好Vi元素等于Ki.

现在我可以写:

global_cardinality([A,B,C], [1-2, 2-1]).

说这个数字1会被使用两次.该号码2仅使用一次.

但我想说的是这个数字1会用到:once, twice or three times

根据手册我需要一个域变量但是它的正确语法是什么？

clpfd是SWI Prolog中整数的约束编程库.集合中是否有类似的库？如果没有,你知道任何有用的文章来实现这样的库吗？

它可行吗？我正在寻找任何形式的输入,因为我的谷歌搜索没有引起任何兴趣.

编辑:搜索时使用引号可以获得更好的结果(doh!).嗯...很高兴收到反馈意见.

编辑:有一个包含B-Prolog(clpset)的库正是这样做的.

约束模型可能具有约束或向约束求解器提供提示,以通过定义求解变量的顺序来更有效地解决问题.有没有一种机制来指定MiniZinc或FlatZinc中需要解决的变量的顺序？

我必须扩展项目的输出和解决方案（安排考试时间）：

-将结构扩展到五天（我一直工作一天）：我仔细考虑了插槽时间的天数（5 * 10），然后调整输出！有没有更好的办法？

现在整个代码：

include "globals.mzn";include "alldifferent.mzn";

%------------------------------Scalar_data----------------------
int: Students;          % number of students
int: Exams;             % number of exams
int: Rooms;             % number of rooms
int: Slotstime;         % number of slots
int: Days;              % a period i.e. five days
int: Exam_max_duration; % the maximum length of any exam (in slots)

%------------------------------Vectors--------------------------
array[1..Rooms] of int  : Rooms_capacity;
array[1..Exams] of int  : Exams_duration; % the duration of written test
array[1..Slotstime, 1..Rooms] of 0..1: Unavailability;
array[1..Students,1..Exams]   of 0..1: Enrollments;

招生会跟踪每个学生的注册情况；从中我可以得出要参加考试的学生人数，以便根据能力选择合适的房间

%---------------------------Decision_variables------------------ …

可再现的例子:

我描述了一个简单的0/1-背包问题lpSolveAPI在ř,它应该返回2级的解决方案:

library(lpSolveAPI)

lp_model= make.lp(0, 3)
set.objfn(lp_model, c(100, 100, 200))
add.constraint(lp_model, c(100,100,200), "<=", 350)
lp.control(lp_model, sense= "max")
set.type(lp_model, 1:3, "binary")

lp_model
solve(lp_model)
get.variables(lp_model)
get.objective(lp_model)
get.constr.value((lp_model))
get.total.iter(lp_model)
get.solutioncount(lp_model)

问题:

但get.solutioncount(lp_model)表明1找到了解决方案:

> lp_model
Model name: 
           C1   C2   C3         
Maximize  100  100  200         
R1        100  100  200  <=  350
Kind      Std  Std  Std         
Type      Int  Int  Int         
Upper       1    1    1         
Lower       0    0    0         
> solve(lp_model)
[1] 0
> get.variables(lp_model)
[1] 1 …

我在Prolog很新,并在swi-prolog.org上找到了解决数据的例子.但我无法运行它.我抬头看着same_length而且只有same_length/2没有same_length/1.也是all_distinct/2没有all_distinct/0.http://www.swi-prolog.org/pldoc/man?section=clpfd-sudoku

这是我的错误:

ERROR: d:/.../prolog/sudoku.pl:5:10: Syntax error: Operator expected
% d:/.../prolog/sudoku compiled 0.00 sec, 0 clauses
Warning: The predicates below are not defined. If these are defined
Warning: at runtime using assert/1, use :- dynamic Name/Arity.
Warning: 
Warning: all_distinct/1, which is referenced by
Warning:        d:/.../prolog/sudoku.pl:16:8: 2-nd clause of blocks/3

这是SWI-Prolog示例的代码:

    use_module(library(clpfd)). 

    sudoku(Rows) :-
        length(Rows, 9), maplist(same_length(Rows), Rows),
        append(Rows, Vs),
        Vs in 1..9,
        maplist(all_distinct, Rows),
        transpose(Rows, Columns),
        maplist(all_distinct, Columns),
        Rows = [As,Bs,Cs,Ds,Es,Fs,Gs,Hs,Is],
        blocks(As, …

我一直在 MiniZinc 中使用一个简单的 n-queens 模型：

include "globals.mzn";
int: n_queens = 8;
array[1..n_queens] of var 1..n_queens: queens;

constraint alldifferent(queens);
constraint alldifferent(i in 1..n_queens) (queens[i] + i);
constraint alldifferent(i in 1..n_queens) (queens[i] - i);
solve satisfy;

该MiniZinc手册中提到failures的“这是故障的叶节点的数目”。以下是运行模型后的统计数据：

%%%mzn-stat: initTime=0.000576
%%%mzn-stat: solveTime=0.000822
%%%mzn-stat: solutions=1
%%%mzn-stat: variables=24
%%%mzn-stat: propagators=19
%%%mzn-stat: propagations=1415
%%%mzn-stat: nodes=47
%%%mzn-stat: failures=22
%%%mzn-stat: restarts=0
%%%mzn-stat: peakDepth=5
%%%mzn-stat-end

有 22 次失败。作为约束编程的初学者，我的理解是范式的整个目的是尽可能地修剪和避免叶节点。我特别困惑，因为搜索树的峰值深度报告为 5（不是 8）。

我对这些统计数据的解释正确吗？如果是，为什么模型中存在叶节点故障？我会通过尝试减少这些失败来创建更好的模型吗？