Questions tagged [linear-programming]
For questions related to problems that optimize (i.e., minimize or maximize) a linear objective subject to linear constraints.
266
questions
1
vote
0answers
53 views
How can I formulate an LP or heuristic solution for this problem?
[I welcome any alternate or simplified formulation of my problem]
I have an optimization problem. See the attached figure which is self explanatory. The solid line is intended signal, the dashed lines ...
0
votes
1answer
154 views
Is optimal solution to dual not unique if optimal solution to the primal is degenerate?
If optimal solution to the primal is degenerate, does it necessarily follow that optimal solution to dual not unique? That is, is uniqueness an unnecessary assumption?
Spin-off from here.
In my ...
2
votes
1answer
58 views
Maximum bipartite matching with breakpoints in edge weight function
I am looking for an analogy to the problem I am facing or better yet a paper or even code.
I have:
Nodes from set A and B.
Edges are from a single A to many B.
I am framing a max bipartite matching ...
2
votes
0answers
46 views
Reading MPS file for linear programming and reconstructing the Optimization model
Are you aware of any tutorial that can help me learn on how to reconstruct the objective function and constraints from a MPS file once it's loaded in MATLAB. I can load the mps file given to me and ...
0
votes
2answers
162 views
How can I formulate this specific if-then constraint?
IF $\sum\limits_d X_{i,d}\ge6$ THEN $Y_i = 1$ (strictly)
AND
IF $\sum\limits_d X_{i,d}<6$ THEN $Y_i = 0$ (strictly)
$X$ and $Y$ are binary variables.
What I'm actually trying to do is to charge the ...
38
votes
8answers
1k views
Optimization Problem Libraries
Can someone please make a list of optimization problem libraries so that the community can add to and refine it?
I know a few off the top of my head.
5
votes
0answers
100 views
Obtaining the system of irredundant inequalities from a set of inequalities using CPLEX
Given a linear system of inequalities $Ax \geq b$, I would ideally like to compute the irredundant set for those set of inequalities. I know how to do so mathematically, but I was wondering if there ...
8
votes
2answers
598 views
Linear optimization problem with user-defined cost function
I have a linear optimization problem for which I am looking for a suitable optimization solution that can fulfill my requirements. Here is an explanation of the optimization problem:
There are a ...
10
votes
5answers
3k views
Is there a Linear Programming Library that natively supports fractions instead of floating point arithmetic?
If one recalls how the Simplex method is taught by hand in most LP classes it takes place entirely in $\mathbb{Q}$. All operations yield exact fractions.
For this reason I'm looking for linear ...
3
votes
0answers
44 views
Simplex method on graphs: How do I find a basic solution using the Ford-Fulkerson algorithm?
I'm tasked with solving a minimal cost flow problem. I'm asked to first use the Ford-Fulkerson algorithm on my graph to find a basic solution that will then be used to do the simplex method on that ...
6
votes
0answers
53 views
Estimating multistop routing costs
In many OR problems, it is sometimes a good idea (or necessary) to relax routing constraints.
An example of this occurs in the classical facility location problem, where a warehouse can send out a ...
4
votes
1answer
74 views
How to linearize $f(x,y) = (ax+by)/(x+y)$?
I have a problem which is mainly linear but it has a non-linear component. The objective function is
obj = Linear_term + $c*f(x,y)$ where,
$f(x,y) = (G_1 x_1 + G_2 x_2)/(x_1 + x_2)$.
The decision ...
4
votes
1answer
65 views
the set of optimal solutions of a linear programming (LP) problem as a mapping of right-hand side
Consider a linear programming (LP) problem
\begin{align}
M(b) \in \arg\min_x \{ c^\top x : Ax=b, x \ge 0 \}.
\end{align}
Suppose the LP is feasible and bounded for all values of $b$. We know that $M(...
0
votes
1answer
71 views
How can I find the shortest path for all nodes in a graph from a source $s$?
This is the shortest path problem. I've used a model where we can find the shortest path between the source and a specified destination.
The idea behind this model is that we assign a flow of 1 for ...
5
votes
0answers
115 views
Is this a valid strong polynomial algorithm for deciding LP feasibility?
Let
$$A \cdot X + B \preceq 0$$ be a system of linear inequalities with $X \in \mathbb{R}^n$ $A\in \mathbb{R}^{m\times n}$ and $B \in \mathbb{R}^m$ where $m \geq n$. According to Farkas lemma, exactly ...
5
votes
1answer
52 views
Min-cost flow with per-edge flow conservation
I am trying to solve a linear program that is identical to a min-cost flow problem, except for a difference in the flow-conservation constraint.
Instead of the summed outgoing flow equaling the summed ...
6
votes
1answer
231 views
Multi-period linear dynamic programming with differing in-period dependencies and changes
I’m not sure if I’m wording this right but in a nutshell, my problem is:
I’m modelling potential actions a boat owner can do to their boat. Let’s say he wants to know over the 50 year lifespan of the ...
0
votes
1answer
154 views
How to form math model to solve this problem using cplex
Hiring company has the following requirement within a year;
week 1 to 5: 20
week 6 to 20: 40
week 21 to 40: 35
week 41 to 60: 55
week 61 to 80:75
week 81 to 100: 60
Training time for an ...
18
votes
4answers
886 views
PhD-level textbooks on linear programming
My graduate Linear Programming class uses Bertsimas & Tsitsiklis's Introduction to Linear Optimization. Are there any alternative texts that I could use to supplement this textbook (mainly the ...
1
vote
1answer
92 views
Minimum value for a group of variables in linear programming
I want to use linear programming to assign weights to a number of groups of variables.
Let's assume we have group $A$ with $x,y,$ and $z$ and group $B$ with $m,n,$ and $p$.
Is it possible to define ...
7
votes
3answers
554 views
How to find all vertices of a polyhedron
I have a convex polyhedron given by a set of linear inequalities, for example:
$$
x_1 \geq 0,~~ x_2 \geq 0, ~~x_3\geq 0
\\
x_1+x_2\leq 1,~~ x_2+x_3\leq 1,~~ x_3+x_1\leq 1
$$
I want to list all the ...
5
votes
1answer
58 views
Maximizing a Ratio/Percent
I'm using cvxpy to model a problem. Inside a very large and complex LP, I create two continuous, affine (unconstrained) expressions: $x$ and $y$. Due to how they ...
3
votes
1answer
92 views
Derive “true” shadow price for degenerated LPs using commercial solvers (e.g. Gurobi)
In linear programming for an optimal primal degenerate solution the values of the dual variables are in general not identical with the corresponding shadow prices. Several proposals on how to find the ...
5
votes
1answer
236 views
Can GLPK be used to solve an optimal team selection problem?
My Problem
I am quite new to optimisation, so any advice is appreciated. I am currently trying to solve a problem as follows:
Given a pool of people, we want to create n teams such to find the optimal ...
3
votes
1answer
72 views
Which method to use to solve this multi-objective conflicting objectives
I have the following multiobjective problem.
I need to minimize the user-perceived latency while doing so aggressively minimizing user-perceived latency generates large switching cost (Reconfiguration ...
2
votes
1answer
37 views
Finding bounds on a data sensitivity scenario ILP problem
This is a follow up to a problem I posted here: Modelling a data-sensitivity scenario as an ILP problem
As a recap, I was interested in finding the minimum number of cells that need to be suppressed ...
2
votes
0answers
84 views
Condition for an integer program and its linear relaxation to have the same value
Let $A$ be a $(0,1)$-matrix where no row or column is a zero vector, and consider the following optimization programs \begin{align}(1):\min&\quad y\cdot1\\\text{s.t.}&\quad yA\ge w\\&\quad ...
3
votes
1answer
86 views
Why is the Lagrange Multiplier not equal the Shadow Price (Excel solver, Matlab linprog, Gurobi)?
I have a LP with equality and inequality constraints.
When solving the LP with the excel-solver (GRG Nonlinear) the sensitivity report returns the lagrange multiplier for all constraints.
When solving ...
3
votes
2answers
92 views
Modelling a data-sensitivity scenario as an ILP problem
I am new to linear programming, and I recently came across the following exercise, which I do not know how to solve:
When publishing data, it is sometimes important to "suppress" sensitive ...
6
votes
0answers
76 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 ...
2
votes
1answer
72 views
Can CPLEX output LP solution with primal variables only?
CPLEX writeSolution method outputs both primal and dual variable values of a LP. I know how to parse through the solution file to extract specific primal variable ...
2
votes
1answer
117 views
Linearize sum of continuous and boolean variable
For maximizing the objective function $\sum_i{d_i y_i}+ A x - B \cdot \mathbb{I}_{x>0}$, how can I linearize $ A x - B \cdot \mathbb{I}_{x>0}$ term where $d_i, A$ and $B$ are positive constants ...
1
vote
0answers
78 views
Expansion heuristic using gurobi reduced cost / shadow price (LP)
Gurobi 9.0.0 // C++ // LP
Let us assume the following problem with three nodes: (1)-----(2)-----(3)
node (1) is producing ...
1
vote
2answers
80 views
How this problem can be defined as MultiObjective optimisation
I need to optimize the end-to-end latency of a multi-component application.
Assuming that the application has 10 components, component 1-5 is hosted by device 1, and device 2 is hosting the other 5 ...
2
votes
1answer
84 views
Specific usecase of two-phase simplex algorithm
The problem below aims to find to most optimal way to transport the fuel :
A company Er must transport a type of fuel from its two refineries Ra and Rb to its two points of sale PV1 and PV2. The ...
3
votes
3answers
98 views
How to write distance specific constraint?
Suppose there are a few plants (p) and few customers (c). The supply (Sp), distance (Dpc), cost (COSTpc) and demand (DEMANDc) between them is given. I have a constraint that 90% of total demand of all ...
2
votes
1answer
113 views
Is my formulation correct and how to formulate this IF-THEN constraint?
I have system with $N_U$ users and $N_T$ transmitters. Multiple transmitters can transmit to a single users and one transmitter can transmit to many users, i.e., two sets of transmitters serving two ...
4
votes
1answer
71 views
How would you linearize this scheduling problem? Or how would you solve this? It is variation of a set coverage problem for OpenSolver
So, it's been about 15 years since I took my OR class in college. I'm not versed in any programming language besides a little bit of VBA.
A client of mine is looking to solve the following problem. I ...
4
votes
1answer
89 views
Formulating these logical constraint in an ILP
I have these two constraints :
$z \leq My$
$t \leq M'y $
where $z$ and $t$ are two integer variables $ z, t\geq 0$, $y$ is a binary variable, and $M$, $M'$ are two big numbers.
So basically these ...
1
vote
1answer
90 views
How can I have minimum amount of resources wasted in this resource allocation problem?
I have a demand, $d$
I also have supply from 1000 sources. The supplies from those $N$ (for example, $N=1000$) sources are given by
$s_1,s_2,s_3,\cdots,s_N$. So,the total supply is : $s_1+s_2+\cdots+...
2
votes
0answers
40 views
High-mix manufacturing capacity
I'm not an expert in OR but I would like to determine what is the maximum manufacturing capacity of a plant (or how much a plant can produce of mix products).
Each person in the plant has a known set ...
7
votes
0answers
74 views
Provide basic solution to CLP
I'm using Pyomo to formulate an LP with approx 500,000 constraints and 200,000 decision variables. The LP is solved using CLP. Some instances fail to return even a feasible solution after many ...
17
votes
2answers
229 views
Automating the column generation decomposition process
When trying a decomposition technique such as column generation, most of the times my approach is to look at the problem and then:
Decide what a column should represent
Write the Master Problem
Write ...
6
votes
2answers
117 views
Simplex algorithm and extreme points
For this question my short-hand is LP = linear program, BFS = basic feasible solution, SEF = standard equality form.
Since the Simplex algorithm iterates from extreme point to extreme point (...
3
votes
1answer
104 views
Logical constraint in ILP
I want to write the following constraint:
Let $z$ be an integer variable such that $0\le z\le M$, and $t$ be a binary variable where $M$ denotes big-M. The logical constraint is as follows:
if $z \...
3
votes
1answer
123 views
How to express this logical constraint for an ILP?
I am trying to write an ILP for a problem but I have this logical constraint and I'm stuck.
In my model I have:
two binary variables: $x$ and $y$
One Integer variable: $z$
The logical constraint I am ...
4
votes
2answers
124 views
Faster implementation of “or” constraints in ILP
I have implemented a set of "or" constraints in my ILP using binary decision variables (as in this method). It works fine for smaller problems, but when I try to increase the number of ...
3
votes
0answers
29 views
Linear functions in Lenstra's algorithm
I had asked this question at MathOverflow and was pointed here.
I'm working on implementing Lenstra's algorithm. At the bottom of p.5 (at "construct $n+1$ linear functions"), he says to ...
0
votes
0answers
111 views
Resource constrained LP problem
I am working on Diet Allocation problem. Where we need to provide food piece for protein deficiency. The data is as below:
...
1
vote
0answers
274 views
Canonical form of a linear program
I have a linear programming problem that I want to write in the canonical form: \begin{align}\min&\quad c^\top X\\\text{s.t.}&\quad A\cdot X\le b\end{align}
The problem is given by \begin{...
