标签: constraint-programming

PHP有任何约束编程库吗？东西会能够处理类似的情况这样.

我正在阅读文档中的矛盾内容.

一方面,这段经文似乎表明连续的计划变量是可能的:

计划值范围是计划变量的可能计划值的集合.该集合可以是离散的(例如,行1,2,3或4)或连续的(例如,在0.0和1.0之间的任何双倍).

另一方面,在定义计划变量时,必须ValueRangeProvider在字段上指定要用于值集的注释:

Solution实现具有返回Collection的方法.该集合中的任何值都是此计划变量的可能计划值.

这两个片段都在文档的相同部分(http://docs.jboss.org/drools/release/latest/optaplanner-docs/html_single/#d0e2518)

那么,这是什么？我可以使用full double作为我的计划变量,还是需要将其范围限制为特定值Collection？

看看实际的算法,我没有看到任何实际上适合优化连续变量的东西,所以我怀疑它是否可能,但是如果澄清并明确表示它会很好.

我的目标是定义一个内射函数f: Int -> Term，其中Term有一些新的类型。提到内射函数的定义后，我写了以下内容：

(declare-sort Term)
(declare-fun f (Int) Term)
(assert (forall ((x Int) (y Int))
                (=> (= (f x) (f y)) (= x y))))
(check-sat)

这将导致超时。我怀疑这是因为求解程序试图验证Int域中所有值的断言，该值是无限的。

我还检查了上述模型是否适用于某些自定义排序，而不是Int：

(declare-sort Term)
(declare-sort A)
(declare-fun f (A) Term)
(assert (forall ((x A) (y A))
                (=> (= (f x) (f y)) (= x y))))
(declare-const x A)
(declare-const y A)
(assert (and (not (= x y)) (= (f x) (f y))))
(check-sat)
(get-model) …

那是什么

我正在尝试为锦标赛制作一套最佳的方括号(最佳约束条件).

问题

我不知道如何处理这个问题. 该论文是相当高的水平,但讨论解决与约束编程集分割问题的可能性.它还指出大多数集合分区问题都是通过整数编程解决的.我主要是在寻找一个模仿的例子.问题类似于这个问题.我见过的大多数约束示例都定义了特定的分区总数.是否可以建模一个系统,其中分区将由约束和参与者集动态确定？我会链接示例,但由于我的声誉,我仅限于2.

一个更具体的例子

已知值

• 参加人数为N.
• 每个参与者具有与他们相关联的权重W.

约束

• 支架(组)由2,3,4,6,7或8个参与者组成.
• 每个参与者只在一个支架中.
• 最低加权参与者与括号中最高加权参与者之间的差异不得超过15%.
• 倾向于在所有其他支架尺寸上创建尺寸为8和4的支架.

例如,说有8个参与者.

{{1,W = 100},{2,W = 103},{3,W = 105},{4,W = 106},{5,W = 110},{6,W = 114},{ 7,W = 120},{8,W = 125}}

一种可能的解决方案是:{1,2,3},{4,5},{6,7,8}

更优化的解决方案是:{1,2,3,4},{5,6,7,8},因为这有利于先前解决方案中的4,8个大小的集合.

是否可以将集合划分为动态数量的子集？

感谢你的宝贵时间!

我正在尝试使用SWI prolog和CLP进行项目调度.我设法支持顺序依赖,但我正在努力避免双重预订人.

我有一个名为Schedule的列表,其中包含[taskname,starttime]等元素,其中starttime是约束求解器的自由变量.它们已经受到顺序依赖性的限制.

我正在尝试编写一个这样的循环来排除双重预订:

  forall /* or maybe foreach*/ (isa(P,person), (
    % Filter scheduled tasks on that person...
    include(\[T,S]^(assigned(T,P)), Schedule, HisSchedule),
    % Present what serialized expects..
    maplist(\[T,S]^S^true, HisSchedule, Sts),
    % duration is just user-defined data... 
    maplist(\[T,S]^D^(duration(T,D)), HisSchedule, Dus),
    % Hit it...
    serialized(Sts, Dus)
  )),

随着foreach它总是失败和forall它总是成功而不会约束任何东西.

就这个循环而言,Schedule是全局的,目的是使用序列化来约束其starttime元素.OTOH,HisSchedule,Sts和Dus取决于特定的人.因此,我认为我需要foreach让Schedule快乐,但是要让HisSchedule等快乐.那是问题吗？如果是这样,我该如何解决？

我希望有人能就这个话题对我有所了解.如果这被认为是一个愚蠢的问题,我很乐意立即删除这个问题.

我正在设计一个课程时间表系统,通过研究,我偶然发现了GA和Constraint Programming作为解决问题的方法.但是,我不太明白两者之间的差异以及一方面有什么优势.我希望有人会以外行的名义向我解释这一点,或者将我引导到一个有这个主题的网站.

提前致谢!

最好的祝福.

我每年都会帮助一个青年营.将参加者分配到卧室是一项艰巨的任务 - 有92间卧室,活动持续一周,与会者可以待上不同的时间,床需要重复使用.

目前需要一名志愿者〜一周时间将人员分配到房间.有很多规则可供遵循,因为并非所有与会者都会在整个一周内完成任务,而是在夜间进行.

我想自动完成任务.编程语言和计算成本是实现细节,我可以根据需要格式化输入数据/规则(包括代码生成).任何可以节省繁琐时间的东西......

可用的技术

我没有领域专业知识,所以首先我必须了解可能的方法.

约束编程似乎是明显的方法,因为有规则要遵循.但是规则不是二进制的,前一个线程向我介绍了软约束和成本函数.

当我阅读成本函数时,它指出了机器学习和神经网络.这些都很受欢迎,但我相信需要一组数据来训练它们,这是我没有的东西 - 我可以创建,但这需要花费更多的时间而不是手动分配.我已经知道了这些限制因素:我不必从数据中推断它们.

• 问:Prolog中的成本函数与机器学习中的成本函数不同吗？
• 问:机器学习是否适合这个问题？
• 问:我还忽略了其他方法吗？

我找不到在网上,期刊等讨论的房间分配问题; 它必须是常见的,因此我缺少一些特定于域的术语.对于需要它的医院和酒店,我确信它已经得到很好的研究.

• 问:文献中提到的床位分配问题是什么？

基于时间的作业

我也有一个概念性的问题.我可以看到我如何解决一个晚上,但我怎么想多个夜晚建模？

约束求解器(或其他技术)不知道时间(并且2016-09-05之前不会知道2016-09-06),但我需要输入人们住的夜晚并且每晚看到作业.

• 问:我应该如何考虑时间序列？

从概念上把握产出

第二个是:系统如何输出分配给哪些卧室的人？在Prolog数独求解器(例如)中,可以有多个解决方案,但这有很多约束.对于模糊约束,我最终会得到人X在房间Y中的概率,以及他们也在房间Z中的概率(如果你愿意的话,量子叠加)？

• 问:输出结果如何？

部分解决方案还可以

必须手动调整的首次通过分配将节省时间.就像手动分配"复杂"的参与者(如夜间安全,谁在特定房间睡觉)并让计算机完成其余工作一样.

• 问:这是否使问题更容易解决？

我的尝试

最初我想过从13年前复活我一个学期的Prolog知识,并为所有标准设置约束.这适用于一个非常简单的案例,但是一旦我超越了"必须"标准,我就失败了灰色规则和妥协.

示例规则(约束)

所有规则都有不同的优先级 为了简化我的分组must,should和nice.

• must 同房性别
  • 除非被"必须与之分享"选项(如夫妻)所覆盖
• must 需要残障人士客房的人可以获得
• must 如果与会者需要一个带婴儿床的房间,他们必须得到它
• must 指定"必须与X共享"或"必须与Y&Z共享"的与会者必须被分配到同一个会议室
  • 他们可能不会在相同的夜晚停留(例如,A-Thu停留,周二至周五为B).在整个期间阻止床是好的)
  • "必须共享"关系可以是单向的或双向的 - 我也可以实现
