英文:
When resulting in an infeasible model, what tips are there to break down the nexus of the issue
问题
我是新手使用or-tools，并且被要求最小化一个具有大量IntVar变量的二次目标函数。我不知道从哪里开始分解可能涉及不可行模型的问题，并欢迎任何开始的提示。
我已经观看了几个关于使用or工具的视频，并在一个较小规模的测试文件中进行了实验，但我的主要问题导致了不可行的模型。我认为问题在于我做的视频/实验中变量较少，但再次强调，这是我第一次使用OR工具。
这是我运行模型时的输出：
开始CP-SAT求解器v9.6.2534
参数：log_search_progress: true enumerate_all_solutions: true
将工作进程数设置为1
初始优化模型'': (模型指纹: 0x8f376cd881ed44f1)
#变量: 214 (#整数: 1在目标中)
- 126个布尔值在[0,1]
- 2在[-100000,100000]
- 84在[0,96]
- 2在[0,2000000]
#kIntProd: 4004
在0.00秒时开始预处理
预处理后的约束#1142不可满足（警告，转储可能不一致）：int_prod { target { vars: 214 coeffs: 3249 offset: 3249 } exprs { vars: 212 coeffs: 570 offset: -102 } exprs { vars: 212 coeffs: 570 offset: -102 } }
预处理摘要：
- 检测到2个仿射关系。
- 规则'仿射：新关系'被应用了2次。
- 规则'int_prod：除以常数因子'被应用了2次。
- 规则'int_prod：通过常数线性化乘积'被应用了1140次。
- 规则'int_prod：删除常数表达式'被应用了1140次。
- 规则'int_square：减小目标域'被应用了2次。
- 规则'linear：使用仿射关系重新映射'被应用了1次。
- 规则'presolve：迭代'被应用了1次。
- 规则'variables：规范化仿射域'被应用了2次。
问题由预处理关闭。
CpSolverResponse摘要：
状态: 不可行
目标: 不适用
最佳界限: 不适用
整数: 0
布尔值: 0
冲突: 0
分支: 0
传播: 0
整数传播: 0
重启: 0
lp迭代: 0
墙上时间: 0.007945
用户时间: 0.007945
确定性时间: 0
gap_integral: 0
英文:
I am new to using or-tools and I have been tasked with minimizing a quadratic objective function with lots of IntVar variables. I don't know where to start breaking down what the problem could be concerning an infeasable model and welcome any tips to begin.
I've watched several videos about using or tools and experimented in a test file with a smaller scale but my main problem results in the infeasable model. The videos/experiments I've done have less variables which I am thinking is the issue but, again, this is my first time using OR-tools.
here is the output from when I run the model:
Starting CP-SAT solver v9.6.2534
Parameters: log_search_progress: true enumerate_all_solutions: true
Setting number of workers to 1
Initial optimization model '': (model_fingerprint: 0x8f376cd881ed44f1)
#Variables: 214 (#ints:1 in objective)
- 126 Booleans in [0,1]
- 2 in [-100000,100000]
- 84 in [0,96]
- 2 in [0,2000000]
#kIntProd: 4004
Starting presolve at 0.00s
Unsat after presolving constraint #1142 (warning, dump might be inconsistent): int_prod { target { vars: 214 coeffs: 3249 offset: 3249 } exprs { vars: 212 coeffs: 570 offset: -102 } exprs { vars: 212 coeffs: 570 offset: -102 } }
Presolve summary:
- 2 affine relations were detected.
- rule 'affine: new relation' was applied 2 times.
- rule 'int_prod: divide product by constant factor' was applied 2 times.
- rule 'int_prod: linearize product by constant.' was applied 1140 times.
- rule 'int_prod: removed constant expressions.' was applied 1140 times.
- rule 'int_square: reduced target domain.' was applied 2 times.
- rule 'linear: remapped using affine relations' was applied 1 time.
- rule 'presolve: iteration' was applied 1 time.
- rule 'variables: canonicalize affine domain' was applied 2 times.
Problem closed by presolve.
CpSolverResponse summary:
status: INFEASIBLE
objective: NA
best_bound: NA
integers: 0
booleans: 0
conflicts: 0
branches: 0
propagations: 0
integer_propagations: 0
restarts: 0
lp_iterations: 0
walltime: 0.007945
usertime: 0.007945
deterministic_time: 0
gap_integral: 0
答案1
得分: 3
我只有一些简单的建议：
- 如果这是一个参数，减小模型大小
- 在保持问题不可行的情况下移除所有约束
- 查看平方约束和相应的域
- 添加假设以检查数据的合理性（容量 >= 0，没有疯狂的值范围，...）
- 调整变量的域以扩大它们
- 注入已知的可行解并尝试找出它何处失败
英文:
I only have simple advices:
- reduce the model size if this is a parameter
- remove all constraints while keeping the problem infeasible
- look at the square constraints and the corresponding domains
- add assumptions to check the soundness of your data (capacity is >= 0, no crazy ranges of values, ...)
- play with the domain of the variables to enlarge them
- inject a known feasible solution and try to find where it breaks
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论