Apparatus and method for using and solving linear programming problem and applications thereof

• US 9,007,961 B2
• Filed: 11/21/2011
• Issued: 04/14/2015
• Est. Priority Date: 11/22/2010
• Status: Active Grant

• Current Assignee: May Patents Ltd.
• Original Assignee: May Patents Ltd.
• Inventors: Binder, Yehuda
• Primary Examiner(s): Zhou, Yong
• Application Number:
  US13/300,928
• Publication Number:
  US 20120127893A1
• Time in Patent Office: 1,240 Days
• US Class Current: 370/255
• CPC Class Codes: H04L 49/101 using crossbar or matrix

Abstract

Method and system for analyzing a linear programming problem or any other problem involving inequalities constraints set relating to multiple variables. An initial feasible region is calculated based on a sub-set of the constraints set. The feasible region is updated based on the additional constraints added one at a time. The method checks for feasibly, identifies active constraints, and provides end-points of the feasible region. The method may be applied to a control system or to a crossbar switch handling routing between multiple input and multiple outputs, such as digital data networking switch used to route TDM digital data streams being packet, frame or cell based, in a LAN, WAN, MAN or Internet application.

Claims

1. An apparatus configured to analyze a set of M inequalities constraints relating to N variables wherein M>

N>

2, the apparatus comprising a memory; and

a processor configured by the memory to perform a method comprising the steps of;

(a) selecting a sub-set of R constraints wherein R>

N;

(b) calculating an Initial Feasible Region (IFR) defined by one or more endpoints and N constraints associated with each endpoints, wherein the endpoints are the intersections of the N constraints out of the selected sub-set, treated as equalities;

(c) selecting any first constraint out of the M constraints which is not part of the selected sub-set; and

(d) calculating a Temporary Feasible Region (TFR) by manipulating the IFR versus the first constraint.

2. The apparatus according to claim 1 wherein configured to analyze the entire set of said M inequalities constraints, the method further comprising the steps of:

(e) selecting a constraint which was not yet selected; and

(f) updating the temporary feasible region (TFR) by manipulating the temporary feasible region (TFR) versus the selected constraint;

wherein steps (e) and (f) are repeated until all the constraints are selected, and wherein the last TFR is declared as the feasible region for the set of M inequalities constraints.

3. The apparatus according to claim 2 further configured to check feasibility of the set of M inequalities constraints, the method further comprising a step after step (f) of checking the feasibility of the TFR, and wherein if a feasible TFR is not obtained, declaring the set as non-feasible.

4. The apparatus according to claim 1 further configured to check the feasibility of the set of M inequalities constraints, the method further comprising after said step (b) a step of checking the feasibility of the IFR, and wherein if a feasible IFR is not obtained, declaring the set as non-feasible.

5. The apparatus according to claim 1 further configured to check feasibility of the set of M inequalities constraints, the method further comprising a step after step (d) of checking the feasibility of the TFR, and wherein if a feasible TFR is not obtained, declaring the set as non-feasible.

6. The apparatus according to claim 1 further configured to check activity of constraints in the set of M inequalities constraints, the method further comprising a step after steps (c) or (e) of checking the TFR, and declaring any selected constraint that is not part of the TFR as non-active.

7. The apparatus according to claim 6, wherein the TFR is checked to be an open or a closed region.

8. The apparatus according to claim 7 wherein the TFR is a closed region, and a selected constraint is declared as non-active if all the endpoints defining the TFR satisfy the selected constraint.

9. The apparatus according to claim 1 for scheduling a switching system, the apparatus further comprising a switch having a plurality of P input ports for receiving incoming digital data streams and a plurality of Q output ports for outputting outgoing digital data streams, and wherein the switch is configurable to be in multiple states, wherein in each state each of the input ports is connected to a single output port and each of the output ports is connected to a single input port for transferring the incoming streams into outgoing streams, and wherein said method is used for scheduling as to determine the states order and the length of stay in each state.

10. The apparatus according to claim 9 configured to be used in digital data networking application, wherein the switch is used for routing digital data streams.

11. The apparatus according to claim 10, wherein the switch is operative to receive and route a plurality of digital data streams, and wherein each digital data stream is carrying information using TDM (Time Division Multiplexing) scheme.

12. The apparatus according to claim 11, wherein the digital data streams include packets, cells or frames, and wherein the switching is respectively packet, cell or frame based.

