# Questions tagged [constraint]

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

278 questions
Filter by
Sorted by
Tagged with
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 ...
• 13.1k
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?
• 2,023
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 ...
• 1,859
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 ...
• 8,667
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 ...
• 338
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.
• 3,459
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 ...
• 2,104
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 ...
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?
• 8,960
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 ...
• 2,319
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 ...
• 8,960
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$ (...
• 13.1k
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 ...
• 1,485
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 ...
• 2,377
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 ...
• 12.2k
5k views

### If-then constraints in MIP programming

For continuous variables $x$ and $y$, the constraints are: ...
• 221
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 ...
• 359
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 ...
• 3,980
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 '...
• 1,859
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 ...
• 211
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 ...
• 1,355
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 ...
• 1,355
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 ...
• 4,891
411 views

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$...
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 ...
• 169
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 \$\...
• 163