• must/should 如果与会者需要一个房间,他们必须得到它,除非没有可能的解决方案
• should按角色分组参加会议的与会者,例如"青年","青年领袖","厨师","领导者".有些角色比其他角色更适合混合.
• should尽量减少跳房:一旦你有一张床,整晚都待在这里.除非没有可能的解决方案
• should 情侣优先客房配有双人床
  • (我还没有弄清楚如何为此制定规则,这并不是假设所有"必须与之分享"的关系都是夫妻关系.目前它是用人类知识完成的)
• nice 他们参加的大学会议室的参加者(如适用)
• nice 优先考虑带有卫浴设施的房间,以及非青年角色

有更多的规则(例如,有饮食要求的人必须留在特定的建筑物中),但这提供了足够的例子.

每个房间的场地收费不是每个房间,所以尽量减少使用的房间数量并不重要 - 至少今年. …

我之前曾问过这个问题,并希望继续跟进,因为我尝试了其他一些事情并且他们没有完全解决问题.

我本质上是在尝试优化R中的NLP类型问题,它具有二进制和整数约束.相同的代码如下:

# Input Data
DTM <- sample(1:30,10,replace=T)
DIM <- rep(30,10)
Price <- 100 - seq(0.4,1,length.out=10)

# Variables that shall be changed to find optimal solution
Hike <- c(1,0,0,1,0,0,0,0,0,1)
Position <- c(0,1,-2,1,0,0,0,0,0,0)