13. The apparatus according to claim 9, wherein the apparatus is part of LAN (Local Area Network), WAN (Wide Area Network), MAN (Metropolitan Area Network) or the Internet.

14. The apparatus according to claim 9, wherein said digital data streams are carried over a conductive medium, and wherein said input and output ports include connectors.

15. The apparatus according to claim 9, wherein said digital data streams are carried over a non-conductive medium, and wherein said input and output ports include antennas or fiber-optics connectors.

16. The apparatus according to claim 9, wherein said switch is at least one of an OSI layer 2 and OSI layer 3 switch.

17. The apparatus according to claim 16, wherein the routing is based on at least one out of IP (Internet Protocol), TCP/IP protocol, Border Gateway Protocol (BGP), and Multi-Protocol Label Switching (MPLS).

18. The apparatus according to claim 9, wherein P=Q.

19. The apparatus according to claim 9, wherein P≠

Q.

20. A switching system based on a scheduling method, for use with a set of M inequalities constraints relating to N variables wherein M>

N>

2, comprising;

a memory for storing the scheduling method;

a processor configured by the memory to perform the scheduling method; and

a switch having a plurality of P input ports for receiving incoming streams and a plurality of Q output ports for outputting outgoing streams, the switch is configurable to be in multiple states, wherein in each state each of the input ports is connected to a single output port and each of the output ports is connected to a single input port for transferring the incoming streams into outgoing streams;

wherein said switch is coupled to said processor for using said scheduling method as to determine the states'"'"' order and the length of stay in each state,

and wherein said scheduling method comprising the steps of;

(a) selecting a sub-set of L constraints wherein L>

N;

(b) calculating an initial feasible region (IFR) defined by one or more endpoints and the N constraints corresponding to each endpoints, wherein the endpoints are the intersections of N constraints out of said selected sub-set, treated as equalities;

(c) selecting a first constraint out of the M constraints which is not part of the selected sub-set; and

(d) calculating a temporary feasible region (TFR) by manipulating the initial feasible region versus the first constraint.

21. The system according to claim 20, wherein said scheduling method is based on solving a standard linear programming.

22. The system according to claim 21 configured to be used in digital data networking application, wherein the switch is used for routing digital data streams.

23. The system according to claim 22, wherein the switch is operative to receive and route a plurality of digital data streams, and wherein each digital data stream is carrying information using TDM (Time Division Multiplexing) scheme.

24. The system according to claim 23, wherein the digital data streams include packets, cells or frames, and wherein the switching is respectively packet, cell or frame based.

25. The system according to claim 23, wherein the switch is part of LAN (Local Area Network), WAN (Wide Area Network), MAN (Metropolitan Area Network) or the Internet.

26. The system according to claim 25, wherein said digital data streams are carried over a conductive medium, and wherein said input and output ports include connectors.

27. The system according to claim 25, wherein said digital data streams are carried over a non-conductive medium, and wherein said input and output ports include antennas or fiber-optics connectors.

28. The system according to claim 25, wherein said switch is at least one of an OSI layer 2 and OSI layer 3 switch.

29. The system according to claim 28, wherein the routing is based on at least one out of IP (Internet Protocol), TCP/IP protocol, Border Gateway Protocol (BGP), and Multi-Protocol Label Switching (MPLS).

30. The system according to claim 20 configured to analyze the whole set of the M inequalities constraints, the method further comprising the steps of:

(e) selecting a constraint which was not yet selected; and

(f) updating the temporary feasible region (TFR) by manipulating the temporary feasible region (TFR) versus the selected constraint;

wherein steps (e) and (f) are repeated until all the constraints are selected, and wherein the last TFR is declared as the feasible region for the set of M inequalities constraints.

31. The system according to claim 20 further configured to check activity of constraints in the set of M inequalities constraints, the method further comprising a step after steps (c) or (e) of checking the TFR, and declaring any selected constraint that is not part of the TFR as non-active.

32. The system according to claim 31, wherein the TFR is checked to be an open or a closed region.

33. The system according to claim 32 wherein the TFR is a closed region, and a selected constraint is declared as non-active if all the endpoints defining the TFR satisfy the selected constraint.

34. The system according to claim 20, wherein P=Q.

35. The system according to claim 20, wherein P≠

Q.