Questions tagged [constraint-programming]
Constraint programming is a particular form of optimization modeling that tends to be well-suited for combinatorial models like scheduling and planning.
164
questions
0
votes
1
answer
29
views
How to extend the $p \Rightarrow q$ constraint with logical AND within the $p$ statement for Big-M method?
I am a network engineer who is currently doing some network optimization problem. In my application, there is a requirement for the network delay to be bounded in some interval once some boolean flag ...
0
votes
1
answer
49
views
Single Machine Job Scheduling With Release Dates and No Idling Constraint
I'm trying to model a linear job scheduling optimisation problem. There is a single machine and N jobs $J_1, J_2, ..., J_N$. Each job consists of one step with processing time $p_1, p_2, ..., p_N$. ...
1
vote
0
answers
107
views
A Mathematical Approach to Solving a Sudoku Puzzle
I've been trying to develop the most efficient algorithm to solve a Sudoku puzzle. The one that I've developed isn't able to solve certain kinds of puzzles without having to use backtracking. One such ...
- 11
1
vote
0
answers
65
views
Optimization/Constraint Solving on Graphs
I play video games, and it sounded like a fun exercise to try to find the optimal order in which to complete quests:
There exist multiple quest trees
There are some quests with inter-dependencies ...
- 111
2
votes
0
answers
65
views
Weighted Least Square with infinite weights
I am considering a weighted least square problem with data $X \in \mathbb{R}^{n \times p}$, (diagonal) weight matrix $W \in \mathbb{R}^{n \times n}$ and responses $y \in \mathbb{R}^n$, i.e. finding $$\...
- 21
0
votes
2
answers
66
views
Constraint optimisation of an objective function
I have below objective function
$S = \lvert 18 - a - b \rvert + \lvert 15 - a - 2b \rvert + \lvert 11.1 - a - 3b \rvert + \lvert 7 - a - 4b \rvert + \lvert 3.4 - a - 5b \rvert + \lvert -1.5 - a - 6b \...
- 196
2
votes
0
answers
25
views
A function optimization problem with constraints
Let a, b, c be three real number constants satisfying $a^2 + b^2 + c^2 \leq 1$. Define the function $f(x, y, z) = \frac{x^2 + y^2}{2(1+z)}$ under the constraints $(x-a)^2 + (y-b)^2 + (z-c)^2 \leq \mu^...
- 21
0
votes
1
answer
35
views
Constraint forcing maximum parameter value to constant
I have an optimisation problem that I thought should be in the form,
\begin{align}
\mathrm{maximise}_{x\in\mathbb{R}^p} & f(x) + \lambda\|x\|_1 \\
\mathrm{subject~to~~~~~~~} ...
- 339
2
votes
1
answer
33
views
Summations and constraints over sets in ILP problem
In a simplified version of the ILP problem I am trying to formulate, I have the following:
A set of elements $A_{i,j} \in \mathcal{A}$.
Each element $A_{i,j} \in \mathcal{A}$ has an associated ...
- 99
1
vote
0
answers
44
views
Relaxing a binary variable in a Mix Integer Programming problem
I am quite new to the field of optimization and currently having a problem of formulating a constraint with binary variable.
For each value of $b$, if there exists one value of k such that $z_1[b, k]$ ...
- 11
3
votes
1
answer
56
views
Demonstrating Piecewise Linearity in a Parametrized Optimization Solution
Let $\mathbf{B}$ be a definite positive square matrix of size $n \times n$, and $\mathbf{b}$ an $n$-sized vector. It can be shown that the solution of $\arg\min_x \left(\mathbf{x}^T \mathbf{B} \mathbf{...
- 33
0
votes
1
answer
77
views
Placing numbers of 1-9 so that the six equations hold
Place the numbers 1 to 9 into the nine positions in such a way that, the 6 equations are valid. Each position must have a distinct value. Multiplication and division have priority over addition and ...
- 13
0
votes
0
answers
73
views
Discrete point inside a polygon formed by set of vertices
I am working on a problem where I have a set of 2D vertices and a test point. I want to check whether the test point lies inside the polygon formed by the set of given vertices. I am trying to model ...
- 21
1
vote
2
answers
103
views
Polynomial constraints for restricting: $a=0$ if and only if $b\neq 0$
For this discussion, I will be considering polynomials over multiple complex variables, and a system of polynomial constraints, where the constraints on the variables can be written as a set of ...
- 890
3
votes
1
answer
125
views
Social golfer problem with additional requirement
I need to write a program that sorts people into groups.
To give a little context: The aim of the program is to create an equitable distribution of tasks and people for a school trip. Every day the ...
1
vote
1
answer
46
views
Formulating a particular constraint
I have a problem setting similar to bin packing but not exactly. I have to put the few boxes of certain dimensions in a square area besides each other. Like a grid. The boxes should be placed around ...
- 21
2
votes
5
answers
197
views
Do perfect squared rectangles with corners of sizes 10, 12 and 13 exist?
A squared rectangle is a rectangle dissected into squares.
squared rectangles are called perfect if the squares in the tiling are all of different sizes and are positive integers.
The smallest perfect ...
- 101
1
vote
0
answers
120
views
A combinatorial problem with coins
I am stuck at a mixture of a combinatorial and maximization problem and don't know how to proceed. Hopefully someone has an idea that can bring me further.
Imagine that we have a sequence of $n$ coins....
- 41
0
votes
1
answer
24
views
Quadratic cost minimization with zero mean constraint
Given an arbitrary vector $\mathbf{y}\in \mathbb{R}^{n}$, I would like to find $\mathbf{x^*} \in \mathbb{R}^n$ which is
$$ \text{argmin}_\mathbf{x} \|\mathbf{x}-\mathbf{y} \|_F^2$$
s.t.
$$ \mathbf{x}\...
- 545
4
votes
2
answers
784
views
Creation/computation of "Two not touch" puzzles
This is a mathematical and algorithmic question, so I hope it is not flagged for failing to be a pure mathematical question.
The puzzle "Two not touch" (or Star Battle) consists of a $10 \...
- 30k
3
votes
3
answers
228
views
Is it possible to find all integer solutions to this system of equations, inequalities and inequations?
Given the following three equations, assuming all unknowns are integers:
$$
x y =\left(x + y - z \right) a
\\
x z =\left(x + z - y \right) b
\\
y z =\left(y + z - x \right) c
$$
And the ...
- 796
0
votes
2
answers
42
views
writing a constraint for a maximisation problem [closed]
There are $n$ seats in a row. $p$ people (where $p<n$) can seat anywhere as long as long as they sit at least one seat apart due to personal relationships.
This statement is part of a larger ...
- 1,870
1
vote
0
answers
113
views
solution of $(A+\lambda{W})x=b$
Trying to solve system $(A+\lambda{W})x=b$ (derived from the method of Lagrange multipliers)
where $\lambda \in \mathbb{R}$ - the Lagrange multiplier. $A$ - symmetric non-singular matrix. $W$ - ...
- 11
0
votes
0
answers
141
views
Quadratic optimization problem where the variable is a binary matrix.
I have the following optimization problem that I want to solve (note that the $X$ variable consists of a binary matrix subject to a single constraint).
First, some definitions:
My $X$ variable:
$$
X = ...
- 158
4
votes
1
answer
163
views
What Is The Most Efficient Way To Tile A Page With Cube Nets?
I'm trying to print out nets of a cube on a sheet of paper, and I'm hoping to fit as many as I can on single sheets. The squares that make up the net are $\frac{1}{2}$ an inch wide, and I'm printing ...
- 75
1
vote
1
answer
83
views
How to formulate the following constraint in OPL (or mathematical program)?
(Originally posted here https://stackoverflow.com/q/72687231/10291218)
Suppose I have an integer array A of size n with two ...
- 333
1
vote
0
answers
30
views
A CSP on bit vector operations
I've got a CSP which is based on constraining bit vector variables. It is explained below through an example, followed by the full definition. So, what I'm concerned about is if you have some idea if ...
1
vote
1
answer
49
views
$l_1$ and $l_2$ norm minimization with a constraint
While working on the algorithm, I need to solve the following problem
$$ \min_{x \in \mathbb{R}^n} \| x \|_1 + \frac{\alpha}{2}\| x - y \|^2 \\ \mathrm{s.t.} \ \| x - s \|^2 \le r$$
where $y,s \in \...
- 11
1
vote
1
answer
157
views
Trouble about first order optimality conditions for programming problems with equality constraint.
I am having trouble understanding the following question.
Question. Take the following non-linear programming problem.
\begin{equation*}
\min f(x_1,x_2,x_3) = x_1^2-3x_1x_2+x_2^2+x_3^2 \\[.15cm]
\text{...
- 1,151
0
votes
0
answers
88
views
Finding a binary vector that satisfies non-linear constraints
I’m looking for good heuristics for finding at least one (of a probably large set, although possibly none) high dimensional ($|v|>5000$) binary vector that satisfies a set of non-linear/non-...
- 176
1
vote
0
answers
47
views
How to prove $-\ln(1-\|x\|^2)$ is self-concordant function?
I'm trying to prove $-\ln(1-\|x\|^2_2)$ is self-concordant function.
I think 1-dim case is easy to prove, but I cannot prove multi-dim cases. It's really hard to use definition because heavy Hessian. ...
- 31
1
vote
1
answer
90
views
Qubo: Energy of of Non Overlapping Constraint in Taillard's Job Shop Problem
Suppose we have a set of tasks $T = \{t_1, t_2, \dots, t_n\}$ with durations $\{d(t)| t \in T\}$, that need to be executed on some machine such that their execution times do not overlap.
We can ...
- 33
0
votes
1
answer
57
views
Find a minimum threshold value for a constraint [closed]
I want to find a minimum threshold value for a constraint, such that if this constraint is satisfied, the next one must be satisfied.
For example, given two inequations $f_1(X)\geq a$ and $f_2(X) \geq ...
- 11
1
vote
1
answer
965
views
How to write the following if-then condition in Mixed Integer Programming? If a<b then c=1, 0 otherwise
I am new to mixed-integer programming and I am confused about how to approach this if-then condition.
How do I the following constraint in mixed-integer programming:
if Dm +t < Dn + then Zmn=1, 0 ...
0
votes
1
answer
55
views
Finding constraints on right-hand side to yield feasible constrained linear problem
I have the following constrained linear system:
$$
Ax = y \\
Cx \ge b
$$
where
$$
y\in \mathbb{R}^3 \\
x \in \mathbb{R}^n \\
b \in \mathbb{R}^m \\
$$
Also, $n$ and $m$ are typically greater than 3, e....
- 101
0
votes
1
answer
475
views
Defining Constraints for the CSP of Skyscraper puzzle
The Skyscraper puzzle has the goal of positioning Skyscrapers of $n$ different heights on an $n \times n$-Field so that the following requirements are met:
Every field contains a skyscraper.
All ...
0
votes
1
answer
183
views
Difference between optimisation on manifolds and Lagrange multipliers
I have few reference I'm currently reading through but I still don't quite get the difference between optimising a function over a manifold and simply use constrained optimisation.
Do the algorithms ...
- 5,377
0
votes
1
answer
74
views
Solution to quadratically constrained binary integer program
I'm trying to solve a problem for $x$ which is a vector of length $n$ with only binary elements, i.e. each $x_{i}$ is either $0$ or $1$.
There are two constraints on $x$, one quadratic and one linear:
...
- 317
1
vote
1
answer
79
views
constraints on portfolio optimization problem
Let $x_j$ denote the ratio of assets to allocate to investment option $j$, where $j=1,...,n$
Let $c_j$ denote the annual expected rate of return on investment option $j$
How do we write the following ...
- 165
2
votes
0
answers
334
views
What is the advantage of the augmented Lagrange method compared to the quadratic penalty method and the method of Lagrange multipliers?
p.s. I already know few things, but it is interesting to listen to different perspectives.
what I know: the augmented Lagrange method combines the penalty method and the method of Lagrange multipliers....
user830472
0
votes
1
answer
46
views
Regression/forecast with an added linear constraint
I am not sure if I am asking on the right place.
But given a set of independent variables $X_i$ and the dependent variable $Y_i = f(X_i, b) +c$, how can I estimate the regression equation given a set ...
- 4,954
0
votes
0
answers
640
views
Conditions for uniqueness of solution of dual
Consider the following linear programming (hereafter, problem [1])
$$
\max_{y\in \mathbb{R}^J}c'y\\
\text{s.t. } b_t' y \leq a_t \text{ }\forall t\in \{1,...,T\}
$$
where $c$ is a $J\times 1$ vector ...
- 278
0
votes
1
answer
60
views
Safe packing Constraint satisfaction problem - is it optimal?
Problem:
You need to pack several items into your shopping bag without squashing anything. The items are to be placed one on top of the other. Each item has a weight and a strength, defined as the ...
0
votes
1
answer
25
views
Looking for an analytical function with f(n) = 1 with x=1 and f(n)=a otherwise.
I am looking for a analytical function that applies to the constraints:
\begin{equation}f(x) = \begin{cases}1 \text{ if } x=1 \\ \alpha \text{ otherwise }\end{cases}, \text{where } 0 \leq \alpha \leq ...
- 11
0
votes
1
answer
217
views
How to model grouping constraint in Knapsack problem?
I would like to add a new constraint to a standard Knapsack problem by introducing groups.
My variables are $x_c \in \mathbb{Z}^+, c\in \mathbb{C}$. Where $\mathbb{C}$ is the set of all items. Each ...
- 17
0
votes
1
answer
29
views
Approach to managing decreasing set of interconnected numbers
We have four variables:
a, which represents numbers from 0-999
b, which represents a1000 (<...
- 113
2
votes
1
answer
60
views
Question on Donoho's 2006 "Compressive sensing" paper
In that paper on page 8, he wrote the classical compressive sensing problem as
$$\min_{\theta} \lVert \theta \rVert_1, s.t. \Phi \theta = y$$
can be reformulated as a linear programming problem
$$\...
0
votes
1
answer
242
views
Constraining linear program with binary variable such that one dimension must be subset of its set
I have a linear program and struggling with a particular constraint requirement. I am hoping there is a way for timely execution via linear construction.
Here is the formula thus far:
Objective ...
- 115
0
votes
1
answer
296
views
How to solve simultaneous linear equations with constraints?
Given:
$$Ax=b$$
$$A = \begin{pmatrix}
1&1&1&1&1&1&1&1&1&1&1&1\\
1&1&0&1&1&1&0&0&0&0&0&0\\
0&0&1&1&...
- 113
1
vote
0
answers
227
views
How can I determine the lower and upper bounds in an easy way? Constrainted optimization
This is a simple question, but I'm not sure how to solve it!
Assume that we have a vector $x$ and we want $x$ to have some upper and lower limits.
$lb <= x <= ub$
Where $lb$ stands for lower ...
- 2,962