Questions tagged [linear-programming]

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

Filter by
Sorted by
Tagged with
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 ...

1
2 3 4 5 6