37
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 ...
- 13.2k
29
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 ...
27
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 ...
- 1,809
26
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 ...
- 13.2k
21
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}$. ...
- 13.8k
19
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 ...
- 1,542
19
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 ...
- 33.6k
18
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 ...
- 671
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 ...
- 13.8k
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 ...
- 40.1k
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 ...
- 13.2k
15
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 \...
- 13.2k
15
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 ...
- 13.8k
15
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 \...
- 13.7k
14
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| \...
- 13.8k
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 ...
- 300
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 ...
- 13.2k
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)...
- 2,866
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 ...
- 3,031
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 ...
- 1,245
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 ...
- 13.2k
12
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 \...
- 2,865
11
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$.
- 40.1k
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.
- 33.6k
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_{...
- 33.6k
11
votes
Accepted
Quadratic constraints in JuMP
A "quadratic constraint" is a constraint of the form $f(x) \leq 0$, where $f(x)$ is a quadratic function, i.e., as you wrote,
$$
f(x) = \frac{1}{2}x^{T}Hx + q^{T}x + b
$$
for some square ...
- 4,268
11
votes
Accepted
Constrained optimization of a sum
You also need to account for Lagrange multipliers for the bound constraints $-1\le x_i \le 1$.
Given all $a_i>0$, the (linear programming) problem is to maximize $\sum_i a_i x_i$ subject to
\begin{...
- 33.6k
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 ...
- 3,469
10
votes
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 ...
- 1,317
Only top scored, non community-wiki answers of a minimum length are eligible