The 2024 Developer Survey results are live! See the results

Questions tagged [constraint-programming]

The tag has no usage guidance.

76 questions
Filter by
Sorted by
Tagged with
1 vote
56 views

Is there a linear programming method that is polynomial in the number of variables, constraints and bitlength of numbers?

AFAIK, Interior Point method for solving a system of linear inequations is polynomial in the number of variables and constraints. Probably there are others. I don't need to optimize any function (...
40 views

Guarantee the solvability of conditional, but cyclic dependencies

I have a bunch of values, some that are given by an end user input and some that are calculated based on that input. The way that the values are calculated are input by a different group of users of ...
1 vote
34 views

Understanding Arc Consistency 4 in the context of Wave Function Collapse

Following this blog post about the Arc Consistency algorithms. Namely, the explanation on AC4. Consider the following example: If I understand AC problems correctly. Then: We have two known ...
• 111
28 views

How can I model this optimization problem?

We're looking to model the following problem as a standard optimization problem (or even a non-standard one). We can come close, but nothing seems to fit exactly. We have a working algorithm coded, ...
• 133
26 views

Placement of Tasks from Dataflow Graph on a Physical Graph

I have a dataflow graph where a set of different types of tasks are placed in corresponding types of nodes. Say the task types are called A, B, and C. A-type tasks are placed in all the leaf nodes of ...
• 1
19 views

Optimize clothing in RPG considering set bonuses

In role playing games, switching equipment for better is a common procedure. My question is to find an algorithm that can optimize linear combination of stats the equipped gear gives - this is exactly ...
113 views

Solving constrained optimization problem using PyTorch: Minimizing L1 norm of $\vec{x}$ subject to $\vec{x} = \mathbb{A^{-1}}\vec{y}$

My goal is to solve the above-constrained minimization problem where my vector to be optimized is x. The matrix A and the vector ...
1 vote
62 views

Encoding "all-except" constraints in CNF

I am looking for an efficient CNF encoding of the following situation: I have sets of boolean literals $A = \{ a_1, \ldots, a_m \}$, $B = \{ b_1,\ldots, b_n \}$ and subsets $B_1, \ldots, B_m$, where ...
• 166
81 views

• 113
993 views

Which AC-3 algorithm is being used here?

This is the illustration of the AC-3 algorithm for four queens from exhaustive study of essential constraint satisfaction problem techniques based on N-Queens problem by Md. Ahsan Ayub, Kazi A Kalpoma,...
• 53
1 vote
75 views

A Quadratically-Constrainted Quadratic Program consists of optimizing a quadratic objective function while imposing quadratic constraints, which can be inequalities or equalities. Obviously, ...
• 945
1 vote
86 views

Finding infeasible sets of constraints (CSP)

Given a set of constraints, I want to check whether the constraints are feasible. What I am trying now, is to feed the constraints to a solver and check if the solver returns infeasible. I am using ...
• 307
1 vote
203 views

(M)ILP overlap of two intervals

I got an ILP Model where $c_i$ represents the starting time for a visit$_i$. $c_i$ is already constraint by a number of constraints, one is $c_i > 0$. I have now outside of my model 0 or multiple ...
• 113
273 views

Conditional milp formulation

I have two binaries, $\alpha_{ts,it}$ and $\alpha_{ts,gshp} \in \{0,1\}$, and two reals $T_{it}$ and $T_{ts}$ which have upper and lower bounds. How can I model $\alpha_{ts,it}=1$ if the following ...
• 1
1 vote
145 views

Algorithm to solve constraint satisfaction problems

I have group of people. Each person can be described by few characteristics: age, occupation, city, favorite_color I would like to generate 60 random people and ...
• 113
1 vote
59 views

Can somebody suggest what is wrong with these constraint? [closed]

I have written two constraints for Mixed integer linear problem. I am working on the scheduling problem i.e., Scheduling of hybrid appliances. For example, the washing machine is appliance indicated ...
• 123
1 vote
57 views

How to create constraints for Mixed integer linear problem?

i am a beginner to Discrete optimization domain. I am working on the real world problem, i.e., Scheduling of hybrid appliances. I have hybrid appliances which can ...
• 123
172 views

How do you proceed if your milp is not solvable

We are currently developing an ilp/milp model to fit the best routes with given resources (people) in a given timeframe and given visits and costs to travel from one visit to another (asymetrical). ...
• 113
1 vote
152 views

Shift Organization algorithms (Constraint Programming + Marriage problem)

I want to assign people to cover shifts considering a set of constraints and preferences. Here's the problem definition: Daily shifts must be covered by workers, who are divided in three groups: ...
• 121
176 views

Constraint Satisfaction: maximizing total value with no overlaps

Suppose we have a bunch of bars, which can represent anything (time slots, paths, physical items...) and each of them has a start point, an end point, and an associated value. Out of all the bars ...
• 203
1 vote
49 views

• 41
253 views

How to encode a sequence of non-decreasing integers with an integer without redundancy, loops, and recursions

How to encode a sequence of n non-decreasing integer of [0, ..., m] fulfilling the following conditions: no or minimal redundancy only use 1 integer variable or k independent integer variables with a ...
78 views

(Historical perspective) CSP and SAT inter-fertilization

[Disclaimer: this is a rather specialized question] It is known that techniques like Conflict-Driven Clause Learning (CDCL) and back-jumping -- which improved the Satisfiability (SAT) strategies ...
• 141
68 views

Using Genetic Algorithms for volatile problems

Suppose I am looking at an optimization problem with a large number of interconnected constraints, but the solution is - in some regions - extremely volatile (With volatile I mean: small mutations ...
• 101