Questions tagged [constraint]
For questions related to constraints, i.e. any restriction or relation a set of decision variables has to satisfy.
248
questions
0
votes
0
answers
3
views
MIP formulation for a lower semi-continuous function
How can I formulate in mixed linear programming (a set of constraints) the following issue.
I have a maximization function on x, g(x).
I need to convert a ...
- 1
0
votes
1
answer
45
views
Sum only over weekend days
I would like to adjust my constraint so that the x are only ever added for the weekend of a week, i.e. days 6,7 and then 13,14 and 20,21 etc.. That would be my previous formulation, but how can I ...
- 31
0
votes
2
answers
62
views
What is the best way to constrain a binary matrix so that at most one row has positive values?
I have a binary variable $x_{i,j}$ for $i\in\{1,\ldots,m\}$ and $j\in\{1,\ldots,n\}$ and the constraint is to have at most one row that has ones. I wrote this as: $$x_{i,j}+x_{i',j'}\leqslant1,\forall ...
- 101
4
votes
1
answer
73
views
How to identify constraints that are good candidates for being lazy constraints?
I am working on reducing the solving time of the optimization problem I am working on. One of the ideas I am exploring is the usage of Lazy constraints. As solver, I am using Gurobi, so both pre-...
- 223
2
votes
1
answer
68
views
Compute time between tasks
I am trying to solve an optimization problem in which there is a set of tasks, $S$, where $s_i$ and $e_i$ are the starting and ending time of task $i \in S$. Each task $i $ must be done within its own ...
1
vote
1
answer
108
views
How to linearize the following constraints
Given the following two expressions:
$ x - \frac{1}{T}\sum_{i} y_{i}$
$ x - \frac{1}{Q}\sum_{i} \beta_{i} y_{i}$
where $x \in \mathbb{Z}_{+}$, $y \in \mathbb{R}_{+}$, and $T$, $Q$ and $\beta_{i}$ ...
- 111
0
votes
2
answers
180
views
Starting with HiGHS
I have been messing about with HiGHS and trying to get a hang of its capability.
Here is an example of a simple model from their github repo
https://github.com/ERGO-Code/HiGHS/blob/master/examples/...
0
votes
1
answer
143
views
Production scheduling
I'm formulating a scheduling problem with the following decision variables:
$$X_t \space \text{is power sold to market in time period t} \\
Y_t \space \text{is power used for production in time period ...
1
vote
1
answer
303
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 chek whether the test point lies inside ...
- 33
1
vote
2
answers
221
views
How to properly tackle a big model using weak constraints
I'm currently working on a model that has a large number of variables (around 200k), and I don't know what the proper way to handle such a big problem is.
One suggestion I got is to use lazy ...
- 11
3
votes
0
answers
129
views
Which solvers provide an IIS feature?
I am well aware that commercial solvers CPLEX and GUROBI provide an IIS (irreducible infeasible set) feature. @batwing mentions FICO Xpress in the comment section as well, and @RobPratt mentions SAS.
...
- 12.9k
1
vote
1
answer
74
views
How to calculate the duration of a task in each shift?
I am solving a job scheduling problem with three shifts,
the duration of all shifts are assumed to be known (and might be equal):
The tasks can start from any shift
We know the duration of each task ...
- 1,275
0
votes
2
answers
35
views
Scheduling next shift such its not within X hours of previous shift
Hey i have this constraint that i am trying to code in python: "scheduling next shift such its not within X hours of previous shift"
Given that i have start, end time of each shift and the ...
2
votes
1
answer
108
views
How to select intermediate nodes in a network?
I have a network where nodes are connected as shown in the Figure .
Nodes 2 and 4 have a connection to the cloud node. I am writing constraints where at least one node with a connection to the cloud ...
- 81
1
vote
2
answers
149
views
Linearizing if else conditions in ILP
We are given three binary indicator variables $X_{ij}, Y_{jk}$ and $Z_{jl}$. Write linear constraints such that,
a) if $X_{ij}$ is equal to 1, then for that $j$ when $X_{ij} = 1$, exactly one $Y_{jk} =...
- 897
4
votes
2
answers
1k
views
Which solvers should I use to solve large, but extremely sparse LP problems with 100-500 thousand variables?
I would like to solve the following type of LP problems:
where M and N are very large numbers, they are on the order of a few hundreds of thousands and tens of thousands, respectively.
As is clear ...
- 143
2
votes
1
answer
70
views
Question About Fritz John Theorem and Slater Constraint Qualification
Background Information
I am studying constraint qualifications. Here are two theorems leading to my question:
Theorem 1$\space\space\space\space$ [Fritz John Theorem] Suppose that $f, g_1, \dots, g_k$...
- 123
1
vote
1
answer
50
views
Is there any literature on constrained nonlinear optimization where constraint returns have to be queried from an oracle?
I am looking at literature considering constrained optimization problems of the form:
$\min_{x\in X\subseteq R^n} f(x), \text{ subject to } g_{oracle}(x) \leq 0$
The optimization algorithm doesn't ...
- 13
2
votes
1
answer
207
views
Compute overlapping time
I am trying to solve an optimization problem in which there is a set of tasks, $S$, where $s_i$ and $e_i$ are the starting and ending time of task $i \in S$. Each task $i $ must be done within its ...
2
votes
1
answer
145
views
SET game: how to generate all sets with a MIP?
I am playing around with the game called Set:
In the game, certain combinations of three cards are said to make up a
"set". For each one of the four categories of features — color,
number, ...
- 29
1
vote
0
answers
24
views
Nesterov Acceleration in Proximal Iteration with Strictly Positive Variable?
I have a cost function of the form $f(x) - \log(x)$, where $f$ is some smooth function mapping $\mathbb{R}^n_+\to\mathbb{R}$and $x$ is restricted to be nonnegative by the problem constraints (and for ...
- 111
1
vote
1
answer
100
views
Constraints to avoid disjointed solutions in a MIP
Given an directed graph $G= (N,E)$, where $N$ is the set of nodes and $E$ is the set of all edges, each associated with a direction. $G$ is a connected graph but not necessarily a complete graph.
A ...
- 111
1
vote
3
answers
201
views
MIP constraints with chronological ordering
I am using a MIP formulation to decide which dates and locations (i.e. stops) should be chosen for a route that maximizes the total revenue over all chosen stops. My decision variable $X$ is the ...
- 35
7
votes
1
answer
612
views
How can one model a binary variable?
I am looking for the formulation of a constraint that does the following. I want to introduce a new binary variable $\kappa_{it}$ that takes the value 1 if the sum of the other binary variable $\...
- 121
-1
votes
1
answer
65
views
Literature for the Big-M constraint method
I've come across the possibility of introducing binary variables in linear programming with the Big-M method here several times now. Here is an example:
\begin{align}
&(1-x_{i})\le \sum_i y_i\\
&...
0
votes
1
answer
181
views
LP - How to model binary variable that indicates a switch
I have the following question / concern. I have a modeling problem with the decision variable $d_{ptm}$ which indicates whether product $p$ was serviced by machine $m$ in period $t$. It takes the ...
2
votes
1
answer
59
views
epigraphs for quadratic constraints
I have a constraint of the following form
\begin{equation}
x^{\top}x + y^{\top}y \leq t
\end{equation}
where x, y are vector variables and t is a scalar variable. I can augment the variables x and y, ...
- 153
1
vote
1
answer
40
views
How to sum over periods till Period t?
I am trying to set up a constraint that does the following. I a binary variable $p_{it}$ that indicates whether a student $i$ passed the test in $t$. 1 if yes and 0 if no. Now I want to set up a ...
- 121
0
votes
1
answer
52
views
Help finding linear constraint - LP
I have the following question. I have two variables $w_{nds}$ and $m_{nd}$. The first variable indicates whether a nurse $n$ works shift $s$ on day $d$. The second one indicates the motivation of ...
- 121
1
vote
3
answers
112
views
How to linearize a chain of if-then constraints?
How can I express the process of converting a series of if-then constraints into a linear form?
Let's assume that we have integer variable $x_i$, non-negative variables $y_i^d$, and binary variables $\...
- 177
4
votes
2
answers
384
views
union of constraints
How to solve problems like $\min_x f(x) \\ g(x) < 0 \ or \ h(x)<0$?
I think we can solve $\min_x f(x) \\ g(x) < 0 $ and $\min_x f(x) \\ h(x) < 0 $, then we compare the solutions from these ...
- 43
1
vote
2
answers
82
views
Grouping variables to take same value
Assume we have 50 variables that we want to split into 3 groups and each group should have at least 5 variables. How to formulate that all variables in the same group take the same values? I used the ...
- 21
1
vote
2
answers
162
views
how to satisfy time constraints with meeting points?
I have a specific pickup and delivery problem to work on and am thinking how to incorporate time windows effectively. The problem has some driver with some time window [$a_d, b_d$] which is the start ...
- 33
3
votes
0
answers
68
views
constrained optimization with decreasing constraint thresholds -Literature tips
consider a constrained optimization problem (typically c=0), with f highly nonlinear:
\begin{equation}
\text{minimize}_x f(x) \\\\ s.t \ \ \ \ g(x) \leq c
\end{equation}
I experimented a bit and found ...
2
votes
1
answer
215
views
it is possible to have a constraint that does not contain any decision variables
I had formulated an optimization model, and along the way I had to change a variable into a parameter. In doing so, one of my constraints that contained the variable I changed no longer contained a ...
- 23
1
vote
1
answer
119
views
Sigmoidal programming
I plan to use sigmoidal programming from the git repo https://github.com/madeleineudell/SigmoidalProgramming.jl
There are some issues with the implementation of this repo. It requires me to pass $A, b,...
- 57
3
votes
2
answers
371
views
How to model this binary constraint?
I have an optimization problem that has a variable in the matrix form. The variable is a binary matrix. It has size $M \times N = 10 \times 50$ where $M$ is the number of machines and $N$ is the ...
2
votes
2
answers
373
views
Representing "and"/"or" relationships into constraints
How do I represent the following constraints in terms of equations?
For each i, either (1) holds or (2) holds-
$$
x_{1}^i \geq x_{2}^i \quad and \quad x_{3}^i \geq x_{4}^i \quad {(1)}
$$
$$
x_{1}^i \...
- 77
3
votes
3
answers
248
views
Equivalence between constraints in ILP
Let's have binary variables $x$ and $y$. I'd like to define a helping binary variable $z$ such that
$$ z = 1 \; \;\; \mathrm{iff} \; \; \; x + y = 2.$$
If I wanted to express the equivalence between ...
- 133
1
vote
1
answer
160
views
Linearize conditional constraint
Consider a variable c from the domain {-1,0,1}. I have the following constraint:
IF $c = 1 \Rightarrow x = 1 $ ELSE $x = 0$
How do I linearize this constraint?
- 19
1
vote
0
answers
78
views
How to speed up state of charge constraint in Pyomo model
Context: I am working on a small electricity market model in Pyomo. It optimizes the capacity of different technologies and generation in at least 43800 hours. One of the technologies is a battery. ...
- 11
2
votes
2
answers
58
views
How to restrict the amount of consecutive assignments
I'm working on a scheduling/rostering problem. In this scenario the shifts are predefined with a starting and ending date and time.
The problem basically assigns people to shifts with a binary ...
- 169
0
votes
1
answer
64
views
Maximization problem with preferences on variables
Consider the following trivial, theoretical model:
$$
\max x+2y+3z \qquad s.t.
$$
$$
x \leq b_x
$$
$$
y \leq b_y
$$
$$
z \leq b_z
$$
$$
x+y+z = 1
$$
$$
x,y,z \in \{0, 1\}
$$
and $b_x$, $b_y$ and $b_z$ ...
- 937
1
vote
1
answer
76
views
Multiplicity-Constraint in Constraint Programming Solvers
I need to solve a CSP with a constraint imposing upper bounds on the multiplicity of variables in a list.
More precisely, I need a constraint of the form
...
- 113
0
votes
1
answer
96
views
Meaning difference between SUMMATION and not in the MIP model
I'm asking you a question because I was confused about MIP while reading the paper.
This paper is about dual crane optimization.
In the MIP model of the paper, equations (7) and (8) are used to model ...
- 1
2
votes
3
answers
143
views
Efficient formulation of flexible job-shop scheduling constraints
I am working on a flexible job-shop scheduling problem, where indices are as follows:
$i$: Index of operations
$j$: Index of jobs
$m$: Index of machines
$p$: Index of operation sequences on a machine
...
- 573
4
votes
2
answers
221
views
how to ensure minimum output of a generator (else zero output) in linear programming?
I want to ensure, that a generator (in my case a heat generator, for example a boiler) first starts to output thermal energy, when a certain minimum output can be realized. Otherwise the output should ...
- 293
3
votes
3
answers
298
views
Set null the next set of N values
I'm dealing with a problem I already modelled by using linear programming. The already existing constraints set at 1 groups of contiguous variables (for ex: ...
- 33
3
votes
2
answers
453
views
Binary integer programming with dynamic costs and total resource constraint
I am trying to find a suitable paradigm under which my discrete optimisation problem falls into. This looks similar to integer programming, so the goal is to find a binary vector $\bar{x}$. However, ...
- 133
2
votes
1
answer
103
views
Prove MF-Constraint Qualification but not LICQ is satisfied
Let $g_1(x):=(x_1-1)^2+(x_2-1)^2-2\leq 0, g_2(x):=(x_1-1)^2+(x_2+1)^2-2\leq 0, g_3(x):=-x_1\leq 0$ be given constraints. Show that the Mangasarian-Fromovitz Constraint Qualification (MFCQ) is ...
- 123