Questions tagged [constraint]
For questions related to constraints, i.e. any restriction or relation a set of decision variables has to satisfy.
288
questions
1
vote
0
answers
51
views
Solve a combinatorial problem under nested cardinality constraints
I am trying to solve the following optimization problem
\begin{align}
\underset{S_t \in \mathbb{S}}{\min} ~ \sum\limits_{S \subset S_t} f(S) \\
s.t. |S| = M,
\end{align}
where $\mathbb{S} := \{S \...
- 33
0
votes
1
answer
56
views
Difficult to understand the solution to the travelling salesman problem having Hamiltonian circuits with added length constraint
The travelling salesman problem has been solved in the below given video, but I didn't understand lower bound computed for the following paths.
I also didn't understand the why Path 8,9 10 and 11 ...
0
votes
0
answers
54
views
Problem in my optimization model (JuMP/Julia/Gurobi) where one variable refuses to go above 0
I am currently writing an Optimization Model which is meant to give advice to companies about the integration of a decentral energy system (it's for my bachelor's thesis, so nothing very complex). A ...
0
votes
3
answers
132
views
Constraint formulation
Let $P$ be the set of periods, with $y_p$ as a binary variable, and $w_{p}^{t}$ as a binary variable that links period $p$ with period $t$, where $p, t \in P$, and $t = p +2$.
The constraint I am ...
- 113
3
votes
2
answers
193
views
Conditional Constraint Formulation LP
I have a continuous variable $z, {-1 < z < 1},$ and a binary variable $w$.
How do I write a conditional constraint which guarantees for $z < 0$, $w = 1$,
and for $z \ge 0$, $w = 0$?
- 33
0
votes
2
answers
77
views
General questions concering column generation
I have a basic question about the Dantig-Wolfe reformulation. How do I know which constraints go into the master problem and which into the subproblem(s)? As I understand it, constraints that connect ...
1
vote
2
answers
81
views
Modification of a switch binary variable
I have the following question. I have just read this question and was wondering if it is possible to extend this problem. I am interested in whether it is also possible to identify which machine is ...
- 91
0
votes
0
answers
43
views
What's the linearization of the product between a discrete variable and a continuous varibale?
I am trying to linearize the product $z=xy$, where $x$ is an integer variable and $y$ a continuous variable, both non-negative, for an optimization problem. I have tried the SCIP formulation:
$v_{bn} \...
0
votes
0
answers
39
views
Mixed integer optimization: what if X has to be a rounded multiple of a fixed value? [duplicate]
I am working on a Mosek project. The utility function is to maximize
u^{t} x
where x is a vector of N
There is a tricky constraint: the first 3 items of X must be ...
- 489
1
vote
0
answers
44
views
How to force a bounded relationship to "become redundant" or "not needed"?
As an engineer who is currently working with some optimization problem I am currently running into a difficult reformulation problem. Here $a$ is a binary decision variable, $\phi \in [0,1]$ and $d$ ...
2
votes
1
answer
40
views
How to generate random bounded polytope by MATLAB defined by Ax=b, x≥0
How can one create a random bounded polytope in MATLAB, specified by the conditions
$\lbracex:~ Ax = b,~ x \geq 0\rbrace$
1
vote
0
answers
77
views
Solve scheduling model using a greedy heurisitc
I have the following scheduling problem. Relatively simple and not very complex (only serves as an example). The indexes are $I$ worker, $T$ days and $J$ shift. The decision variable is $x_{ijt}$, ...
- 71
0
votes
1
answer
79
views
Adopt constraint formulation
I have this constraint which ensures that there are at least $F$ consecutive days off. F.e. for $F=2$, an 1-0-1 is prevented.
$$1+y_{it}\ge y_{i(t-1)}+y_{ik}~\forall i\in I, t\in\left\{ 2,\ldots,T- {F}...
- 19
0
votes
1
answer
77
views
PULP: Optimization Assignment of Bicycle production per month
Q1. If bicycles of types A and H are produced, then bicycles of type C can be produced with 20% shorter working hours, while selling profit of bicycles type H can be 20% higher.
Q2: If bicycles of ...
0
votes
1
answer
75
views
Inconsistencies in modeling a binary variable that indicates a switch
this is a follow-up question to this post here and to @RobPratt's answer. I have implemented the whole thing, and now it happened that on day 1 the machine did not run and was only used for the first ...
- 89
0
votes
2
answers
106
views
Combine two constraints into one
I have these two constraints, where the indices are $i$ person, $j$ shift and $t$, the day. $x_{ijt}$ is the shift assignment, $m_{ijt}$ the motivation of the person in a shift (only takes values $m_{...
- 139
1
vote
1
answer
87
views
Schedule monotony constraints
Suppose I have a model for creating a nurse's duty roster. The model has the indices $i$ for the person, $t$ for the day and $s$ for the shift. I have the binary variable $x_{its}$ which indicates ...
0
votes
0
answers
48
views
Constraint formulation in MILP AGV Scheduling (using CPLEX)
I am currently working on a MILP formulation for optimizing AGV/AMR scheduling.
The model aims to optimize task scheduling across multiple missions using a limited set of resources. Parameters such as ...
- 1
0
votes
1
answer
76
views
Getting rid of Big-M notation
i have the following constraint using the Big-$M$ method and i was wondering if it is possible to formulate these constraints without Big-$M$. These are the constraints in question:
$$\sum_{j=1}^{t}z_{...
- 19
3
votes
1
answer
194
views
Reformulate constraints
I have the following constraints and am wondering whether I can formulate the whole thing more narrowly and with fewer constraints. $x_{itk}$ is binary and $u_{it}, v_{itk}\in [0,1]$. $M$ is a Big-M ...
0
votes
0
answers
31
views
0
votes
0
answers
107
views
Need Help for building two constraints in MIP model
Really need help for building two constraints with MIP model, I have written the required information and variable information on the diagram below.
The way I think of it now is to use two ...
- 113
0
votes
1
answer
47
views
Distinguishing between soft and hard constraints
I am currently setting up a nurse rostering model. In it, I have several regulatory constraints, such as limits on working days and so on. Apparently these are considered hard constraints. However, I ...
- 139
0
votes
2
answers
93
views
linearizing a constraint involving an absolute function
I would like to know what is the best way to linearize a constraint involving an absolute function. More precisely, imagine I have three binary variables and their relationships is as follows:
|x-y| = ...
- 97
2
votes
1
answer
104
views
Flow conservation constraints for an Open Vehicle Routing Problem
I'm currently reviewing literature on the Open Vehicle Routing Problem (Open VRP), which characterizes scenarios where trucks do not return to the depot after serving the last customer. In this ...
- 165
0
votes
1
answer
108
views
Exception from IBM ILOG CPLEX: CPLEX Error 5002: 'q1' is not convex.->
I am currently solving a scheduling optimization problem regarding the fleet management of AGV/AMR. I always get the same error and I don't know where to start to solve it. Here's the code snippet for ...
- 1
0
votes
0
answers
45
views
Projection of QP problem solved with Gradient Descent
Lets say we have a QP problem as shown below
$$\min {\bf x}^T {\bf R}{\bf x}+{\bf c}^T{\bf x}$$
subject to
$${\bf A_{eq}x}={\bf e}_{eq}$$
$${\bf Ax}\le {\bf e}$$
$${\bf x}\in \lbrace 0,1\rbrace$$
${\...
- 2,397
1
vote
0
answers
17
views
Does Theory of Constraints weigh in on marginal vs conditional bottlenecks?
I have a modelling project using a Kelly network.
An observation I have made is that the bottlenecks based on the marginal distributions of service times is not always the same as the bottlenecks ...
- 141
0
votes
0
answers
19
views
What notion of ordering is the important for identifying bottlenecks in Theory of Constraints?
In many systems the completion of an activity takes an amount of time that is not perfectly predictable. In statistics we would consider these to be random variables.
For two measurements of time $t_1$...
- 141
0
votes
0
answers
32
views
Theory of Contraints Technical Reference
I have dived into Theory of Constraints by reading The Goal, It's Not Luck, Isn't it Obvious, and Critical Chain. I am currently reading Goldratt's Rules of Flow.
While I enjoy these short novels, ...
- 141
1
vote
0
answers
45
views
What reasons would cause lazy constraints to degrade the performances when reoptimizing with a different objective?
We are currently solving a hard MILP problem on optimality. Once it has been solved, several times (from 5 to 10 times), we change one coefficient of the objective function and reoptimize. Thus the ...
- 819
0
votes
1
answer
84
views
Scheduling: Connecting the end and the beginning of the planning horizon
I would like to create a rota that repeats every 28 days and adheres to the usual rules. These include the minimum/maximum number of consecutive working days and the break days. I have created a model ...
- 81
2
votes
2
answers
124
views
Differentiability of solution of optimization problem with respect to constraint (properties, conditions etc)
Assume you have the following simple constrained optimization problem:
$$
\begin{equation}
\begin{split}
&\min_x f(x) \\
& s.t \quad g(x) = c
\end{split}
\end{equation}
$$
where $f,g$ are both ...
- 23
2
votes
1
answer
237
views
How to modify a model to be cyclic?
I have the following question. I have the following physician problem with the indices $I$ (doctor), $T$ (days) and $J$ (shifts). $x_{itj}$ is the decision variable, $d_{tj}$ is the demand and $g$ is ...
2
votes
2
answers
343
views
How to model weekend constraints in a nurse rostering problem?
I have the following problem. I have a Nurse rostering problem and want to model the following. I have the indices $D$ (days), $I$ (nurse), $S$ (shift). My planning period $D$ is 28 days. Now I want ...
- 71
3
votes
2
answers
381
views
How to set up a constraint that represents a median?
I'm trying to create an optimization problem where one of my constraints represents a median of another decision variable. Suppose I have decision variables $\bf{y}$ and $z$. My problem will look ...
- 145
1
vote
1
answer
89
views
Problems with Big-M Constraint
I have the following constraints for my roster optimisation problem:
\begin{align}
&(1-r_{i,t})\le \sum_{j=t-\chi}^{t-1}sc_{i,j}\quad &\forall i\in I, t\in \{1+\chi,\ldots,T\}
\end{align}
\...
- 81
0
votes
2
answers
177
views
Generalize working days constraints
I have the following constraints. The first ensures that in my shift plan there are always exactly two days off between blocks of working days and only then does the next block begin.
It reads as ...
- 81
0
votes
0
answers
54
views
Objective/Cost Function Normalization (MPC)
I am trying to develop an MPC. In this MPC, I predict the temperature and try to bring the sensor value to the desired setpoint temperature. I predict the temperature in the next 180 minutes for the ...
- 1
1
vote
2
answers
227
views
Which of these formulations has the tightest linear relaxation?
I have a sequence of binary variables $x_i$ and want to enforce consecutive $1$'s of length at least $3$. I have $2$ formulations:
Model $1$ (from here):
\begin{align}
x_i \le x_{i-1}+x_{i+1} \tag{1}\...
- 55
-1
votes
1
answer
71
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 an objective function $\underset{x}{\max} g(x)$.
I need to convert a continuous linear function $f(x)$...
- 11
0
votes
1
answer
81
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 ...
- 91
0
votes
2
answers
85
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
5
votes
1
answer
148
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-...
- 233
2
votes
1
answer
87
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
129
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}$ ...
- 113
0
votes
3
answers
699
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
191
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
424
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
281
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