Skip to main content

Questions tagged [constraint]

For questions related to constraints, i.e. any restriction or relation a set of decision variables has to satisfy.

Filter by
Sorted by
Tagged with
32 votes
3 answers
19k 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 ...
LarrySnyder610's user avatar
29 votes
3 answers
8k 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?
YukiJ's user avatar
  • 2,023
22 votes
4 answers
3k 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 ...
Albert Schrotenboer's user avatar
18 votes
1 answer
3k 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 ...
Oguz Toragay's user avatar
  • 8,667
17 votes
2 answers
512 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 ...
prash's user avatar
  • 338
16 votes
2 answers
1k 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.
Richard's user avatar
  • 3,459
16 votes
1 answer
11k views

How to formulate (linearize) a 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 ...
Mostafa's user avatar
  • 2,104
16 votes
2 answers
2k 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 ...
Andrei Smolensky's user avatar
15 votes
3 answers
15k 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?
A.Omidi's user avatar
  • 8,960
13 votes
2 answers
1k 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 ...
GrayLiterature's user avatar
13 votes
1 answer
2k 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 ...
A.Omidi's user avatar
  • 8,960
12 votes
2 answers
3k 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$ (...
LarrySnyder610's user avatar
12 votes
3 answers
524 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 ...
chupa_kabra's user avatar
  • 1,485
12 votes
3 answers
3k views

Does it make sense to use strict equality constraints in optimization?

Once I learned from some post that the strict equality constraint in an optimization problem does not make much sense. We should always use $\le$ constraint. How much truth is in this? If I must have ...
KGM's user avatar
  • 2,377
12 votes
1 answer
1k views

Which ML algorithms work by solving constrained optimization problems?

As far as I know, most machine learning algorithms solve unconstrained optimization problems, i.e., if we were to unroll all the neurons into symbolic expressions we would end up with a massive ...
Nikos Kazazakis's user avatar
12 votes
1 answer
5k views

If-then constraints in MIP programming

For continuous variables $x$ and $y$, the constraints are: ...
Qbik's user avatar
  • 221
12 votes
1 answer
610 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 ...
Tim's user avatar
  • 359
12 votes
1 answer
877 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 ...
independentvariable's user avatar
12 votes
1 answer
371 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 '...
Albert Schrotenboer's user avatar
11 votes
3 answers
361 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 ...
Marco's user avatar
  • 211
11 votes
2 answers
262 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 ...
Daniel Duque's user avatar
  • 1,355
11 votes
1 answer
1k 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 ...
Daniel Duque's user avatar
  • 1,355
10 votes
4 answers
252 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 ...
Geoffrey De Smet's user avatar
10 votes
2 answers
411 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 $...
Tim's user avatar
  • 205
10 votes
1 answer
2k views

No "not equals" constraint in Gurobi

I'm using Gurobi and trying to set a constraint that two variables A, B are not equal ...
pigsun's user avatar
  • 145
10 votes
2 answers
586 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 ...
rasul's user avatar
  • 2,150
10 votes
1 answer
1k 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 &...
Harry van t Kamp's user avatar
9 votes
3 answers
487 views

Is there a better way to formulate this constraint?

Let $x_{r}^{j}=1\iff$ the machine schedules job $j$ using resource $r$. My constraint says that: a resource cannot be used twice, i.e., if $x_{r}^{j}=1$, then $x_{r}^{j'}=0$ for $j'\neq j$. I write ...
zdm's user avatar
  • 403
9 votes
1 answer
631 views

Adding a constraint in constraint programming

Is it true that the more we add constraint to a constraint programming solver the more efficient it will be? How does this compare to adding constraints in integer programming solvers.
Best_fit's user avatar
  • 567
9 votes
2 answers
818 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 ...
SantiagoAm16's user avatar
9 votes
1 answer
185 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 ...
campioni's user avatar
  • 1,133
9 votes
1 answer
248 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, ...
Libra's user avatar
  • 937
8 votes
2 answers
1k views

Can the (famous) "Problem of Apollonius" be Considered as a "Constraint Optimization" Problem?

In the famous "Problem of Apollonius" (https://en.wikipedia.org/wiki/Problem_of_Apollonius), the goal is to draw three circles that are tangential to another circle: Algebraically, we can ...
stats_noob's user avatar
  • 1,841
8 votes
3 answers
421 views

How to model a non-overlap constraint between 2 groups of tasks?

Let $T$ be a set of tasks. Each task $t \in T$ has a duration $d_t$. Let $T_1 \subset T$ and $T_2 \subset T$ such as $T_1 \cap T_2 = \emptyset $ How can I model the following constraint : all tasks ...
LouisPopovic's user avatar
8 votes
3 answers
689 views

Bin packing variant

I am currently struggling with a bin packing variant, where we have fuel and compartments of a tank truck. Some industry constraints apply, but the whole picture is that you must fit the total volume ...
dimboukosis's user avatar
8 votes
3 answers
934 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"...
Skander H.'s user avatar
  • 2,139
8 votes
2 answers
3k 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 ...
campioni's user avatar
  • 1,133
8 votes
1 answer
571 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 ...
Eugene's user avatar
  • 183
8 votes
1 answer
202 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 ...
janicebaratheon's user avatar
7 votes
2 answers
292 views

Index of element in MILP vector decision variable that equals 1

Consider a decision variable in a MILP constrained: $$\sum_i p_i = 1$$ $$p_i\ \in \{0, 1\}$$ Obviously one element in $p$ is 1 and all others are 0. How can I set a decision variable to the index i of ...
davidconf's user avatar
7 votes
2 answers
384 views

Set constraint mip

I am programming a MIP problem. There are two continuous variables but only one can have a value and the other must then be zero. How do I give this as a constraint?
kc27's user avatar
  • 73
7 votes
1 answer
509 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,...
ooo's user avatar
  • 1,589
7 votes
1 answer
882 views

How to find the idle intervals in integer programming?

I have a scheduling problem with one machine and one job. I defined a binary variable $z_t$ that is 1 iff the job is scheduled at time $t$ (the job can be served in multiple times that are not ...
zdm's user avatar
  • 403
7 votes
2 answers
806 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 ...
naive's user avatar
  • 173
7 votes
1 answer
641 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 $\...
nflgreaternba's user avatar
7 votes
2 answers
249 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$...
Harry van t Kamp's user avatar
7 votes
2 answers
3k views

The general meaning of "constraint relaxation" in the context of the Shortest Path Problem

I've read that in the context of the Shortest Path Problem, the use of the term "relaxation" ("relaxing edges") [...][the use of the term "relaxation"] is historical. The outcome of a relaxation ...
Alexey's user avatar
  • 169
6 votes
4 answers
927 views

Constrained optimization of a sum

I have to maximize the function $f= \sum_{i=1}^na_ix_i $ subject to the constraints $g = \sum_{i=1}^n x_i = 0 $, $-1\leq x_i \leq 1$ and $a_i>0$. Lagrange multiplier method doesn't work because $\...
Deep's user avatar
  • 163
6 votes
1 answer
1k views

Quadratic constraints in JuMP

I am a bit new to programming and am currently working with solving optimization problems in JuMP in Julia. I got a tip from the JuMP page that I should also use ...
Annaquest's user avatar
6 votes
1 answer
463 views

How to solve this linear program with an exponential number of constraints?

Consider the following convex program: \begin{align*} \min g(x) && \text{such that} \\ f_i(x) &\geq b_1 && \text{ for } i \in 1,\ldots,n; \\ f_i(x)+f_j(x) &\geq b_1+b_2 &&...
Erel Segal-Halevi's user avatar

1
2 3 4 5 6