# Questions tagged [linear-programming]

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

841 questions
Filter by
Sorted by
Tagged with
1 vote
29 views

### Optimal way to formulate a piecewise linear function

I am working on LP problem whose objective function includes a piecewise linear function. I would like to figure out the optimal way to formulate the piecewise linear function in order to minimize the ...
62 views

### Enforcing Order in a Linear Programming Question

I have an optimization model to fulfill the water requirements of a city's distribution network. The model includes water sources from rainfall collection, river extraction, reservoir storage, and ...
• 31
1 vote
38 views

### Multi-Commodity Flow with "group edges"

I'm currently working on a special variation of the Multi-Commodity flow problem. My goal is to solve this variation via column generation, because the graph can become very large. Description Given......
• 13
1 vote
151 views

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

(Edit: there was a slight translation error, to be clear, we tried this since the start with Binary variables (IP), even then we couldn't crack it) I'm an undergraduate in Industrial Engineering and ...
65 views

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

I want to use the sum of a series of linear expressions as objective and constraints. These linear expressions are chosen to be included or not based on some conditions. I can achieve it in Excel ...
• 13
1 vote
57 views

### Integrality gap vs Gurobi Gap

I was wondering what the difference is between the integrality gap (i.e. best known solution in relation to the LP relaxation) and the gap from the MIP solver from Gurobi, for example. As I understand ...
• 21
46 views

### Need help for the python scheduling code

I'm working on a Python application using PuLP for optimization, and I'm having trouble ensuring that only one material is produced on a given day. The constraint prob += pulp.lpSum(production_flag[m][...
1 vote
45 views

### How to set up the master and subproblem

I have the following question. I have a classical scheduling model with the following constraints: Demand coverage One shift per day Minimum and maximum number of consecutive working days Forward ...
1k views

### Multiple Travelling Salesmen - How to make the second slowest salesman matter?

I'm building a Mixed Integer Linear Program for a variant of TSP I'm dealing with, where there are multiple salesmen. The way I have formulated the problem is that each agent has a time variable $T_i$ ...
36 views

### How to generate random bounded polytope by MATLAB defined by Ax=b, x≥0

How can one create a random bounded polytope in MATLAB, specified by the conditions $‎\lbrace‎x:~ Ax = b,~ x \geq 0‎\rbrace‎$
1 vote
72 views

### Solve scheduling model using a greedy heurisitc

I have the following scheduling problem. Relatively simple and not very complex (only serves as an example). The indexes are $I$ worker, $T$ days and $J$ shift. The decision variable is $x_{ijt}$, ...
• 71
1 vote
67 views

### Best approach to initialize column generation

I was wondering what the typical approaches are for generating an initial solution for the first column in a COlumn Generation approach and which usually work best and are easiest to implement (Gurobi)...
69 views

• 1,857
40 views

304 views

### Linear condition between two continuous variables

There are two real variables $x$ and $y$. The conditions are such that: if $y\le 0$, then $x=0$ if $y>0$, then $x=y$ How to write linear equations or inequalities to satisfy both the conditions?
• 41
104 views

### How to model this constraint in a better way?

I have a resource allocation problem. There are $M$ users and $N$ resources (machines). One user can be assigned to multiple resources/machines. But maximum $B$ machines can be activated at a time for ...
• 2,377
1 vote
43 views

### Primal-dual simplex method for general LP

I've learned the primal-dual method for standard LP, but for a general LP written as \begin{align} \min_{x\in \mathbb{R}^n} ~~~ &c^\top x \\ s.t. ~~& l^{s}\leq Ax \leq u^{s},\\ ...
• 77
59 views

### What's the dual of an LP in its general form?

For an LP written as \begin{align} \min_{x\in \mathbb{R}^n} ~~~ &c^\top x \\ s.t. ~~& l^{s}\leq Ax \leq u^{s},\\ &l^{x}\leq x \leq u^{x} \end{align} how can we get its dual ...
• 77
194 views

### Reformulate constraints

I have the following constraints and am wondering whether I can formulate the whole thing more narrowly and with fewer constraints. $x_{itk}$ is binary and $u_{it}, v_{itk}\in [0,1]$. $M$ is a Big-M ...
67 views

### What approximation is guarantees when solving an LP with floating-point numbers?

Given a linear program \begin{align} \text{maximize} \quad & c^{T}x \\ \text{s.t.} \quad & A x \leq b \end{align} I can solve it exactly in polynomial time, using e.g. interior-point ...
1 vote
86 views

### How to track the first timestep at which a binary variable becomes 1 in an IP? [duplicate]

I have an MIP where I have a binary variable $y_t$ which is set to 1 or 0 and is indexed by time t. It can be set to 1 at multiple timestamps but it is never continuously 1 for more than single ...
• 33
1 vote
45 views

### Converting a function composing of multipe pieces into a linear equation

I have a variable (alpha) which depends on some other binary variables, denoted as X_i. So, for some combination of other variables, alpha may take a value (Beta_j). I added some auxillary variables (...
• 97
1 vote
86 views

### How to model $\max\limits_{x\in X} \min\limits_{y\in Y} \max\limits_{z\in Z} f(z)$ as single MILP

I have the following optimization problem: \begin{align*} \max\limits_{x\in X} &\min\limits_{y\in Y} \max\limits_{z\in Z} & f(z) \\ &\text{such that} & (x, y, z)\in P \end{align*} ...
90 views

### Why this ILP and LP are equivalent?

Let's consider a competition with $n$ questions. Each question has a price $p_i$ and a score $v_i$. To advance to the next round of the competition, we need to accumulate a minimum score of $D$. We ...
1 vote
95 views

### A tool for finding integer solutions to linear systems

I have a system of linear equations $A x = 0$, where $A$ is an integer matrix, and I want to find a non-zero solution, if it exists. In that case, a rational solution exists. Multiplying by the common ...
49 views