Skip to main content

New answers tagged

1 vote

Can a cut be tight across a diagonal in a polytope?

I'll use $(x,y,z)$ for the coordinate system in three dimensions. Consider the polytope $P$ defined by the following. \begin{align*} x-y+z & \le1\\ -x+y+z & \le1\\ \frac{1}{2}x-\frac{1}{2}y+z &...
prubin's user avatar
  • 39.8k
3 votes

Can LP be solved using the previous solution during branching?

Yes, after branching, the basis from the parent node will be dual feasible to its children, so dual simplex is the natural choice to warm start the LP solver. That is how virtually every branch-and-...
RobPratt's user avatar
  • 33.1k
5 votes

How to model an optimization problem with mutual exclusivity of two variables, without introducing integer variables?

You want to enforce $L_t=0 \lor S_t=0$, where both variables are nonnegative. Here are three ways: The approach in your question, but with $z_t$ binary. Nonlinear “complementarity” constraint $L_t ...
RobPratt's user avatar
  • 33.1k
1 vote
Accepted

Optimal way to formulate a piecewise linear function

I don't think you can gainfully avoid the binary variables (or SOS constraints). Some solvers directly support piecewise linear functions, but I'm pretty sure that means added binary variables under ...
prubin's user avatar
  • 39.8k
2 votes

My Professor couldn't complete the model for this optimization problem. how do i model this problem?

Without the group score it's a very easy problem. With the group score it becomes (for an open-source solver) a very difficult problem, even though the number of auxiliary variables isn't very high. ...
Reinderien's user avatar
4 votes

Enforcing Order in a Linear Programming Question

For simplicity, I will omit the $t$ index. You want to enforce $$x_1+x_2+x_3\ge d \implies x_4=0.$$ Equivalently, enforce the contrapositive $$x_4>0 \implies x_1+x_2+x_3< d.$$ Let $\epsilon$ be ...
RobPratt's user avatar
  • 33.1k
2 votes
Accepted

Multi-Commodity Flow with "group edges"

First note that you can replace the pair of inequality constraints with a single equality constraint. Yes, column generation with a shortest path subproblem applies here. The $y$ variable is a ...
RobPratt's user avatar
  • 33.1k
2 votes

My Professor couldn't complete the model for this optimization problem. how do i model this problem?

There are at least two approaches that can be used to model this. The more obvious one uses binary variables $x_{wsd}$ equal to 1 if and only if worker $w$ is scheduled in slot $s$ on day $d.$ Some of ...
prubin's user avatar
  • 39.8k
1 vote
Accepted

How to write conditional constraints and sum the result in Linear Programming in Python?

To minimize $\sum_i \max(f_i,0)$, introduce a nonnegative variable $y_i$ and minimize $\sum_i y_i$ subject to $y_i\ge f_i$. To enforce $\sum_i \min(f_i,0)\ge -5000$, introduce a nonpositive variable $...
RobPratt's user avatar
  • 33.1k

Top 50 recent answers are included