29 votes
Accepted

In an integer program, how I can force a binary variable to equal 1 if some condition holds?

If $x$ is binary: Then the "if" condition really means either "$x = 0$" or "$x=1$". To enforce "if $x=0$ then $y=1$": use $$y \ge 1-x.$$ To enforce "if $x=1$ then $y=1$": use $$y \ge x.$$ If you ...
user avatar
27 votes
Accepted

Is the Irreducible Infeasible Subset (IIS) of an LP unique?

The irreducible infeasible subsystem (IIS) for an infeasible linear program (LP) is a minimal subset of constraints that has no feasible solution, i.e., an inconsistent set of constraints for which ...
user avatar
23 votes
Accepted

Soft constraints and hard constraints

In an optimization model, a hard constraint is a constraint that must be satisfied by any feasible solution to the model. On the other hand, a soft constraint can be violated, but violating the ...
user avatar
  • 1,759
23 votes
Accepted

How to formulate (linearize) a maximum function in a constraint?

(I'm going to change $c$ to $x$ in my answer, since $c$ is usually used for cost coefficients, not decision variables.) We want a set of constraints that enforces $X = \max\{x_1,x_2\}$. Define a new ...
user avatar
20 votes
Accepted

Linearize or approximate a square root constraint

This can be handled as an MISOCP, Mixed-Integer Second Order Cone problem. The leading commercial MILP solvers can also handle MISOCP. Specifically, due to $x_{ij}$ being binary, $x_{ij}^2 = x_{ij}$. ...
user avatar
18 votes
Accepted

Is This Constraint Convex?

Arguments 3 and 4 are incorrect. The Right-Hand Side (RHS) is not convex. Even if it were, setting a nonlinear equality with either side non-affine is non-convex. As the final coup de grace, even if ...
user avatar
18 votes

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

You have the inputs and outputs confused. The three black circles are given, and the purple circle is a desired output. But, yes, any system of equations can be thought of as an optimization problem ...
user avatar
  • 21.7k
17 votes
Accepted

What is the difference between integer programming and constraint programming?

You have asked a broad question, so I will provide a broad answer. Integer programming typically refers to integer linear programming which is a mathematical modeling and solution paradigm. Decisions ...
user avatar
  • 1,502
17 votes
Accepted

Difference between lazy callbacks and using lazy constraints directly

Lazy constraints will only be checked when an MIP solution satisfying all other constraints, including integrality, is found. If you provide all your lazy constraints in advance to CPLEX, for ...
user avatar
17 votes
Accepted

Divisibility constraints in integer programming

I going to assume that the ratio $L(x)/Q(x)$ is nonnegative. If it can be negative, I think there may be a workaround, but this will complicated enough without dealing with that. I'm also going to ...
user avatar
  • 28.7k
15 votes
Accepted

How to handle real-world (soft) constraints in an optimization problem?

Essentially you are trying to constrain $|p_1-p_2|$, where $p_1$ and $p_2$ are the pressures. Normally this must be done using binary variables (see this question, which @MarcusRitt linked to), but in ...
user avatar
14 votes
Accepted

No "not equals" constraint in Gurobi

If you want $x_1\neq x_2$, you can linearize $|x_1-x_2|\ge \varepsilon$, where $\varepsilon$ is your tolerance. You can do this by introducing a boolean variable $y=1$ if and only if $x_1-x_2\ge \...
user avatar
  • 10k
13 votes

In an integer program, how can I “activate” a constraint only if a decision variable has a certain value?

These are know as "indicator constraints" or "on/off" constraints. The best formulation is the convex-hull one, it includes the optimal big-M value plus additional non-redundant constraints, here's a ...
user avatar
  • 300
13 votes
Accepted

In an integer program, how can I “activate” a constraint only if a decision variable has a certain value?

Let $M$ be a new parameter (constant) that equals a large number. Greater-than-or-equal-to constraints: The constraint is $a_1x_1 + \cdots + a_nx_n \ge b$. Rewrite it as $$a_1x_1 + \cdots + a_nx_n \...
user avatar
13 votes

Difference between "Optimization" and "Constrained Optimization"?

You are right that most real-world problems are constrained, and therefore, for the most part, "optimization" and "constrained optimization" are synonymous. However, some algorithms only apply to ...
user avatar
13 votes

Is This Constraint Convex?

Counterexamples to your arguments: Argument 1: Only affine equality constraints are convex, $x = y^2$ is not convex. Argument 3: Take $f(x) = x^4$ and $g(x) = x$. Both are convex, but the ratio $h(x)...
user avatar
13 votes
Accepted

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

I suspect you read that actual floating point optimization solvers treat strict inequalities ($<$ and $>$) as non-strict inequalities ($\le$ and $\ge$). Solvers also give themselves a fudge ...
user avatar
13 votes

Adding a constraint in constraint programming

This is not true in practice. Moreover, this is something almost impossible to guess without experimenting. Indeed, adding constraints (proven to be mathematical valid, or just guessed by your flair ...
user avatar
  • 2,609
12 votes

In an integer program, how I can force a binary variable to equal 1 if some condition holds?

Rather than linearising the logical constraint, I would try the logical constraints built in a solver. Gurobi and SCIP both have indicator constraints. My colleague works with these a lot and he’s ...
user avatar
  • 1,225
12 votes
Accepted

Working with absolute values in constraint in a LP or MILP

You need to model disjunctive constraints. I will assume that variable $x$ is constrained to lie in $L_1 \le x \le U_1$ or $L_2 \le x \le U_2$. For instance, if you have the constraint $2 \le |x| \...
user avatar
12 votes

Is my approach to my internship project good? Optimal allocation of product across stores, constrained optimization

This is a very broad question and there is a lot going on here. So I will provide a few initial thoughts; hopefully others will chime in as well; and then you might want to post more specific ...
user avatar
11 votes
Accepted

Is there a better way to formulate this constraint?

You can strengthen your "conflict" constraint to a "clique" constraint: $$\sum_j x_r^j \le 1$$ for all $r$. There are fewer of these, and they dominate the conflict constraints.
user avatar
  • 21.7k
11 votes

Hard to soft constraint

My approach would be: $$\begin{align} \min\>&- f(\color{darkred}x)+\sum_j \color{darkblue}p^-_j \color{darkred}s^-_j +\sum_j \color{darkblue}p^+_j \color{darkred}s^+_j\\ &\sum_i \...
user avatar
11 votes

Gurobi: how to add a constraint to make there be only one non-integer value

Let $x_{p,\ell}$ be the continuous variables in your table. Introduce integer variables $y_{p,\ell}$ and binary variables $z_{p,\ell}$, and impose linear constraints \begin{align} -z_{p,\ell} \le x_{...
user avatar
  • 21.7k
10 votes
Accepted

KKT inequality conditions

If you want to use the KKT conditions for the solution, you need to test all possible combinations. This is why in most cases, we use the KKT's to validate that something is an optimal solution, since ...
user avatar
  • 3,034
10 votes
Accepted

How to linearize a constraint with max

Welcome to OR.SE! If you're looking to enforce $$\max\limits_{pcj}X_{pwcj} \leq L_{wk}, \ \forall w,k$$ then simply using the constraint $$X_{pwcj} \leq L_{wk}, \ \forall p,w,c,j,k$$ will do the ...
user avatar
  • 1,307
10 votes

Linearization $\max(c_1 x_2, c_2 x_2, \ldots, c_nx_n) \geq q$ constraint

Assuming that the $c_i$ and $q$ are all positive you may add one binary variable $y_i$ for every $i=1,\cdots,n$ then you may do \begin{align}c_i x_i &\geq q y_i \quad\forall i\\\sum_i y_i &\...
user avatar
10 votes
Accepted

Linearization $\max(c_1 x_2, c_2 x_2, \ldots, c_nx_n) \geq q$ constraint

You can do this with no new variables. Let $S=\{k:c_k \ge q\}$ and add the constraint $\sum_{k\in S}x_k \ge 1$.
user avatar
  • 28.7k
10 votes
Accepted

How to set a limit for a switch to 0 of a variable for 2 variables combined

Again, you need to introduce binaries: $\delta_t$ takes values $1$ if and only if the device is switched off at time $t$ $\alpha_t$ is the binary associated with variable $x_t$ $\beta_t$ is the ...
user avatar
  • 10k
10 votes
Accepted

How to model: If $X\ge\epsilon$ then $X\ge Y$

Introduce binary variable $Z$ and linear constraints \begin{align} X - \epsilon &\le (\bar{X} - \epsilon) Z \tag1 \\ Y - X &\le (\bar{Y} - 0) (1-Z) \tag2 \\ \end{align} Constraint $(1)$ ...
user avatar
  • 21.7k

Only top scored, non community-wiki answers of a minimum length are eligible