# Questions tagged [linear-programming]

For questions related to problems that optimize (i.e., minimize or maximize) a linear objective subject to linear constraints.

352 questions
Filter by
Sorted by
Tagged with
357 views

### if-else condition for the objective variable using big M notation

Let $0\leq \beta\leq 1$ be an objective variable. The size of $\beta$ is $N\!\times\!N$. Now, how can I impose the following? if $\beta_{i,j}>0$ then $\beta_{j,i}=0$ Big M notation can be ...
157 views

137 views

### Modeling traffic in a city

I am trying to model traffic in a city, $(i,j)$ represents a road in a city. There are $H$ vehicles in a city they have some prescheduled set of destinations to visit, $A_{j,h}$ denotes arrival time ...
536 views

134 views

### Choosing better objective function for vehicle routing problem

I have a graph $G$ and the following variables. $b_{i,j}$ is $(i,j)$ edge is taken or not. $t_{i,j}$ is time to travel $(i,j)$ $A_{i}$, $D_{i}$ are arrival and departure time at node $i$. My first ...
78 views

### Building the Scheurman's Model II constraints for a multi period linear program

Scheurman's paper discusses Model I and model II Formulation to solve harvesting and scheduling problems. It is a specific implementation to solve multi period linear programs. Both models are also ...
248 views

### Trade off between number of constraints and bounds of a variable

I am not familiar with the inner working of the solvers. I mostly use the python pulp or IBM CPLEX solver. For fast execution ...
136 views

### Linearizing constraint with continuous and boolean variables

I have two continuous variables $A$, $B$ and two binary variables $x$, $y$. Condition: if $A = B \wedge x = 1 \wedge y=1$ then $z = 1$ else $z = 0$ from In an integer program, how I can force a ...
184 views

### Reducing number of suppliers for product portfolio

I have the following matrix of suppliers who are able to make a certain product, against all products in my portfolio. What is the best way of finding the solution to "the least suppliers necessary ...
469 views

### Negative reduced cost for basic variable

I am observing something unusual : after solving a linear program, some basic variables have negative reduced costs (instead of $0$) : ...
135 views

### Optimising the current model

After developing the MIP model I noticed that solver is taking a lot of time to reach the solution. So, how should I approach to optimize the current model? Are there any visualization tools or any ...
308 views

### Can we have all reduced costs (strictly) positive?

I had a number of students claim on their homework that "All $z_j-c_j$ values are positive, therefore the solution is optimal." Of course, I noted that they should say "non-negative" instead of "...
1k views

### How to formulate problems in the language of mathematical programming?

The question says it all. I am having difficulties formulating general problems (meaning no numbers just variables). When I read the solution, I understand but I can't figure how to formulate myself ...
41 views

1k views

### Open Source MILP software for Python with user-friendly API to define the optimization problem

Following the accepted answer to Assignment problem where assignments must be done sequentially I would like to write a Python script which can solve the problem defined there. It's a Mixed Integer ...
64 views

163 views

### Publishing paper that uses LP solver to solve equation

I was reading this paper by Cerna et al. (2018)1. In the paper there are only CPLEX-solvable equations given by the authors and the results. How valuable is this paper, and what is its quality? Can ...
201 views

### MIP for similar production percentages in production planning

As a task, I want to produce three products $x,y,z$ in different quantities $a,b,c>0$ respectively. It is not always possible to produce the full amount of each product, because of a lack of ...
208 views

### How to express this constraint?

I have the constraint \begin{align}\max&\quad\gamma\\\text{s.t.}&\quad a\ge\gamma b\\&\quad\gamma\le 1\end{align} where $\gamma$ is an optimization variable and $a$ is a function of some ...
211 views

### GUROBI Re-optimize a model

(For Linear Programming) I am aware of CPLEX's reoptimize methods. If I am not wrong, if you solve a problem and after that you add a new constraint, then you can call the reoptimize method for not to ...
453 views

### CPLEX Python API

I am trying to run the following optimization problem at Python by using the CPLEX API: $$\min \{x_1 + x_2\ | \ x_1 \geq 3, x_2 \geq 2, 2x_1 + x_2 \geq 9\}$$ I just want to give a matrix of ...
274 views

### LP sum of variables that are above a threshold

I am trying to code a constraint of the form: $$\sum_i y_i < K\,\text{where}\,\begin{cases}y_i = x_i\quad\text{if}\,x_i>k_i\\0\quad\text{otherwise}.\end{cases}$$ In other words, I want to ...
244 views

### Speedup or Caching for a Multi-Iteration MIP problem

I'm solving an MIP: \begin{align}\mathrm{arg\,min}&\quad\sum\limits_{i}{x_i}\\\text{s.t.}&\quad A\,x\geq1,\end{align} where both the matrix $A$ and vector $x$ are boolean valued, and $A$ is ...
315 views

### shadow prices associated with nonnegativity constraints

Why are shadow prices associated with nonnegativity constraints also called as reduced costs, even if they have the same interpretation as shadow prices associated with an optimal solution? Why the ...
317 views

### LP how to sum up positive free variables and negative free variables separately?

For an LP problem where $x_1,\dots,x_n$ are free variables (which may take positive or negative values), I want to bound the sums of $a_i\cdot x_i$ where $x_i>0$, and where $x_i<0$. I suspect ...
71 views

### Modelling a simple ordering problem to have balanced delivery days

Assuming that I should buy 50 items from 25 different vendors with pre-known delivery duration between 2-7 day for each, which day of a week should I place each order so that the delivery days be even ...
279 views

### Max flow problem without splitting the flow from the supply nodes - LP formulation help

Since max flow formulation can be easily solved using LP, I wanted to ask the following: I am trying to solve a simple max flow problem where the graph is bipartite but with one added constraint. The ...
253 views

### Search approach to solve optimization problem with only a minimum where time series get scaled

Currently, I am working on a relatively simple optimization problem: There is a set of time series (red) that get summed up to a cumulated time series (blue). The red time series have different forms ...
It is known that, in a linear program with $k$ constraints, there exists a basic feasible solution in which at most $k$ variables are non-zero. How can I find such a solution? Is there a polynomial-...