# Questions tagged [linear-programming]

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

326 questions
Filter by
Sorted by
Tagged with
39 views

996 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 ...
205 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 ...
202 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 ...
413 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 ...
267 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 ...
240 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 ...
298 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 ...
293 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 ...
69 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 ...
271 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 ...
252 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 ...
86 views

### Variable Sensitivity Analysis

I am working with the following MIP : \begin{alignat}2\min&\quad\sum_{j\in J} c_j x_j\\\text{s.t.}&\quad l_j \le f(x_j,t_j) \le u_j \quad &\forall j \in J \\&\quad x_j \in \mathbb{N} \...
1k views

### Finding a solution to a linear program with a small number of zeros

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-...
353 views

### Black-box optimization with linear programming?

In my research, I do a black-box optimization based on a simulation model with nonlinear properties. The simulation model gets an operation plan for a time period and then returns a time series, which ...
322 views

### Is there any relationship between KKT and duality?

I noticed the similarities between KKT and complementary slackness, but I do not fully understand it.
224 views

### Find all Combinations of a Matrix

I have a $16\times11$ matrix and want to find all eligible* combinations of this matrix including always entities from all 11 columns. A simple example from a $2\times3$ matrix would be the following:...
128 views

### Introducing a big M variable in given equations

While I do understand the general workings of the Big-M-method I am struggling with the following sample exercise, in which the Big-M-method has to be used to find a first feasible solution: \begin{...
163 views

74 views

### What to do with cuts (constraints) when a fixation is contrary to a RHS in a ILP / LP relaxation?

I am trying to understand an algorithm in a paper by Crévits et al. (2012)1 (see algorithm 2, the cuts I'm referring to are from the reduced costs). It uses a series of successive cuts on a linear ...
428 views

1k views

This page describes the graphical method to solve a linear program. The formulation is as follows. \begin{alignat}{2} \max &\quad Z = 200W + 100B\\ \text{s.t.} &\quad 1W + 0.8B &&\... 0answers 33 views ### In a binary logistic regression context, how to introduce a constraint to model the dependency between consecutive samples Imagine we are running a logistic regression to identify opportunities for car sale promotion, using previous promotion campaign's result. Each y is the increase of car sale after the promotion. ... 1answer 552 views ### Duality in mixed integer linear programs I know that the standard duality theory for the linear programming problem does not hold for mixed integer linear programming problems. I was wondering why an integer program does not have a dual ... 4answers 277 views ### Does this 0-1 integer program have any speciality? Given matrix A \in \{0,1\}^{m \times n} and vector b \in (\mathbb{Z^+})^m, where \mathbb{Z^+} is the set of positive integers,\begin{array}{ll} \text{maximize} & c^\top x\\ \text{subject ...
I'm trying to deal with a process planning and machine layout allocation simultaneously. I have the following variables: $X_p{_w}_{cj}=1$ if an operation $p$ is done by a machine $w$ with a ...