Questions tagged [linear-programming]
For questions related to problems that optimize (i.e., minimize or maximize) a linear objective subject to linear constraints.
300
questions
1
vote
0answers
25 views
Unifying constraint matrices in sparse situations
$\DeclareMathOperator\Set{Set}$
Let
$Set=\{x\in\mathbb Z^{n}:\exists y\in\mathbb Z^m\text{ satisfying } A[x,y]'\leq b\}$
where $A$ has $r=km$ rows and $k=O(1)$.
I am trying to write
$$
Set=\{x\in\...
4
votes
3answers
168 views
Clustering points based on a distance matrix
Although I asked this question on stackoverflow to possibly reach a broader audience, I wonder your inputs about this problem. Without giving much research into this, I thought p-center problem ($x_{...
2
votes
0answers
67 views
Solving transportation problem by the Network Simplex
I am trying to solve the following problem using Network Simplex method. But I have questions.
My attempt:
Basis Matrix$(B)$
Rows: 1, 2, 3, 4, 5
Column: (1,3) (1,4) (1,5) (2,3) (2,4) (2,5)
$$
\...
2
votes
0answers
45 views
Two binding constraints - Linear Programming
I'm having some troubles to continue solving my system, I'm used to solve such systems but with "one" binding constraint, if someone could give me some helpful hints so I can solve it I will ...
2
votes
1answer
232 views
If-then constraint with continuous variables
I was usually using if-then constraints with integer variables but ended up using continuous variables and got confused. I have variables $x_{ij}\in\mathbb{R}_{\geq 0}$, and would like to force the ...
3
votes
1answer
205 views
Algorithms for sparse linear systems
I've long wondered this, but what is the algorithm(s) implemented in modern linear equation solvers for sparse systems?
The obvious answer I can think of is Gauss-Jordan with a bunch of tricks to make ...
1
vote
0answers
44 views
To estimate new sales from history
A fruit supplier sells 3 types of fruits. The company has 3 salespersons.
Here are the sales quantity of each person for each fruit. The total sales figure is available. (this is all the available ...
3
votes
0answers
30 views
PuLP Python: How to linearize an inequality involving an integer variable
I am working on a Copper payables problem where the objective function is to maximise the sum of copper payable over a time period, T.
The total amount of payable tonnes i.e. what the customer will ...
1
vote
0answers
31 views
How can I see the engine log when solving a LP using pulp (python)?
I wonder which command should I use to see how the steps the pulp solver is doing when solving a linear program.
2
votes
1answer
104 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+...
1
vote
1answer
28 views
How to dynamically set variable names in Pyomo?
I am looking to set variables in my Pyomo model by using a loop, so that they can be created automatically. However, each variable also contains bounds.
I was hoping that it can loop through a ...
4
votes
2answers
165 views
Two-Objective Optimization in CPLEX
Until now, I used CPLEX to solve single-objective optimization problems only,
but now I need to solve a two-objective mixed-integer linear optimization problem and I noticed that CPLEX 12.6.9 (unlike ...
7
votes
1answer
102 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 ...
6
votes
1answer
942 views
What are good reference books for introduction to operations research?
The reference books should cover the wide range of problem-solving techniques and methods.
2
votes
2answers
94 views
Multi-objective function normalization
I am trying to solve the multi-objective function of my linear program. Are there another approaches other than the weighted sum approximation?
1
vote
0answers
64 views
Decomposition of Polyhedra
There is no doubt that clear examples consolidate the understanding of concepts being learnt. I am new to finding the structure and decomposition of a polyhedra. Suppose that we have the system
$$ \...
4
votes
1answer
65 views
How to convert static variables into arrays for use with PuLP
I have the following code in Python and PuLP which uses static variables. I want to know how to solve the problem by converting all of the LpVariable parts into an array, as well as the constraints. ...
3
votes
0answers
50 views
Where I can study some job shop scheduling by course (video )?
I am seeking the help to know where I can study the job shop scheduling Heuristics or using solver
by some course/video as I see some of books and papers hard to understand .
It is hoped that the ...
1
vote
0answers
61 views
How to start the Dantzig-Wolfe decomposition?
I have the following problem: \begin{align}\min&\quad3x_1+5x_2+3x_3-2x_4+3x_5\\\text{s.t.}&\quad x_1+x_2+x_3+x_4\geq3\\&\quad3x_1+x_2+5x_3+x_4-2x_5\geq6\\&\quad x_1+2x_3-x_4\geq2\\&...
0
votes
1answer
41 views
Adding slack nodes to min cost network flows
I have the following question. I want to clarify couple of points.
As you can see, total demand and total supply does not match, we do not have enough demand. What I want to ask is:
Do we need to ...
27
votes
1answer
3k views
How to linearize the product of a binary and a non-negative continuous variable?
Suppose we have a binary variable $x$ and a non-negative continuous variable $y$. How can we linearize the product $x y$?
1
vote
1answer
39 views
Maximum flow minimum cut
For the following problem I am trying to find maximum flow and minimum cut:
I found the maximum flow as 6 like this:
$1-3-7-8:2 flows$
$1-2-5-8: 2 flows$
$1-3-4-5-8:1 flow$
$1-3-4-6-5-8:1 flow$
But I ...
4
votes
1answer
180 views
Column generation for a linear optimization problem
I have an LP that has exponentially many constraints, and just linearly many variables. The dual of the problem, therefore, has exponentially many variables, while just linearly many constraints. My ...
3
votes
1answer
103 views
Find a particular optimal solution
After writing an integer linear program in AMPL, I solved it using CPLEX. Now, I have some variables that must necessarily be 1, others that must necessarily be 0 and finally it is possible that some ...
1
vote
1answer
57 views
$i \neq j$ as a linear constraint where variables are binary
Let $i$ and $j$ be two binary variables.
How can I express $i \neq j$ as a linear constraint?
0
votes
1answer
51 views
Minimum cost flow problem with negative cost arcs
As far as I know, if there is a directed arc with a negative cost, we change its direction to its opposite and get a positive cost. But in the following question, if we change the direction of the arc ...
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
3answers
912 views
How do you take into account order in linear programming?
How do you write order in a linear program?
For instance, you want to arrange red and blue marbles labelled 1 – 30 each, and you would want to arrange it in ascending order, you cannot have red ...
8
votes
4answers
519 views
Algorithm for simplifying a set of linear inequalities
I am looking for an algorithm that, given a set of linear inequalities in $m$ variables, returns a simplified set. "Simplified" may mean an equivalent set with a smallest number of ...
1
vote
0answers
32 views
Vertices of Polytope using Gurobi
Is there any way I can obtain all the vertices of a polytope using Gurobi?
If this isn't possible, can I log all the intermediate vertices that Simplex finds before it hits the optimal one?
3
votes
2answers
174 views
Modeling in integer programming vs modeling in constraint programming
I have some experience with linear and integer programming modeling (I read Model Building In Mathematical Programming by Williams).
Now I am trying to learn how to model with constraint programming. ...
3
votes
1answer
128 views
How to set combined stop condition in AMPL/CPLEX?
I would like to set a stop condition combined of a timelimit and a relative MIP gap.
So I would like AMPL/CPLEX to look for the solution of my LP for an hour and if there isn't a solution stop if or ...
11
votes
2answers
1k views
Linear programming: objective function with “buckets”
I had a linear programming problem with the following objective function
$$f(x) = \sum_{j}x_jq_jp_j - \sum_{i}\left(\sum_{j}x_jq_jC_{ij} \right) c_i$$
Where $q, p, C, c$ are known.
This problem was ...
3
votes
1answer
78 views
In integer programming what's the difference between using lower upper bound constraints and using a big M constraints?
I've noticed that for integer programming models with binary variables some use upper bound constraints and others use big M constraints in order to have two mutually exclusive choices.
I have trouble ...
1
vote
1answer
74 views
How can I formulate an objective function that minimises the number of items required to solve a problem
I am currently trying to solve a problem where I need to minimise transport cost through the choice of vehicle (and how many of each choice) subject to a given demand.
The problem:
There are currently ...
16
votes
6answers
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 ...
2
votes
1answer
96 views
Defining Solution Space in MILP / LP using If Then Statements
I have the following statements for an MILP:
Variables:
$c$ (can be $1$ or $0$);
$\alpha_j$ (real numbers with $0\le\alpha_j\le1$).
I have a linear inequality system for $\alpha_j$:
$\sum_jv_j\...
3
votes
1answer
52 views
Strict inclusion for facility location formula and aggregate facility location formula
I am trying to prove that $P_{FL} \subset P_{AFL}$ where \begin{align}P_{FL}&=\left\{({\bf x},{\bf y})\,\,\middle\vert\,\,\forall i,j:\sum_{j=1}^nx_{ij}=1,x_{ij}\le y_j,0\le x_{ij},y_j\le1\right\}\...
2
votes
0answers
69 views
How to linearize this multiplicative constraint?
I have a constraint in the form
$\sqrt{|\sum_{c\in C}{h_cw_c}|^2}\ge\sqrt{x}\zeta$
Here, $h_c$ is s row vector (know), $w_c$ is a column vector (variable).
$x$ and $\zeta$ are also optimization ...
-2
votes
1answer
60 views
How can I model this Hyperbolic constraint?
In this problem, $\beta_u$, $w_{u,c}$ (a vector of complex elements), $x_u$ are optimization variables.
Now,
$||2\sqrt{\frac{\pi_u}{2}}\beta_u; h_{u,c}^{\rm H}w_{u,c}-\frac{1}{2\pi_u}x_u-1||_2\le h_{u,...
13
votes
3answers
2k views
How Close Is Linear Programming Class to What Solvers Actually Implement for Pivot Algorithms
As part of a final project for my linear programming course, I have been asked to discuss implementations of pivot algorithms, including which combinations of the ideas we have talked about in class ...
0
votes
1answer
202 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 ...
9
votes
2answers
150 views
How to get all the facet inequalities from a set of valid inequalities?
For a given set of valid inequalities $\cal V$
$$
\left\{\sum_{i}^n w_k x_i + c_k \le 0\right\}_k
$$
we can obtain a polyhedron $P$ in $n$-dimensional space. It's known that the polyhedron $P$ can be ...
2
votes
0answers
56 views
Determine set of “arbitrage-free” regional prices
I am seeking for a way how to determine set of "arbitrage-free" regional prices for a single commodity market.
There are $N>1$ production units with costs $C^{prod}_i, i=1,\dots,N$ and ...
3
votes
0answers
58 views
Optimal Seat Allocation Problem
I have to do an operations research assignment based on optimal seat allocation. The problem goes something like this. There are 5 rooms in an office each with a separate seating capacity. We now have ...
2
votes
1answer
46 views
Understanding MDP's Dual Linear Program
I'm trying to understand a proof in Puterman'05 (Markov Decision Processes: Discrete Stochastic Systems). My question is within Theorem 6.9.1 pertaining to the equivalence of solutions to the primal (...
2
votes
1answer
64 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
55 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
202 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 ...
5
votes
0answers
106 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 ...
