Tag Info

Hot answers tagged constraint

28

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 want to require that $y=1$ if and only if the condition holds, then replace the $\ge$s above with $=$s. If $x$ is continuous: In this case, numerical inaccuracy ...

27

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 any proper subset of the constraints is consistent. It is not true that an IIS is unique. For intuition, consider that there may be more than one source of ...

21

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 constraint incurs a penalty in the objective function (often, the greater the amount by which the constraint is violated, the greater the penalty). So, a good way to ...

21

(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 binary decision variable $y$, which will equal 1 if $x_1 > x_2$, will equal 0 if $x_1 < x_2$, and could equal either if $x_1 = x_2$. Let $M$ be a constant ...

20

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}$. Therefore, the left-hand side is the two-norm of the vector over $i \in I$ having elements $\sqrt{a_{ij}} x_{ij}$. I don't know whether this is the best way ...

18

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 the RHS were convex, an inequality, {affine expression} $\le$ {convex RHS}, is going the wrong direction to be convex. I suggest you study sections 2.3 and ...

17

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 example, then your main benefit is that these constraints are only checked against solutions that would otherwise be feasible. However, you may have an exponential ...

17

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 assume that $Q(x)$ and $L(x)/Q(x)$ have a priori upper and lower bounds, say $\underline{Q} \le Q(x) \le \overline{Q}$ and $L(x)/Q(x) \in \{1,\dots,N\}$. You can ...

16

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 are modeled as a vector of real numbers, some of which are further constrained to take only integer values. The decision vector is constrained to satisfy a ...

15

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 this case, binary variables are not needed (since the lower bound on the absolute value is 0, as @MarkLStone pointed out). In short, you can simply use the ...

13

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 note characterizing this formulation. There's also a generalization for convex nonlinear "on/off" constraints here and recent extensions here.

13

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 \ge b - M(1-y).$$ Then, if $y = 1$, the constraint is active, and if $y=0$, it has no effect since the right-hand side is very negative. (If all of the $a_i$ ...

13

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 unconstrained problems: an easy example is bisection search. So when people say "constrained optimization," they are emphasizing that they're considering the ...

13

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) = \frac{x^4}{x}$ is not. Argument 4: Let $f(x) = x$, and $y \in \mathbb{R}$. $f$ is convex, but $g(x, y) = yf(x) = xy$ is not.

13

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 factor, called feasibility tolerance, equal to the amount by which they may be violated in reality but treated as satisfying the constraint by the solver. If you ...

12

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 finding the indicator constraints in Gurobi perform worse than big-M. He’s in contact with the Gurobi developers so I might be able to get more info if there’s ...

12

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| \le 5$, then choose $L_1 = -5$, $U_1 = -2$, $L_2 = 2$, $U_2 = 5$. My solution handles a more general case than what you require, but includes your situation as ...

12

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 questions, which will be easier for us to provide more concrete answers to. The approach you outlined is focused on the inventory level (IL). It assumes that there is ...

11

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.

11

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 and feeling of the business) to a mathematical optimization model that is solved by constraint programming techniques or integer programming techniques should be ...

11

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 \color{darkblue}a_{i,j}\color{darkred}x_{i,j} = 10 -\color{darkred}s^-_j + \color{darkred}s^+_j&&\forall j\\ &\color{darkred}s^-_j,\color{... 11 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_{p,\ell} - y_{p,\ell} &\le z_{p,\ell} &&\text{for all p and \ell} \tag1 \\ \sum_\ell z_{p,\ell} &\le 1 &&\text{for all p} \tag2 \... 10 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 the KKT's are the first-order necessary conditions for optimality. For convex nonlinear optimization, you are better off using sequential quadratic ... 10 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,kwill do the trick. This will ensure every value (including the maximum) will be at most L_{wk}. (If there's another dynamic you're looking to enforce, e.g., within a set of ... 10 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 &\geq 1\end{align} 10 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 binary associated with variable y_t The condition can be written in conjunctive normal form as follows: (\alpha_{t-1}\wedge \lnot \alpha_{t} \wedge \lnot \...

10

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)$ enforces $X > \epsilon \implies Z = 1$. Constraint $(2)$ enforces $Z = 1 \implies X \ge Y$.

9

Indeed, as you pointed out already, checking time windows feasibility is only doable in linear time for a given, static, route. However, you may exploit preprocessing techniques and partial paths concatenation to achieve constant time worst-case complexity to assess time windows feasibility within a typical routing metaheuristic. Take a look at the article ...

9

If the model in PuLP is: from pulp import LpProblem, LpVariable, LpMaximize, lpSum m = LpProblem(name='example', sense = LpMaximize) x = LpVariable.dicts(name='x',indexs=[1,2,3]) m += lpSum(x) <= 3, 'c1' m += lpSum(i*x[i] for i in [1,2,3]), 'obj' We can access the coefficient of $x_1$ in 'C1' with: m.constraints['c1'][x[1]] # This the coefficient => ...

9

As the borders between statistics and machine learning are diffuse, I take freedom to include statistics. Some links: Non-negative least squares, posts on cross validated. But often restrictions can be implemented just by reformulation. Order-restricted statistical inference should be better known and more used. There is a new R package being developed ...

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