# Bounds for Hikes/Positions
HikeLB <- rep(0,10)
HikeUB <- rep(1,10)
PositionLB <- rep(-2,10)
PositionUB <- rep(2,10)

library(Rsolnp)

# x <- c(Hike, Position)
# Combining two arrays into one since I want 
# to optimize using both these variables

opt_func <- function(x) {

  Hike <- head(x,length(x)/2)
  Position …

我有一个约束问题,我试图用python-constraint解决

所以假设我有3个位置: loc1,...loc3

另外,我有7个设备: device1,...device7

每个位置的最大设备数量:( loc1:3, loc2:4, loc3:2 例如最多3个设备loc1等等......)

以及有关位置和设备的一些限制:

loc1: device1, device3, device7,

loc2: device1, device3, device4, device5, device6, device7

loc3: device2, device4, device5, device6

(仅作为示例device1,device3也device7可以是loc1.)

我正在尝试为位置设备提供一组可能的选项.

    from constraint import *
    problem = Problem()
        for key in locations_devices_dict:
           problem.addVariable(key,locations_devices_dict[key])
           # problem.addVariable("loc1", ['device1', 'device3', 'device7'])
   problem.addConstraint(AllDifferentConstraint())

我一直坚持如何做约束.我试过了:

problem.addConstraint(MaxSumConstraint(3), 'loc1')

但它不起作用,MaxSumConstraint不总结我需要的东西.

所有设备必须放在某处

解决方案:

loc1: device1, device3
loc2: device4, device6, device7
loc3: device2, device5

有人有想法吗？

(另一个python包/不使用任何包,如果有人有任何建议也是个好主意...)

我有一个系统,我需要计算每个变量的可能值范围(我不需要找到系统的解决方案).以下是示例系统的说明:

每条蓝线都是一个节点(由它上面的标签命名),灰线是节点之间的边缘.给出了初始约束:例如,边缘BC可以是0和1之间的任何实数,并且边缘BE可以是大于或等于9的任何数.节点不能跨越其他节点.将它们想象成可以伸展和缩回的金属条是有帮助的,推动蓝色板周围.

我的目标是为每条边计算它们的最小和最大长度.起始约束设置了系统,但最终结果可能比它们更受限制.例如,边缘DF的起始最小值/最大值为(2,∞),但是你可以看到它实际上不能短于3,因为收缩它将D拉入E,E拉向F,而EF有一个至少为3.最终的结果就是这个,我相信:

需要注意的是,我需要一种可以扩展到数十万个节点的算法,这个节点比这个例子更密集.它不能以指数方式增加运行时间,因为我还必须运行这个算法数十万次.

我尝试了一种方法,它给出了一些更多约束值,但不是最受约束的值.为了使方法可视化,我基本上尽可能地将所有板拉到左边,然后记录每个板的最大位置.然后我做了同样的事情,将它们拉到右边.然后,对于每个边,我只是找到每个板的值之间的差异.此方法非常有效地找到最大值,但问题是当您遇到类似于此示例的情况时,其中CD被BC和DE"锁定"到BE.它不能是6,因为系统只允许它比9短.我需要一种方法来找到真正的最小值7.我的方法不捕获"锁定"关系:当你拉C全部在左边的路上,BC是0,当你把D一直拉到右边时,DE是0,但如果CD是6,它们不能都是0.

在这个例子中,很容易看出CD受到BE的约束,但在实践中,系统会比例子更密集和更大,并且发现这种情况似乎并非易事.如果该方法涉及在本地搜索它,我担心它会扩展得很差,但这可能是唯一的方法.

如果将其建模为线性规划问题(AB + BC = AC,AB> 1等),则可能会利用该系统的某些属性:约束的所有系数均为1,并且约束中只有加法和减法.

有没有人对如何解决这个问题有任何建议？或者对我应该实际希望的运行时间复杂程度有任何见解？谢谢!