Questions tagged [constraint]
For questions related to constraints, i.e. any restriction or relation a set of decision variables has to satisfy.
43
questions
4
votes
1answer
131 views
How to model shipment size constraint?
I am working on an LP problem where I have to model a constraint as:
"The total number of units of product A and B should be shipped in multiples of $1200$"
e.g. $700\text{(product A)} + 500\text{(...
5
votes
1answer
368 views
Single KKT solution for a simple problem: proof of being minimizer
I have a very simple problem:
$$ \begin{align*}
\begin{array}{ll}
\min\limits_{x_1,x_2} & -x_1x_2 \\
\text{s.t.} & x_1 + x_2 - 2 = 0.
\end{array}
\end{align*} $$
The KKT system gives me $x_1^*...
5
votes
2answers
441 views
Integer programming problem
I have the following exercise:
Stockco is considering four investments. Investment 1 will yield a net present value (NPV) of \$16,000; investment 2, an NPV of \$22,000; investment 3, an NPV of \$12,...
7
votes
2answers
163 views
shadow prices associated with nonnegativity constraints
Why are shadow prices associated with nonnegativity constraints also called as reduced costs, even if they have the same interpretation as shadow prices associated with an optimal solution? Why the ...
12
votes
3answers
653 views
Does it make sense to use strict equality constraint in optimization?
Once I learned from some post that the strict equality constraint in optimization problem does not make much sense. We should always use $\le$ constraint.
How far this is true.
If I must have a ...
5
votes
1answer
75 views
Precedence constraints using binary variables - DOCPLEX
I would like to establish a precedence constraint to ensure the precedence relation of tasks. I have a set of tasks available, but required tasks are not always the same. It means, the tasks executed ...
7
votes
2answers
116 views
Linear constraint formulation (OR-statement)
I have the decision variable $X_{iz}$
And I have two parameters $T_i\in\{0,1\}$ and $IT_z\in\{0,1,2\}$. I can only assign $i$ to $z$ if the following holds:
for $T_i=0$, $IT_z$ needs to be $0$ or $2$...
10
votes
2answers
119 views
Linearization $\max(c_1 x_2, c_2 x_2, \ldots, c_nx_n) \geq q$ constraint
I have a MIP minimization problem where I have a maximization in the constraints:
$$\max(c_1x_2,\, c_2x_2,\, \ldots,\, c_nx_n) \geq q$$
Where:
$c_n$ constants
$x_n$ binary variables
$q$ constant
$...
9
votes
1answer
211 views
Linear programming with if-then-else (big-M)
I am trying to formulate the following in linear programming.
\begin{cases}\text{if}\,\,a>b\,\,\text{then}\,\,c=a\\\text{else}\,\,c=b.\end{cases}
I tried some things with big $M$, like $$a + my &...
11
votes
1answer
117 views
Example satisfying Mangasarian-Fromovitz CQ but not LICQ
On Wikipedia's page for the KKT conditions, it is stated that Mangasarian-Fromovitz constraint qualification (MFCQ) is weaker than linear independent constraint qualification (LICQ). What is a ...
8
votes
1answer
102 views
Minizinc: How to use a predicate in an assert statement?
Trying to use minizinc builtins to do some basic validation of data inputs but I get a type error ...
12
votes
1answer
167 views
Which ML algorithms work by solving constrained optimisation problems?
As far as I know, most machine learning algorithms solve unconstrained optimisation problems, i.e., if we were to unroll all the neurons into symbolic expressions we would end up with a massive ...
12
votes
1answer
154 views
If-then constraints in MIP programming
For continuous variables $x$ and $y$, the constraints are:
...
13
votes
2answers
885 views
Is This Constraint Convex?
I have a constraint that I believe to be convex and not affine which I think means that I can implement a relaxation. I will first define the full constraint, and then build up my (informal) reasoning ...
6
votes
1answer
56 views
Optimal resource allocation - 3 step process
I have a 3 step process. Step A takes 20 min, Step B : 60 min, Step C : 20 min
Steps in production of output "news nuggets" is as below:
Step A : Do Secondary Research
Step B : Analyse the data, ...
6
votes
1answer
127 views
How To Linearize $X = \max\{x_1,x_2\}$
I am new to thinking about math programming and I have a particular constraint I am hoping to reformulate, I just don't know the proper mathematical translation for what I am hoping to do. Enforcing ...
9
votes
1answer
92 views
Constraint to state the relation between 2 binary variables
I'm trying to deal with a process planning and machine layout allocation simultaneously.
I have the following variables:
$X_p{_w}_{cj}=1$ if an operation $p$ is done by a machine $w$ with a ...
8
votes
2answers
270 views
How to linearize a constraint with max
I would like to linearize a constraint with max. I have the following constraint:
$$\max_{pcj}X_{pwcj}\leqslant L_{wk}.$$
With this constraint, I would like to ensure that for $\forall w \in W$, no ...
8
votes
3answers
127 views
Difference between “Optimization” and “Constrained Optimization”?
(Another OR noob question)
As I'm trying to learn about OR and Optimization methods for work, I'm having a hard time understanding the difference between "Optimization" and "Constrained Optimization"...
7
votes
2answers
123 views
Common structures in Gurobi - Python
I'm new to Gurobi in Python and I was wondering if someone knows how to code some common structures of linear constraints. I'm trying to understand how you'll code something like the following ...
8
votes
2answers
340 views
What is the standard practice in Constraint Programming modeling?
I know some general concepts regarding Constraint Programming (e.g., the ones explained in this answer). I am interested in learning how to formulate a combinatorial optimisation problem as a ...
9
votes
1answer
82 views
How to model 24 hours demand into a daily shift schedule?
I am working on a weekly staff scheduling optimization problem with 24/7 demand.
The binary decision variable is: $X_{\text{staff},\,\text{day},\,\text{shift}}$ whether to assign the staff $s$ to day ...
15
votes
2answers
212 views
Divisibility constraints in integer programming
In the study of a certain pure mathematical problem (related to infinite-dimensional Lie algebras) I found myself in a situation where it would be very desirable to be able to solve an integer ...
9
votes
1answer
123 views
Static stochastic knapsack problem: unbounded version
In the static stochastic knapsack problem (SSKP) the weights $w_i$ of the items are distributed according to a probability distribution. Each item $i \in I$ can be selected at most once.
So, ...
19
votes
4answers
995 views
Linearize or approximate a square root constraint
I encounter a nonlinear constraint that contains the square root of a sum of integer variables. Of course one could use nonlinear solvers and techniques; but I like linear programming. Are there any ...
11
votes
3answers
1k views
Soft constraints and hard constraints
The terms "soft constraints" and "hard constraints" are used in the context of optimization modeling.
Is there any standard way to figure out which is which in some of the complicated models?
11
votes
1answer
117 views
Change coefficient in PuLP
Once a model is implemented in PuLP, how do you change a coefficient (e.g., $a_{ij}$, $b_i$ or $c_j$) of a program of the from $\min\{c^{\top}x: Ax=b, x\geq0\}$?
Specifically:
How to update ...
10
votes
2answers
188 views
Fast validation of time windows in a routing problem
When solving a routing problem with time windows, unless you go for the arc-based math program that describes it, you have to check time windows "manually." For example, generating routes with any ...
4
votes
0answers
57 views
If and then constraint for a special case [duplicate]
I have the following constraint:
$$f\geq C_1\left(d-z-E_1-E_2\right)+C_2\left(E_1+E_2\right).$$
Here $f, d,z\in \mathbb{R}_{\geq 0}$ and $y\in \{0,1\}$ are variables and $C_1$, $C_2$, $E_1$, and $E_2$...
11
votes
3answers
255 views
Is my approach to my internship project good? Optimal allocation of product across stores, constrained optimization
Context: I am a CS student currently in a non-CS internship (logistics, supply chain).
My manager wants to leverage my knowledge of programming to build a program to solve the following problem:
As ...
7
votes
1answer
309 views
KKT inequality conditions
Let's say I have an objective function
$$f(x_1,x_2, \cdots, x_n)$$
and $N$ constraints
$$x_i \ge 0. $$
I am trying to solve it with KKT conditions. Now the objective function becomes
$$f(x_1,x_2,...
14
votes
1answer
565 views
How to formulate maximum function in a constraint?
How to formulate (linearize) a maximum function in a constraint? Suppose $C = \max \{c_1, c_2\}$, where both $c_1$ and $c_2$ are variables. If the objective function is minimizing $C$, then it can be ...
16
votes
2answers
149 views
Can we replace a binary variable with a continuous variable using a quadratic equality constraint?
Is it possible to replace a binary variable $x$ with a continuous variable that satisfies the quadratic equality constraint $x^2 - x=0$?
The function $f(x) = x^2 -x$ is not a convex function. Can ...
15
votes
2answers
109 views
Is the Irreducible Infeasible Subset (IIS) of an LP unique?
The IIS is a standard part of most modern solvers, but is it unique for an LP? My intuition tells me that it should be, but I could find any proof.
12
votes
1answer
215 views
Difference between lazy callbacks and using lazy constraints directly
I'm trying to use lazy constraints to solve an optimization problem. In some software such as CPLEX or GUROBI, they have some tools to handle them directly (in the original model) or using callback ...
11
votes
3answers
257 views
How to handle real-world (soft) constraints in an optimization problem?
Cross-posted at Stats.SE (aka Cross Validated)
I am working on a problem which involves optimizing for minimum power consumption in a large compressor network interconnected through pipelines (think ...
9
votes
4answers
147 views
Is there a canonical name for Score Folding (multiplying a priority soft constraint by a big weight)?
I've regularly encountered that there are too many constraints to categorize into just hard and soft constraints. For example:
Physical constraints (very hard), e.g. 1 person can only be at 1 spot ...
20
votes
3answers
431 views
What is the difference between integer programming and constraint programming?
At first glance both approaches appear to be very similar.
What are the major differences between integer programming and constraint programming?
11
votes
1answer
108 views
Simplest way to eliminate redundant constraints due to a new cut
I have a polyhedral set for constraining $x$:
\begin{align}
\mathcal{P} = \{x \in \mathbb{R}^n_{+} : \ Dx \leq d \}
\end{align}
where $D \in \mathbb{R}^{m \times n}, d \in \mathbb{R}^m$. I find the ...
11
votes
2answers
215 views
In an integer program, how can I “activate” a constraint only if a decision variable has a certain value?
Suppose we have the constraint
$$a_1x_1 + \cdots + a_nx_n \gtreqless b,$$
where $a_i$ and $b$ are constants and $x_i$ are decision variables. Suppose also that we want the constraint to hold if $y=1$ (...
22
votes
3answers
652 views
In an integer program, how I can force a binary variable to equal 1 if some condition holds?
Suppose we have a binary or continuous variable $x$, a binary variable $y$, and a constant $b$, and we want to enforce a relationship like
If $x \gtreqless b$, then $y = 1$.
How can we write this ...
12
votes
1answer
146 views
2 stage stochastic programming to approximate many stage problems
There are many naturally multi-stage (i.e., more than two) stochastic programming problems that are approximated by a two-stage stochastic programming model due to the complete intractability of the '...
16
votes
1answer
206 views
Working with absolute values in constraint in a LP or MILP
Having all the approaches explained in the blog called "OR in an OB World" (this address) in my mind, I would like to ask the following question:
What is the best practice to make a constraint linear ...
